25. Random Projections for Semidefinite Programming and Polynomial Optimization
Invited abstract in session TD-2: Conic and polynomial optimization, stream Conic and polynomial optimization.
Thursday, 14:45 - 16:15Room: C 103
Authors (first author is the speaker)
| 1. | Monse Guedes Ayala
|
| The University of Edinburgh | |
| 2. | Pierre-Louis Poirion
|
| RIKEN-AIP | |
| 3. | Lars Schewe
|
| School of Mathematics, University of Edinburgh | |
| 4. | Akiko Takeda
|
| University of Tokyo |
Abstract
Random projections, a dimensionality reduction technique, have been found useful in recent years for reducing the size of optimization problems. In this presentation, we explore using random projections to approximate semidefinite programming (SDP) problems by reducing the size of matrix variables, thereby solving the original problem with less computational effort. We provide some theoretical guarantees on the quality of the projection. We also investigate the performance of the approach on semidefinite relaxations appearing in polynomial optimization, with a focus on combinatorial optimization problems.
Keywords
- Conic and semidefinite optimization
- SS - Semidefinite Optimization
Status: accepted
Back to the list of papers