Vortrag aus Archiv

Applications and approximations for copositive optimisation

10.06.2013

During the last century, conic optimisation has been established as a useful tool with a wide range of applications. In conic optimisation, we are minimising a linear objective function subject to some linear constraints and a cone constraint. In this talk, we will look at a special type of conic optimisation called copositive optimisation. For this type of conic optimisation, the cone that we are considering is the cone of copositive matrices. This provides numerous applications, and in the first half of this talk we shall look at a new proof for how the NP-hard problem of finding the stability number of a graph can be reformulated as a copositive optimisation problem. From this we get that copositive optimisation is NP-hard. Due to this difficulty, when considering a copositive optimisation problem, we often replace the copositive cone with a simpler approximation of it. For the second half of this talk, we shall consider some new results on a sum-of-squares based class of inner approximations called the Parrilo cones.

This was joint work with Mirjam Dür (Universität Trier), Luuk Gijben (Rijksuniversiteit Groningen) and Roland Hildebrand (Université Joseph Fourier).