Computational complexity of sum-of-squares bounds for copositive programs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909450487463936 |
|---|---|
| author | Palomba, Marilena Slot, Lucas Vargas, Luis Felipe Mastrolilli, Monaldo |
| author_facet | Palomba, Marilena Slot, Lucas Vargas, Luis Felipe Mastrolilli, Monaldo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03698 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational complexity of sum-of-squares bounds for copositive programs Palomba, Marilena Slot, Lucas Vargas, Luis Felipe Mastrolilli, Monaldo Optimization and Control Computational Complexity 90C22, 90C23, 90C25, 90C27, 90C51, 90C60 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. |
| title | Computational complexity of sum-of-squares bounds for copositive programs |
| topic | Optimization and Control Computational Complexity 90C22, 90C23, 90C25, 90C27, 90C51, 90C60 |
| url | https://arxiv.org/abs/2501.03698 |