Computational Mathematics and Scientific Computing Seminar

---

A Nasty Cone with Nice Properties - New Issues in Copositive Optimization

Speaker: Immanuel Bomze, University of Vienna

Location: Warren Weaver Hall 1302

Date: Sept. 13, 2013, 10 a.m.

Synopsis:

A symmetric matrix is called copositive, if it generates a quadratic form taking no negative values over the positive orthant. Contrasting to positive-semidefiniteness, checking copositivity is NP-hard. In a copositive optimization problem, we have to minimize a linear function of a symmetric matrix over the copositive cone subject to linear constraints. This convex program has no non-global local solutions. On the other hand, there are several hard non-convex programs which can be formulated as copositive programs, among them mixed-binary QPs or Standard QPs. Some of these problems (e.g. the Standard QP) admit a PTAS, others are APX-hard. The conic formulation offers a unified view into some key classes of continuous and discrete optimization problems, and applications range from machine learning to several combinatorial problems, but also allows for a treatment of mixed-integer nonlinear problems under uncertainty. This optimization technique shifts complexity from global optimization towards sheer feasibility questions. Approximation hierarchies offer a way to obtain approximate solutions by tractable conic (e.g., semidefinite) optimization techniques.