SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
From MaRDI portal
(Redirected from Publication:499161)
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.
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
Cites work
- scientific article; zbMATH DE number 3177945 (Why is no real title available?)
- scientific article; zbMATH DE number 3465097 (Why is no real title available?)
- scientific article; zbMATH DE number 1502618 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
- A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
- A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Convex analysis and nonlinear optimization. Theory and examples.
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Frequency planning and ramifications of coloring
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- Monotone Operators and the Proximal Point Algorithm
- ON MATRICES DEPENDING ON PARAMETERS
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Semidefinite relaxations for best rank-1 tensor approximations
- Semismooth Homeomorphisms and Strong Stability of Semidefinite and Lorentz Complementarity Problems
- Semismooth Matrix-Valued Functions
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
Cited in
(94)- A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Unified convergence analysis of a second-order method of multipliers for nonlinear conic programming
- Spectral operators of matrices
- Composite difference-MAX programs for modern statistical estimation problems
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
- 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
- Certifying the global optimality of quartic minimization over the sphere
- A primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming
- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- B-subdifferential of the projection onto the generalized spectraplex
- Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian
- A novel approach for solving semidefinite programs
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
- A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
- scientific article; zbMATH DE number 7370526 (Why is no real title available?)
- Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
- A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations
- Scalable semidefinite programming
- Strong Variational Sufficiency for Nonlinear Semidefinite Programming and Its Implications
- Convex relaxation approaches for strictly correlated density functional theory
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- \(\mathrm{B}\)-subdifferentials of the projection onto the matrix simplex
- A proximal DC approach for quadratic assignment problem
- Ellipsoidal classification via semidefinite programming
- SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Clustering subgaussian mixtures by semidefinite programming
- ADMM for the SDP relaxation of the QAP
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Best nonnegative rank-one approximations of tensors
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
- SDPNAL+
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems
- Proximal gradient method for nonsmooth optimization over the Stiefel manifold
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
- Tensor theta norms and low rank recovery
- Augmented Lagrangian methods for convex matrix optimization problems
- An efficient quadratic programming relaxation based algorithm for large-scale MIMO detection
- Accuracy of approximate projection to the semidefinite cone
- A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds
- An ADMM-based interior-point method for large-scale linear programming
- A robust Lagrangian-DNN method for a class of quadratic optimization problems
- A multilevel analysis of the Lasserre hierarchy
- An exact algorithm for semi-supervised minimum sum-of-squares clustering
- A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming
- Covariate regularized community detection in sparse graphs
- An efficient augmented Lagrangian method for support vector machine
- On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems
- Quadratic growth conditions for convex matrix optimization problems associated with spectral functions
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- A Newton-bracketing method for a simple conic optimization problem
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- An efficient inexact ABCD method for least squares semidefinite programming
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- Algorithm 996
- The linear and asymptotically superlinear convergence rates of the augmented Lagrangian method with a practical relative error criterion
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- A convex matrix optimization for the additive constant problem in multidimensional scaling with application to locally linear embedding
- On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming
- 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
- Approximation of the Shannon capacity via matrix cone programming
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming
- A new homotopy proximal variable-metric framework for composite convex minimization
- 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 Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
- Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming
- A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
- Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- On degenerate doubly nonnegative projection problems
- Memory-efficient structured convex optimization via extreme point sampling
- Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
- A semismooth Newton based dual proximal point algorithm for maximum eigenvalue problem
- Optimal neural network approximation of Wasserstein gradient direction via convex optimization
- Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone
- Solving graph equipartition SDPs on an algebraic variety
- Semi-definite programming and quantum information
- Loraine – an interior-point solver for low-rank semidefinite programming
- Optimization models and approaches for strongly correlated electrons systems
- A feasible method for general convex low-rank SDP problems
- A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
- Averaging orientations with molecular symmetry in cryo-EM
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)
