Journée, M.; Bach, F.; Absil, P.-A.; Sepulchre, R. Low-rank optimization on the cone of positive semidefinite matrices. (English) Zbl 1215.65108 SIAM J. Optim. 20, No. 5, 2327-2351 (2010). 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. Reviewer: Nada Djuranović-Miličić (Belgrade) Cited in 49 Documents 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 Keywords:low-rank constraints; cone of symmetric positive definite matrices; Riemannian quotient manifold; sparse principal component analysis; maximum-cut algorithms; large-scale algorithms; nonconvex programs; convergence Software:DSPCA; SDPLR PDFBibTeX XMLCite \textit{M. Journée} et al., SIAM J. Optim. 20, No. 5, 2327--2351 (2010; Zbl 1215.65108) Full Text: DOI arXiv