Combining ADAL with Factorizing the Dual to Solve SDP

joint work with Marianna De Santis and Franz Rendl.

Using semidefinite programming has become a promising method for solving or approximating various combinatorial optimization problems. However, solving semidefinite programs is challenging due to either the large size of the matrices involved or a huge number of constraints. The most prominent methods, interior point methods, run out of memory for many practical applications.

Other algorithms for solving semidefinite problems are based on augmented Lagrangian methods using various ways of dealing with the semidefiniteness constraint. We developed such an augmented Lagrangian algorithm where we replace the semidefiniteness constraint of the dual problem by a factorization Z=VV^t. Using this factorization, we end up with an unconstrained (non-convex) problem in V. We then perform updates of this matrix V towards the optimal solution of Z following an alternating direction method or in the fashion of the boundary point method. We will present results for computing the theta number of a graph and computing bounds on the quadratic linear ordering Problem.