Mirjam Duer
TU Darmstadt
Abstract. Optimization over convex cones has become increasingly popular in recent years, the most prominent cones being the positive semidefinite cone and the second order cone. Semidefinite programming provides good and efficiently computable relaxations for several hard combinatorial and quadratic problems. However, it is known that these bounds may be improved by solving optimization problems over the copositive cone. Moreover, it has been shown that certain types of quadratic problems can be reformulated as copositive programs. The drawback of this approach is a jump in complexity, as copositive programs are NP-hard. In this talk, we introduce a new approximation scheme which allows to solve copositive programs to a prescribed precision. The approach relies on inner and outer polyhedral approximations of the copositive cone. Substituting the copositive cone with these approximating cones gives a sequence of linear programs which can be solved efficiently and which approximate the copositive program arbitrarily well. The approximations can be refined in such a way that only those parts of the cone are refined which are relevant for the optimization, which reduces the computational effort.
This is joint work with Stefan Bundfuss.