Lift me up but not too high: fast algorithms to solve semidefinite programs with block-diagonal constraints

Nicolas Boumal - Université catholique de Louvain (Belgium)
May 13 2014 - 4:00pm
Event type: 
110 Fine Hall

We consider optimization problems of the following form (sometimes called Orthogonal-Cut):
minimize f(X) such that X is positive semidefinite and the diagonal blocks of X are identity matrices.
Such programs notably come about as relaxations of certain quadratically constrained quadratic programs. When f(X) is linear, this is a semidefinite program (SDP), and it can thus be solved in polynomial time with interior point methods (IPM's). Nevertheless, IPM's are still rather slow. The main reason for this is that IPM's deal internally with full-rank matrices X of large size. This is a waste, considering that (in the targeted applications) we expect low-rank solutions to exist. One way to address this is to factor X = YY^T with Y, a tall and skinny matrix. Then, attempt to solve the new problem in Y. As long as Y is not square, this is still hard to solve globally. But fortunately, one can show that as soon as we find a merely local optimizer of the problem in Y that is also rank-deficient, then, the associated X = YY^T is a global optimizer of the convex program. The strategy is thus to start with skinny Y's, find a local optimizer and check its rank. Do over with a fatter Y until rank deficiency is detected. This idea is already exploited in the solver SDPLR. We further leverage the fact that for the program under consideration, the factors Y live on a Riemannian manifold. Using Riemannian optimization algorithms, we can then solve the intermediate problems orders of magnitude faster than the competition. We show numerical results on the generalized Procrustes problem using Manopt, our Riemannian optimization toolbox.