EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1888. From approximate to exact optimal solutions of large semidefinite programs
Invited abstract in session WA-38: Recent advances in LP and SDP for discrete optimization problems, stream Conic Optimization: Theory, Algorithms, and Applications.
Wednesday, 8:30-10:00Room: 34 (building: 306)
Authors (first author is the speaker)
| 1. | David de Laat
|
| TU Delft | |
| 2. | Henry Cohn
|
| Microsoft Research and MIT | |
| 3. | Nando Leijenhorst
|
| Delft University of Technology |
Abstract
For semidefinite programs where the solution is nonunique but the dimension of the optimal face is smaller than the dimension of the affine space, it is not immediately clear how to round the numerical output of an interior-point solver to an exact optimal solution. Rounding each entry of the solution matrices often does not work since the analytical center of the optimal face is complicated to describe. Projecting into the affine space also does not work, since the projection will not be positive semidefinite. In [Dostert, de Laat, Moustrou 2021] a rounding approach using the LLL algorithm is given. I will explain our improved method, using the LLL algorithm in different ways, which is much faster for large semidefinite programs. This allows us to prove the optimality of several spherical codes using semidefinite programming bounds.
Keywords
- Programming, Semidefinite
- Algorithms
- Interior Point Methods
Status: accepted
Back to the list of papers