QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
From MaRDI portal
Abstract: In this paper, we present a two-phase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality, inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNAL-Phase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNAL-Phase II, we design an augmented Lagrangian method (ALM) where the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R-(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our two-phase algorithm is highly efficient and robust in obtaining accurate solutions.
Recommendations
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- A Newton-CG Augmented Lagrangian Method for Convex Quadratically Constrained Quadratic Semidefinite Programs
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- An augmented Lagrangian iteration method for convex quadratic SDP
- Alternating direction augmented Lagrangian methods for semidefinite programming
Cites work
- scientific article; zbMATH DE number 3465097 (Why is no real title available?)
- scientific article; zbMATH DE number 1502618 (Why is no real title available?)
- scientific article; zbMATH DE number 5239114 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
- A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs
- A partial proximal point algorithm for nuclear norm regularized matrix least squares problems
- A predictor--corrector algorithm for QSDP combining Dikin-type and Newton centering steps
- An efficient inexact ABCD method for least squares semidefinite programming
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
- An inexact interior point method for \(L_{1}\)-regularized sparse covariance selection
- An inexact primal-dual path following algorithm for convex quadratic SDP
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Computing the nearest correlation matrix--a problem from finance
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
- Local Duality of Nonlinear Semidefinite Programming
- Monotone Operators and the Proximal Point Algorithm
- Optimization and nonsmooth analysis
- QAPLIB - a quadratic assignment problem library
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Semismooth Homeomorphisms and Strong Stability of Semidefinite and Lorentz Complementarity Problems
- Semismooth Matrix-Valued Functions
- Solving Euclidean distance matrix completion problems via semidefinite progrmming
- Strong conical hull intersection property, bounded linear regularity, Jameson's property \((G)\), and error bounds in convex optimization
Cited in
(36)- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
- On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
- Strong Variational Sufficiency for Nonlinear Semidefinite Programming and Its Implications
- A Riemannian dimension-reduced second-order method with application in sensor network localization
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- A feasible method for general convex low-rank SDP problems
- Finding the global optimum of a class of quartic minimization problem
- B-subdifferential of the projection onto the generalized spectraplex
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- The linear and asymptotically superlinear convergence rates of the augmented Lagrangian method with a practical relative error criterion
- On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming
- An inexact augmented Lagrangian method for second-order cone programming with applications
- Sparse estimation of high-dimensional inverse covariance matrices with explicit eigenvalue constraints
- A multi-level ADMM algorithm for elliptic PDE-constrained optimization problems
- Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming
- QSDPNAL
- Quadratic growth conditions for convex matrix optimization problems associated with spectral functions
- Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian
- On degenerate doubly nonnegative projection problems
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- \(\mathrm{B}\)-subdifferentials of the projection onto the matrix simplex
- scientific article; zbMATH DE number 7370538 (Why is no real title available?)
- An iDCA with sieving strategy for PDE-constrained optimization problems with \(L^{1-2}\)-control cost
- On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- Augmented Lagrangian methods for convex matrix optimization problems
- A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems
- A Euclidean distance matrix model for protein molecular conformation
- Polynomial norms
- A Newton-CG Augmented Lagrangian Method for Convex Quadratically Constrained Quadratic Semidefinite Programs
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- A semidefinite programming approach for the projection onto the cone of negative semidefinite symmetric tensors with applications to solid mechanics
- QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
- Synthesizing invariant barrier certificates via difference-of-convex programming
- A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems
This page was built for publication: QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741120)
