A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
From MaRDI portal
Abstract: We develop a decomposition method based on the augmented Lagrangian framework to solve a broad family of semidefinite programming problems, possibly with nonlinear objective functions, nonsmooth regularization, and general linear equality/inequality constraints. In particular, the positive semidefinite variable along with a group of linear constraints can be transformed into a variable on a smooth manifold via matrix factorization. The nonsmooth regularization and other general linear constraints are handled by the augmented Lagrangian method. Therefore, each subproblem can be solved by a semismooth Newton method on a manifold. Theoretically, we show that the first and second-order necessary optimality conditions for the factorized subproblem are also sufficient for the original subproblem under certain conditions. Convergence analysis is established for the Riemannian subproblem and the augmented Lagrangian method. Extensive numerical experiments on large-scale semidefinite programming problems such as max-cut, nearest correlation estimation, clustering, and sparse principal component analysis demonstrate the strength of our proposed method compared to other state-of-the-art methods.
Recommendations
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Using a factored dual in augmented Lagrangian methods for semidefinite programming
- Alternating direction augmented Lagrangian methods for semidefinite programming
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Regularization methods for semidefinite programming
Cites work
- scientific article; zbMATH DE number 3173999 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Adaptive quadratically regularized Newton method for Riemannian optimization
- Adaptive regularization with cubics on manifolds
- An Extrinsic Look at the Riemannian Hessian
- An inexact interior point method for \(L_{1}\)-regularized sparse covariance selection
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Benchmarking optimization software with performance profiles.
- BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
- Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- Global rates of convergence for nonconvex optimization on manifolds
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Handbook on semidefinite, conic and polynomial optimization
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Low-rank optimization on the cone of positive semidefinite matrices
- On the Shannon capacity of a graph
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Possible generalization of Boltzmann-Gibbs statistics.
- Practical augmented Lagrangian methods for constrained optimization
- Problems of distance geometry and convex properties of quadratic maps
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Semismooth Matrix-Valued Functions
- Sparse PCA: convex relaxations, algorithms and applications
Cited in
(15)- Solving low-rank semidefinite programs via manifold optimization
- A feasible method for general convex low-rank SDP problems
- Computational enhancements in low-rank semidefinite programming
- Low-rank optimization on the cone of positive semidefinite matrices
- Scalable low-rank semidefinite programming for certifiably correct machine perception
- An augmented Lagrangian decomposition method for block diagonal linear programming problems
- Using a factored dual in augmented Lagrangian methods for semidefinite programming
- Global convergence of an augmented Lagrangian method for nonlinear programming via Riemannian optimization
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Optimal neural network approximation of Wasserstein gradient direction via convex optimization
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- Instance-specific linear relaxations of semidefinite optimization problems
- Block coordinate descent methods for semidefinite programming
This page was built for publication: A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116234)
