An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization

DOI10.1007/S10107-022-01912-6zbMath1522.90033arXiv2105.14033MaRDI QIDQ6165592

Heng Yang, Kim-Chuan Toh, Ling Liang, Luca Carlone

Publication date: 1 August 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingnonlinear programmingdegeneracypolynomial optimizationinexact projected gradient methodrank-one solutions

Mathematics Subject Classification ID

Semidefinite programming (90C22) Large-scale problems in mathematical programming (90C06) Methods of successive quadratic programming type (90C55) Polynomial optimization (90C23)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the nearest correlation matrix--a problem from finance
• Overview of total least-squares methods
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Optimality conditions and finite convergence of Lasserre's hierarchy
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
• Lectures on convex optimization
• Semidefinite representations for finite varieties
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Dual quadratic estimates in polynomial and Boolean programming
• Complementarity and nondegeneracy in semidefinite programming
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Semidefinite programming relaxations for semialgebraic problems
• A semidefinite programming approach to the quadratic knapsack problem
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• On the tightness of SDP relaxations of QCQPs
• On the local stability of semidefinite relaxations
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• The sum-of-squares hierarchy on the sphere and applications in quantum information theory
• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming
• Software for weighted structured low-rank approximation
• A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
• Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices
• Structured low-rank approximation and its applications
• Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
• Global Optimization with Polynomials and the Problem of Moments
• Projection Methods in Conic Optimization
• Polynomial Optimization with Real Varieties
• Proximal Splitting Methods in Signal Processing
• Manopt, a Matlab toolbox for optimization on manifolds
• Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
• Exact Recovery in the Stochastic Block Model
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Projection methods for conic feasibility problems: applications to polynomial sum-of-squares decompositions
• Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception
• A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
• Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
• Monotone Operators and the Proximal Point Algorithm
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• A Dual Approach to Semidefinite Least-Squares Problems
• Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
• Total Least Norm Formulation and Solution for Structured Problems
• An Inexact Accelerated Proximal Gradient Method for Large Scale Linearly Constrained Convex SDP
• Semidefinite Optimization and Convex Algebraic Geometry
• A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property
• A Convex Relaxation to Compute the Nearest Structured Rank Deficient Matrix
• Scalable Semidefinite Programming
• Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
• Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
• Regularization Methods for Semidefinite Programming
• Optimal Linear Quadratic Regulator of Switched Systems
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• Hypercontractivity, sum-of-squares proofs, and their applications
• GloptiPoly
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Phase Retrieval via Matrix Completion
• Benchmarking optimization software with performance profiles.
• Strong duality in lasserre's hierarchy for polynomial optimization

This page was built for publication: An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization