EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1270. Semidefinite programming by projective cutting planes

Invited abstract in session TB-38: Advances in Complex and Real Semidefinite Programming, stream Conic Optimization: Theory, Algorithms, and Applications.

Tuesday, 10:30-12:00
Room: 34 (building: 306)

Authors (first author is the speaker)

1. Daniel Porumbel
CEDRIC CS Lab, CNAM

Abstract

We consider the most standard SDP (semidefinite programming) program in a cutting-planes setting, i.e., the program is formulated using the infinitely-many linear cuts that define the SDP cone. We go beyond the most classical approach that relies on repeated separation; to separate a matrix X is enough to test if its minimum eigenvalue is above or below zero. Instead, we upgrade the separation sub-problem to a projection sub-problem: given a feasible matrix X in the SDP cone and an arbitrary direction D, what is the maximum t such that X+tD stays in the SDP cone? This new sub-problem enabled the new algorithm to converge to the optimal solution through a sequence of both inner and outer solutions (with regards to the SDP cone). The general Projective-Cutting-Planes logic was first proposed in a purely linear context [Daniel Porumbel, Projective Cutting-Planes, SIAM Journal on Optimization, 30(1): 1007-1032, 2020]. We will show that the projection sub-problem can also be solved very efficiently in a new SDP context. One way to solve it would be to compute the generalized eigenvalues of X and -D. But we seek maximum speed and we solve it using certain factorizations suitably tailored to our given context. Results suggest that the overall method may be very competitive (compared to Mosek or ConnicBundle) for matrix sizes larger than 2000 × 2000. It is less competitive if the matrix size is low and if the initial program has many linear constraints.

Keywords

Status: accepted

Back to the list of papers