SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
From MaRDI portal
Publication:499161
DOI10.1007/S12532-015-0082-6zbMATH Open1321.90085arXiv1406.0942OpenAlexW1861508522MaRDI QIDQ499161FDOQ499161
Authors: Liuqin Yang, Defeng Sun, Kim-Chuan Toh 
Publication date: 30 September 2015
Published in: Mathematical Programming Computation (Search for Journal in Brave)
Abstract: In this paper, we present a majorized semismooth Newton-CG augmented Lagrangian method, called SDPNAL, for semidefinite programming (SDP) with partial or full nonnegative constraints on the matrix variable. SDPNAL is a much enhanced version of SDPNAL introduced by Zhao, Sun and Toh [SIAM Journal on Optimization, 20 (2010), pp.~1737--1765] for solving generic SDPs. SDPNAL works very efficiently for nondegenerate SDPs but may encounter numerical difficulty for degenerate ones. Here we tackle this numerical difficulty by employing a majorized semismooth Newton-CG augmented Lagrangian method coupled with a convergent 3-block alternating direction method of multipliers introduced recently by Sun, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)]. Numerical results for various large scale SDPs with or without nonnegative constraints show that the proposed method is not only fast but also robust in obtaining accurate solutions. It outperforms, by a significant margin, two other competitive publicly available first order methods based codes: (1) an alternating direction method of multipliers based solver called SDPAD by Wen, Goldfarb and Yin [Mathematical Programming Computation, 2 (2010), pp.~203--230] and (2) a two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE by Monteiro, Ortiz and Svaiter [Mathematical Programming Computation, (2013), pp.~1--48]. In contrast to these two codes, we are able to solve all the 95 difficult SDP problems arising from the relaxations of quadratic assignment problems tested in SDPNAL to an accuracy of efficiently, while SDPAD and 2EBD-HPE successfully solve 30 and 16 problems, respectively.
Full work available at URL: https://arxiv.org/abs/1406.0942
Recommendations
- A Newton-CG augmented Lagrangian method for semidefinite programming
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Alternating direction augmented Lagrangian methods for semidefinite programming
- First- and second-order methods for semidefinite programming
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Iterative numerical methods for linear systems (65F10)
Cites Work
- A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- Title not available (Why is that?)
- Title not available (Why is that?)
- Monotone Operators and the Proximal Point Algorithm
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Title not available (Why is that?)
- On the copositive representation of binary and continuous nonconvex quadratic programs
- ON MATRICES DEPENDING ON PARAMETERS
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Copositive and semidefinite relaxations of the quadratic assignment problem
- A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
- Convex analysis and nonlinear optimization. Theory and examples.
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- Semidefinite relaxations for best rank-1 tensor approximations
- Frequency planning and ramifications of coloring
- Semismooth Matrix-Valued Functions
- Semismooth Homeomorphisms and Strong Stability of Semidefinite and Lorentz Complementarity Problems
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Approximating K‐means‐type Clustering via Semidefinite Programming
Cited In (94)
- A novel approach for solving semidefinite programs
- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
- Strong Variational Sufficiency for Nonlinear Semidefinite Programming and Its Implications
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
- A Newton-CG augmented Lagrangian method for semidefinite programming
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
- Alternating direction augmented Lagrangian methods for semidefinite programming
- A multilevel analysis of the Lasserre hierarchy
- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- B-subdifferential of the projection onto the generalized spectraplex
- Ellipsoidal classification via semidefinite programming
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- Unified convergence analysis of a second-order method of multipliers for nonlinear conic programming
- Composite difference-MAX programs for modern statistical estimation problems
- Covariate regularized community detection in sparse graphs
- On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems
- The linear and asymptotically superlinear convergence rates of the augmented Lagrangian method with a practical relative error criterion
- Spectral operators of matrices
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- Tensor theta norms and low rank recovery
- On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming
- A convex matrix optimization for the additive constant problem in multidimensional scaling with application to locally linear embedding
- A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming
- Title not available (Why is that?)
- Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems
- On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
- An efficient inexact ABCD method for least squares semidefinite programming
- A globally convergent method for solving a quartic generalized Markowitz portfolio problem
- Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
- A proximal DC approach for quadratic assignment problem
- Convex relaxation approaches for strictly correlated density functional theory
- A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds
- Quadratic growth conditions for convex matrix optimization problems associated with spectral functions
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- An efficient augmented Lagrangian method for support vector machine
- Algorithm 996
- Certifying the global optimality of quartic minimization over the sphere
- SDPNAL+
- An ADMM-based interior-point method for large-scale linear programming
- \(\mathrm{B}\)-subdifferentials of the projection onto the matrix simplex
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- Clustering subgaussian mixtures by semidefinite programming
- An exact algorithm for semi-supervised minimum sum-of-squares clustering
- Proximal gradient method for nonsmooth optimization over the Stiefel manifold
- Augmented Lagrangian methods for convex matrix optimization problems
- A Newton-bracketing method for a simple conic optimization problem
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- Best nonnegative rank-one approximations of tensors
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
- Scalable semidefinite programming
- Accuracy of approximate projection to the semidefinite cone
- ADMM for the SDP relaxation of the QAP
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- An efficient quadratic programming relaxation based algorithm for large-scale MIMO detection
- A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems
- A primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming
- A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- A robust Lagrangian-DNN method for a class of quadratic optimization problems
- Semi-definite programming and quantum information
- A feasible method for general convex low-rank SDP problems
- A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
- Approximation of the Shannon capacity via matrix cone programming
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- A DCA-Newton method for quartic minimization over the sphere
- A new homotopy proximal variable-metric framework for composite convex minimization
- Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
- Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone
- Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming
- On degenerate doubly nonnegative projection problems
- Optimal neural network approximation of Wasserstein gradient direction via convex optimization
- A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
- A semismooth Newton stochastic proximal point algorithm with variance reduction
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
- A semismooth Newton based dual proximal point algorithm for maximum eigenvalue problem
- IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming
- Loraine – an interior-point solver for low-rank semidefinite programming
- Optimization models and approaches for strongly correlated electrons systems
- Averaging orientations with molecular symmetry in cryo-EM
- Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- Memory-efficient structured convex optimization via extreme point sampling
- Solving graph equipartition SDPs on an algebraic variety
- A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
Uses Software
This page was built for publication: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499161)
