292. New results for sparse conic reformulations
Invited abstract in session WD-2: Conic and polynomial optimization, stream Conic optimization: theory, algorithms and applications.
Wednesday, 11:25 - 12:40Room: M:O
Authors (first author is the speaker)
| 1. | Markus Gabl
|
Abstract
Positive semidefinite and copositive optimization offers powerful tools for nonlinear optimization but often suffer from poor scalability due to the matrix variable's high dimension and the conic constraints' computational demands. One remedy is to exploit sparsity patterns in the problem data via sparse reformulations where only submatrices are subjected to conic constraints, while the rest of the variables are dropped from the problem. The theoretical tools from linear algebra that enable these reformulations come from the theory of positive semidefinite and completely positive (cp) matrix completion. Due to the limitations of that theory, exact reformulations are only available for specific sparsity patterns, unless one considers additional problem structure. The latter has hardly been explored so far. We present new results that extend existing literature in several ways. We present new cp completion results that lie outside known sufficient conditions and are based on copositive optimization theory and recent results on the uniqueness of cp-factorizations. Further, we discuss a strategy for sparse copositive reformulations of QPs where only the objective, but not the constraints, exhibit sparsity.
Keywords
- Conic and semidefinite optimization
- Global optimization
- Large- and Huge-scale optimization
Status: accepted
Back to the list of papers