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-6MaRDI QIDQ6165592zbMATH OpenFDO

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

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

degeneracyinexact projected gradient methodnonlinear programmingpolynomial optimizationrank-one solutionssemidefinite programming

Mathematics Subject Classification ID

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

Abstract: We consider solving high-order semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss-Seidel based accelerated proximal gradient method (sGS-APG) to generate a good initial point, and phase two using a modified limited-memory BFGS (L-BFGS) method to obtain an accurate solution. We analyze the convergence for both phases and establish a novel global convergence result for the modified L-BFGS that does not require the objective function to be twice continuously differentiable. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate rank-one SDPs to high accuracy, even in the presence of millions of equality constraints.

Recommendations

• EQUALITY BASED CONTRACTION OF SEMIDEFINITE PROGRAMMING RELAXATIONS IN POLYNOMIAL OPTIMIZATION
• Solving a class of semidefinite programs via nonlinear programming
• A projected gradient algorithm for solving the maxcut SDP relaxation
• An exact Jacobian SDP relaxation for polynomial optimization
• A convergent hierarchy of SDP relaxations for a class of hard robust global polynomial optimization problems

Cites work

• A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
• A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
• A convex relaxation to compute the nearest structured rank deficient matrix
• A Dual Approach to Semidefinite Least-Squares Problems
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Newton-CG augmented Lagrangian method for semidefinite programming
• A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
• A semidefinite programming approach to the quadratic knapsack problem
• 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
• Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Benchmarking optimization software with performance profiles.
• Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices
• Complementarity and nondegeneracy in semidefinite programming
• Computing the nearest correlation matrix--a problem from finance
• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Dual quadratic estimates in polynomial and Boolean programming
• Exact Recovery in the Stochastic Block Model
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Global optimization with polynomials and the problem of moments
• GloptiPoly
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 5504153 (Why is no real title available?)
• scientific article; zbMATH DE number 3465097 (Why is no real title available?)
• scientific article; zbMATH DE number 1757962 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Hypercontractivity, sum-of-squares proofs, and their applications
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lectures on convex optimization
• Manopt, a Matlab toolbox for optimization on manifolds
• Monotone Operators and the Proximal Point Algorithm
• On the local stability of semidefinite relaxations
• On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming
• On the tightness of SDP relaxations of QCQPs
• Optimal Linear Quadratic Regulator of Switched Systems
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Overview of total least-squares methods
• Phase retrieval via matrix completion
• Polynomial optimization with real varieties
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Projection methods for conic feasibility problems: applications to polynomial sum-of-squares decompositions
• Projection Methods in Conic Optimization
• Proximal splitting methods in signal processing
• Regularization methods for semidefinite programming
• Scalable low-rank semidefinite programming for certifiably correct machine perception
• Scalable semidefinite programming
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite programming relaxations for semialgebraic problems
• Semidefinite representations for finite varieties
• Software for weighted structured low-rank approximation
• Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• Strong duality in lasserre's hierarchy for polynomial optimization
• Structured low-rank approximation and its applications
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• The sum-of-squares hierarchy on the sphere and applications in quantum information theory
• Total Least Norm Formulation and Solution for Structured Problems
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity

Cited in

(4)

• Accelerated first-order methods for a class of semidefinite programs
• Nesterov's accelerated Jacobi-type methods for large-scale symmetric positive semidefinite linear systems
• Instance-specific linear relaxations of semidefinite optimization problems
• Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165592)