667. Computational complexity of sum-of-squares bounds for copositive programs
Invited abstract in session MA-49: Sums-of-squares optimization, stream Conic and polynomial optimization.
Monday, 8:30-10:00Room: Parkinson B10
Authors (first author is the speaker)
| 1. | Marilena Palomba
|
| IDSIA USI-SUPSI | |
| 2. | Lucas Slot
|
| ETH Zürich | |
| 3. | Luis Felipe Vargas
|
| USI - SUPSI, Istituto Dalle Molle Studi sull’Intelligenza Artificiale (IDSIA) | |
| 4. | Monaldo Palmo Mastrolilli
|
| Dipartimento tecnologie innovative, SUPSI, IDSIA USI-SUPSI |
Abstract
In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations of copositive programs based on semidefinite programming (SDP) have been proposed in the literature, meant to provide tractable bounds. However, while these SDP-based relaxations are amenable to the ellipsoid algorithm and interior point methods, it is not immediately obvious that they can be solved in polynomial time (even approximately). In this paper, we consider the sum-of-squares (SOS) hierarchies of relaxations for copositive programs introduced by Parrilo (2000), de Klerk & Pasechnik (2002) and Peña, Vera & Zuluaga (2006), which can be formulated as SDPs. We establish sufficient conditions that guarantee the polynomial-time computability (up to fixed precision) of these relaxations. These conditions are satisfied by copositive programs that represent standard quadratic programs and their reciprocals. As an application, we show that the SOS bounds for the (weighted) stability number of a graph can be computed efficiently.
Additionally, we provide pathological examples of copositive programs (that do not satisfy the sufficient conditions) whose SOS relaxations admit only feasible solutions of doubly-exponential size.
Keywords
- Convex Optimization
- Programming, Semidefinite
Status: accepted
Back to the list of papers