×

Low-rank optimization on the cone of positive semidefinite matrices. (English) Zbl 1215.65108

The authors propose an algorithm for solving nonlinear, and often convex, optimization problems defined on a subset of the cone of symmetric positive semidefinite matrices and that are expected to present a low-rank solution. The proposed algorithm rests on the factorization \(X=YY^T\), where the number of columns of \(Y\) fixes an upper bound on the rank of the positive semidefinite matrix \(X\), and solves a sequence of nonconvex programs of much lower dimension than the original one. It presents a monotone convergence toward the sought solution, uses quadratic second-order optimization methods, and provides a tool to monitor the convergence, which enables evaluation of the quality of approximate solutions for the original problem. Namely, the factorization \(X=YY^T\) leads to a reformulation of the original problem as an optimization on a particular quotient manifold.
The authors discuss the geometry of that manifold and derive a second-order optimization method with guaranteed quadratic convergence. The efficiency of this approach is illustrated on several applications, involving convex as well as nonconvex objective functions: the maximal cut of a graph and three problems in the context of sparse principal component analysis.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C25 Convex programming
90C22 Semidefinite programming
90C27 Combinatorial optimization
62H25 Factor analysis and principal components; correspondence analysis
90C26 Nonconvex programming, global optimization

Software:

DSPCA; SDPLR
PDFBibTeX XMLCite
Full Text: DOI arXiv