Abstract: Solving an optimisation problem usually involves choosing an appropriate algorithm or designing a new one if none exists. This may be a difficult task as some problems are notoriously hard, for instance NP-hard problems such as the famous travelling salesman problem. However “P versus NP” is not the only challenge faced by the researchers in optimisation theory. There are numerous open questions whose resolution will lead to breakthroughs in our understanding of optimisation.
In this talk I will focus on two challenging geometric problems that originate from computational complexity and representational challenges in convex optimisation: the polynomial Hirsch conjecture and the generalised Lax conjecture. The former asks for a polynomial bound for the combinatorial diameter of a polytope, and the latter is about representing a class of algebraically-defined constraints as slices of the cone of positive semidefinite matrices.