SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints

DOI10.1007/S12532-015-0082-6zbMath1321.90085arXiv1406.0942OpenAlexW1861508522MaRDI QIDQ499161

Liuqin Yang, Defeng Sun, Kim-Chuan Toh

Publication date: 30 September 2015

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.0942

zbMATH Keywords

semidefinite programmingdegeneracyaugmented Lagrangiansemismooth Newton-CG method

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Iterative numerical methods for linear systems (65F10)

Related Items (83)

Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ 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 ⋮ Augmented Lagrangian methods for convex matrix optimization problems ⋮ Composite Difference-Max Programs for Modern Statistical Estimation Problems ⋮ A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations ⋮ A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization ⋮ Spectral operators of matrices ⋮ Quadratic Growth Conditions for Convex Matrix Optimization Problems Associated with Spectral Functions ⋮ Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis ⋮ An exact algorithm for semi-supervised minimum sum-of-squares clustering ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ Strong Variational Sufficiency for Nonlinear Semidefinite Programming and Its Implications ⋮ An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs ⋮ A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP ⋮ SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ A semismooth Newton based dual proximal point algorithm for maximum eigenvalue problem ⋮ A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming ⋮ A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees ⋮ Solving graph equipartition SDPs on an algebraic variety ⋮ Unnamed Item ⋮ A primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming ⋮ A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring ⋮ Approximation of the Shannon capacity via matrix cone programming ⋮ Ellipsoidal classification via semidefinite 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 ⋮ Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method ⋮ Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming ⋮ Clustering subgaussian mixtures by semidefinite programming ⋮ A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems ⋮ A matrix nonconvex relaxation approach to unconstrained binary polynomial programs ⋮ An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming ⋮ DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ⋮ An efficient augmented Lagrangian method for support vector machine ⋮ On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming ⋮ A multilevel analysis of the Lasserre hierarchy ⋮ The Linear and Asymptotically Superlinear Convergence Rates of the Augmented Lagrangian Method with a Practical Relative Error Criterion ⋮ A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond ⋮ ADMM for the SDP relaxation of the QAP ⋮ QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming ⋮ Memory-Efficient Structured Convex Optimization via Extreme Point Sampling ⋮ A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming ⋮ A robust Lagrangian-DNN method for a class of quadratic optimization problems ⋮ Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems ⋮ On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems ⋮ 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 ⋮ IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming ⋮ Convex Relaxation Approaches for Strictly Correlated Density Functional Theory ⋮ A proximal DC approach for quadratic assignment problem ⋮ A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions ⋮ Best Nonnegative Rank-One Approximations of Tensors ⋮ When do birds of a feather flock together? \(k\)-means, proximity, and conic programming ⋮ An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming ⋮ Algorithm 996 ⋮ Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold ⋮ Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs ⋮ Tensor theta norms and low rank recovery ⋮ Spectral Operators of Matrices: Semismoothness and Characterizations of the Generalized Jacobian ⋮ On the Nonergodic Convergence Rate of an Inexact Augmented Lagrangian Framework for Composite Convex Programming ⋮ SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0) ⋮ \(\mathrm{B}\)-subdifferentials of the projection onto the matrix simplex ⋮ SDPNAL+ ⋮ Accuracy of approximate projection to the semidefinite cone ⋮ Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms ⋮ Unnamed Item ⋮ Computing the Best Approximation over the Intersection of a Polyhedral Set and the Doubly Nonnegative Cone ⋮ An Efficient Quadratic Programming Relaxation Based Algorithm for Large-Scale MIMO Detection ⋮ Covariate Regularized Community Detection in Sparse Graphs ⋮ A Newton-bracketing method for a simple conic optimization problem ⋮ An ADMM-based interior-point method for large-scale linear programming ⋮ Scalable Semidefinite Programming ⋮ On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming ⋮ Unified convergence analysis of a second-order method of multipliers for nonlinear conic programming ⋮ A Convex Matrix Optimization for the Additive Constant Problem in Multidimensional Scaling with Application to Locally Linear Embedding ⋮ A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems ⋮ On Degenerate Doubly Nonnegative Projection Problems ⋮ Exact SDP relaxations of quadratically constrained quadratic programs with forest structures ⋮ B-subdifferential of the projection onto the generalized spectraplex

Uses Software

• Unnamed Item
• DIMACS
• 2EBD-HPE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
• Convex analysis and nonlinear optimization. Theory and examples.
• Copositive and semidefinite relaxations of the quadratic assignment problem
• A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
• A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
• 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
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Monotone Operators and the Proximal Point Algorithm
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
• Frequency planning and ramifications of coloring
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• Approximating K‐means‐type Clustering via Semidefinite Programming
• ON MATRICES DEPENDING ON PARAMETERS
• Semismooth Matrix-Valued Functions
• Semismooth Homeomorphisms and Strong Stability of Semidefinite and Lorentz Complementarity Problems
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent

This page was built for publication: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints