A hierarchy of spectral relaxations for polynomial optimization
From MaRDI portal
Publication:6062883
Abstract: We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods that minimize the largest eigenvalue of a matrix pencil. Convergence to the optimal value of the semidefinite relaxation is guaranteed. As a result we obtain a hierarchy of nonsmooth "spectral relaxations" of the initial POP. Efficiency and robustness of this spectral hierarchy is tested against several equality constrained POPs on a sphere as well as on a sample of randomly generated quadratically constrained quadratic problems (QCQPs).
Recommendations
- A bounded degree SOS hierarchy for polynomial optimization
- A new hierarchy of SDP-relaxations for polynomial programming
- A new approximation hierarchy for polynomial conic optimization
- Lagrangian-conic relaxations. II: Applications to polynomial optimization problems
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
Cites work
- A bounded degree SOS hierarchy for polynomial optimization
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A Positivstellensatz for sums of nonnegative circuit polynomials
- A quasi-Newton algorithm for nonconvex, nonsmooth optimization with global convergence guarantees
- A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
- A second order cone characterization for sums of nonnegative circuits
- A Spectral Bundle Method for Semidefinite Programming
- A Stochastic Smoothing Algorithm for Semidefinite Programming
- An Algorithm for Constrained Optimization with Semismooth Functions
- An introduction to polynomial and semi-algebraic optimization
- An optimal-storage approach to semidefinite programming using approximate complementarity
- ARPACK Users' Guide
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Convergence of the Gradient Sampling Algorithm for Nonsmooth Nonconvex Optimization
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Global optimization with polynomials and the problem of moments
- Globally convergent limited memory bundle method for large-scale nonsmooth optimization
- scientific article; zbMATH DE number 4070633 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Introduction to nonsmooth optimization. Theory, practice and software
- Large-Scale Optimization of Eigenvalues
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Low-rank optimization on the cone of positive semidefinite matrices
- Moments, positive polynomials and their applications
- New limited memory bundle method for large-scale nonsmooth optimization
- Nonsmooth optimization via quasi-Newton methods
- Numerical methods for large eigenvalue problems
- On the complexity of Putinar's Positivstellensatz
- On the complexity of Schmüdgen's Positivstellensatz
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Optimization of upper semidifferentiable functions
- Projection Methods in Conic Optimization
- Proximity control in bundle methods for convex nondifferentiable minimization
- Relative entropy relaxations for signomial optimization
- Revisiting two theorems of Curto and Fialkow on moment matrices
- Scalable semidefinite programming
- Second Derivatives for Optimizing Eigenvalues of Symmetric Matrices
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Strong duality conditions in semidefinite programming
- Strong duality in lasserre's hierarchy for polynomial optimization
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- The spectral bundle method with second-order information
- Truncated \(K\)-moment problems in several variables
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- Updating Quasi-Newton Matrices with Limited Storage
Cited in
(12)- Connecting optimization with spectral analysis of tri-diagonal matrices
- Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
- A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
- On the strength of recursive McCormick relaxations for binary polynomial optimization
- Harmonic Hierarchies for Polynomial Optimization
- The moment-SOS hierarchy: applications and related topics
- Towards global solutions for nonconvex two-stage stochastic programs: a polynomial lower approximation approach
- An overview and comparison of spectral bundle methods for primal and dual semidefinite programs
- Spectral methods for polynomial optimization
- Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant
- Term-sparse polynomial optimization for the design of frame structures
- Border basis relaxation for polynomial optimization
This page was built for publication: A hierarchy of spectral relaxations for polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6062883)
