Computer Science NASC Seminar

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

Immanuel Bomze, University of Vienna

September 13, 2013 10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110

Fall 2013 NASC Seminars Calendar


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.

top | contact webmaster