Source-linked AI summary
Low-rank optimization for semidefinite convex problems
M. Journée, F. Bach, P. -A. Absil, R. Sepulchre
TL;DR
The paper addresses large convex semidefinite programs whose solutions may be low rank, using the factorization X = Y Y^T to reduce dimensionality. It develops quotient-manifold second-order optimization with rank conditions for equivalence to the original problem, and demonstrates the approach on maximal cut and sparse PCA. The method provides monotone convergence and convergence monitoring, while rank-one recovery remains a scope boundary of the convex relaxations.
Problem
Large convex semidefinite relaxations can require optimization over high-dimensional positive semidefinite matrices, motivating methods that exploit low-rank solutions.
Method
The paper factorizes X = Y Y^T, optimizes over the associated quotient manifold using second-order methods, and increases p until conditions certify equivalence with the original problem.
Results
The proposed algorithm achieves monotone convergence with superlinear second-order methods and is illustrated on maximal cut and sparse principal component analysis.
Takeaways & Limitations
The approach offers lower-dimensional optimization for large semidefinite problems with low-rank solutions and includes an indicator for controlling approximate-solution accuracy.
Takeaways & Limitations
The convex sparse-PCA relaxations drop the rank-one condition, so their solutions are expected to have rank larger than one; very small smoothing parameters can also make Hessians ill-conditioned.
Abstract
from arXiv · showhide
We propose an algorithm for solving nonlinear convex programs defined in terms of a symmetric positive semidefinite matrix variable $X$. This algorithm rests on the factorization $X=Y Y^T$, where the number of columns of Y fixes the rank of $X$. It is thus very effective for solving programs that have a low rank solution. The factorization $X=Y Y^T$ evokes a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second order optimization method. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. The efficiency of the proposed algorithm is illustrated on two applications: the maximal cut of a graph and the sparse principal component analysis problem.
1 Introduction
The paper targets large convex semidefinite programs whose solutions are low rank, replacing the matrix variable with a lower-dimensional factor and optimizing over the resulting quotient space. It develops second-order methods and rank-based conditions to recover solutions of the original problem.
- Motivation: Large convex relaxations often optimize over symmetric positive semidefinite matrices, making computation demanding despite their usefulness for bounds and approximate solutions.When the relaxation is tight at rank one, low-rank structure can make direct solution more feasible.
- Factorized formulation: The method factorizes X as Y Y^T, fixing the represented rank through the number of columns p and reducing the search space to dimension np.The resulting optimization problem is nonlinear rather than convex.
- Quotient geometry: Orthogonal right multiplication leaves solutions equivalent, so the algorithm works conceptually on quotient classes where minimizers are isolated.This symmetry is especially important for second-order methods, whose convergence can be affected by nonisolated Euclidean solutions.
- Rank selection and algorithm: The algorithm increments the factorization rank p until a sufficient condition indicates that Y Y^T solves the original convex program, despite the unknown solution rank.It combines monotone convergence, superlinear second-order methods, and an accuracy-control convergence indicator.
- Scope and contributions: The paper builds equivalence conditions, derives quotient-manifold geometry, and applies the resulting approach to maximal cut and sparse principal component analysis.Earlier factorization work used gradient methods, whereas this paper exploits equality-constraint structure for second-order descent with guaranteed superlinear convergence.
2 Notations
The notation lifts a function on symmetric matrices to a function on factor matrices by evaluating it at Y Y^T, while defining derivatives with respect to X.
- Function lifting: For f: S^n → R, the lifted function is defined by tilde f(Y) = f(Y Y^T).This expresses the factorized objective in terms of the matrix product generated by Y.
- Derivatives: The operator ∇ denotes the first-order derivative, with ∇_X f(X_0) representing the gradient with respect to X at X_0.The notation also introduces directional derivatives of f with respect to X.
- Derivatives: The paper assumes f is differentiable when defining the gradient matrix B elementwise.B is the gradient of f with respect to X evaluated at X_0.
3 Optimality conditions
The paper compares optimality conditions for the convex matrix program and its lower-dimensional factorized nonconvex reformulation, deriving criteria for when a local factor minimizer is globally valid for the original problem. These criteria underpin an increasing-rank algorithm with monotone descent and second-order inner optimization.
- 3.1 First-order optimality conditions: Theoretical optimality conditions relate local minimizers of the factorized program to solutions of the original convex program.The comparison shows that all but one condition for the convex formulation are inherited by YY^T from a local factor minimizer.
- 3.1 First-order optimality conditions: A local minimizer Y provides the convex solution YY^T if and only if the associated matrix is positive semidefinite for multipliers satisfying the factorized first-order conditions.This is the criterion stated by Theorem 3.
- 3.2 Second-order optimality conditions: A rank-deficient local minimizer Y automatically provides the convex solution YY^T.The result follows from second-order conditions and the factorization of Y into a rank-r component and a full-rank matrix.
- 3.2 Second-order optimality conditions: When p = n, every local minimizer of the factorized program provides a solution of the original convex program.If Y is rank deficient, Theorem 6 applies; otherwise the associated dual matrix is zero.
- 3.3 An algorithm to solve the convex problem: The meta-algorithm solves successive factorized problems with increasing p, appending a zero column to preserve monotone descent and using a smallest-eigenvalue direction when needed.The eigenvalue threshold ε tests the relevant matrix condition; the implementation sets ε to 10^-12.
- 3.3 An algorithm to solve the convex problem: The algorithm can stop at p = n at latest, often at a lower rank, while |λmin| monitors proximity to the convex KKT conditions and ε controls accuracy.The rank condition is cheaper to evaluate than the nonnegativity condition but does not provide a saddle-point escape direction and requires p > r.
4 Manifold-based optimization
The paper reformulates the factorized optimization problem on a quotient manifold that removes orthogonal right-multiplication symmetry, then applies manifold-based second-order optimization.
- Quotient-manifold formulation: The quotient manifold represents equivalence classes of feasible factors Y under right multiplication by orthogonal matrices.This accounts for the invariance of the factorized problem and makes minimizers isolated in the quotient space.
- Manifold geometry: The tangent space is decomposed into vertical directions along equivalence classes and a horizontal space used for optimization.The horizontal space is the orthogonal complement of the vertical space within the tangent space.
- Second-order optimization: The trust-region method projects Euclidean directions onto the horizontal space using a closed-form projection determined by a Sylvester equation and linear constraints.The projection removes components in the vertical and normal spaces.
- Second-order optimization: Gradients and Hessian actions on the quotient manifold are obtained from Euclidean derivatives through horizontal-space projection.The Euclidean objective is defined by f̃(Y) = f(Y Y^T).
- Manifold geometry: A retraction maps horizontal search directions back to the feasible manifold by projecting Y + Z along the normal space.Under the stated assumption, the coefficients enforcing feasibility are computed from a quadratic polynomial.
- Computational cost: Manifold-related operations have linear complexity in n, while objective, gradient, and directional-derivative evaluations dominate the computational cost.The costly evaluations occur in the Euclidean space R^n×p.
5 Optimization on the elliptope: the max-cut SDP relaxation
The proposed method is applied to the elliptope formulation of the max-cut SDP relaxation, using low-rank factors and quotient-manifold optimization. On tested graphs, the factorization substantially reduces search-space size, while runtime is suggested to be similar to SDPLR despite differing implementations.
- Max-cut formulation: The maximal cut problem partitions graph vertices into two sets maximizing the total weight of crossing edges, and its standard SDP relaxation provides a 0.878-approximation algorithm.The relaxation is tight when the solution has rank one.
- Max-cut formulation: The elliptope satisfies the framework’s structural assumption, so the max-cut SDP can be optimized on the quotient manifold formed from factors with diag(Y Y^T) = 1.The factorization is X = Y Y^T.
- Computational cost: Algorithm 1 has complexity O(n^2p) for the elliptope application, dominated by manifold optimization and eigenvalue decomposition of the dual matrix S_Y.Sparse matrices A can reduce the cost of manifold-based optimization.
- Computational results: The optimizer rank indicates that X = Y Y^T significantly reduces the search-space size on the tested graph instances.Table 1 compares the Matlab implementation of Algorithm 1 with the C implementation of SDPLR.
- Computational results: Both methods perform similarly according to Table 1, although the differing Matlab and C implementations prevent a rigorous computational-load comparison.The comparison is therefore suggestive rather than a controlled runtime benchmark.
- Convergence behavior: For graph toruspm3-15-50, the cost decreases monotonically across iterations and ranks, while the smallest eigenvalue of S_Y increases monotonically toward zero.The magnitude of λ_min provides insight into current solution accuracy.
6 Optimization on the spectahedron: the sparse PCA problem
The sparse PCA section develops low-rank quotient-manifold methods for convex spectahedral relaxations, addressing the combinatorial sparsity constraint and large-scale computation. Experiments examine convergence, complexity, smoothing, rank behavior, and projection to rank-one solutions.
- Problem: Sparse PCA seeks a unit-norm vector maximizing the Rayleigh quotient while imposing sparsity, whose optimal pattern is combinatorial.The data matrix may be dense, including Gaussian matrices in compressed sensing.
- Convex relaxations: The relaxations lift x into a positive semidefinite trace-one matrix X and replace cardinality constraints with convex penalties.The rank-one relation X = xx^T makes the lifting equivalent when the relaxed matrix remains rank one.
- Low-rank optimization: The proposed approach factorizes the matrix as Y Y^T and optimizes on a quotient manifold, with computational complexity O(n^2p) for the first relaxation.The quotient removes the redundancy from right multiplication by orthogonal matrices.
- First relaxation: Algorithm 1 converges monotonically on the smooth relaxation, while the smallest eigenvalue of S_Y monitors convergence and rank-related optimality.For the reported 50 × 50 Gaussian experiment, solutions are expected to be close to rank one, so increasing rank beyond one yields little objective improvement.
- Second relaxation: The sparse PCA relaxation is solved directly as a nonsmooth spectral optimization, with complexity O(nm^2p) and suitability for large-scale data when m ≪ n.The reported experiments state that the proposed method converged successfully despite the absence of a convexity-preserving smoothing method.
- Rank-one recovery: Dropping the rank-one condition means the convex relaxations may return higher-rank matrices, motivating rank-one projection and continuation strategies.A continuation parameter can move solutions from typically higher-rank relaxed solutions toward rank-one extreme points; the proposed projection outperforms eigenvalue-decomposition projection in achieved objective value.
7 Conclusion
The paper proposes a low-rank factorization algorithm that replaces a large convex semidefinite program with lower-dimensional nonconvex programs while retaining convergence guarantees and assessing approximate solutions.
- The algorithm solves a sequence of lower-dimensional nonconvex programs for convex semidefinite problems assumed to have low-rank solutions.It uses monotone convergence and second-order methods with superlinear convergence.
- The approach provides a tool to monitor convergence and evaluate the quality of approximate solutions for the original convex problem.
- Efficiency is illustrated on maximal cut and several sparse principal component analysis problems.
- For nonconvex cost functions, the algorithm converges toward a local optimizer.