# zbMATH — the first resource for mathematics

Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs. (English) Zbl 1445.90074
Summary: We consider semidefinite programs (SDPs) with equality constraints. The variable to be optimized is a positive semidefinite matrix $$X$$ of size $$n$$. Following the Burer-Monteiro approach, we optimize a factor $$Y$$ of size $$n \times p$$ instead, such that $$X = YY^T$$. This ensures positive semidefiniteness at no cost and can reduce the dimension of the problem if $$p$$ is small, but results in a nonconvex optimization problem with a quadratic cost function and quadratic equality constraints in $$Y$$. In this paper, we show that if the set of constraints on $$Y$$ regularly defines a smooth manifold, then, despite nonconvexity, first- and second-order necessary optimality conditions are also sufficient, provided $$p$$ is large enough. For smaller values of $$p$$, we show a similar result holds for almost all (linear) cost functions. Under those conditions, a global optimum $$Y$$ maps to a global optimum $$X = YY^T$$ of the SDP. We deduce old and new consequences for SDP relaxations of the generalized eigenvector problem, the trust-region subproblem, and quadratic optimization over several spheres, as well as for the Max-Cut and Orthogonal-Cut SDPs, which are common relaxations in stochastic block modeling and synchronization of rotations.

##### MSC:
 90C22 Semidefinite programming 90C26 Nonconvex programming, global optimization
Full Text: