A bounded degree SOS hierarchy for polynomial optimization
From MaRDI portal
Publication:2397758
DOI10.1007/S13675-015-0050-YzbMATH Open1368.90132arXiv1501.06126OpenAlexW1822269556MaRDI QIDQ2397758FDOQ2397758
Authors: Kim-Chuan Toh, Shouguang Yang, Jean B. Lasserre 
Publication date: 23 May 2017
Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)
Abstract: We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem on a compact basic semi-algebraic set . This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine's positivity certificate and some advantages of the standard SOS-hierarchy. In particular it has the following attractive features: (a) In contrast to the standard SOS-hierarchy, for each relaxation in the hierarchy, the size of the matrix associated with the semidefinite constraint is the same and fixed in advance by the user. (b) In contrast to the LP-hierarchy, finite convergence occurs at the first step of the hierarchy for an important class of convex problems. Finally (c) some important techniques related to the use of point evaluations for declaring a polynomial to be zero and to the use of rank-one matrices make an efficient implementation possible. Preliminary results on a sample of non convex problems are encouraging.
Full work available at URL: https://arxiv.org/abs/1501.06126
Recommendations
- A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- A new approximation hierarchy for polynomial conic optimization
- A Lagrangian relaxation view of linear and semidefinite hierarchies
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
Cites Work
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Solving semidefinite-quadratic-linear programs using SDPT3
- Global optimization with polynomials and the problem of moments
- A collection of test problems for constrained global optimization algorithms
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- GloptiPoly 3: moments, optimization and semidefinite programming
- Title not available (Why is that?)
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Semidefinite Programming vs. LP Relaxations for Polynomial Programming
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- The truncated complex $K$-moment problem
- Anneaux preordonnes
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A Lagrangian relaxation view of linear and semidefinite hierarchies
- Truncated \(K\)-moment problems in several variables
- Convex relaxations and integrality gaps
- Semidefinite representation of convex sets
- Convexity in SemiAlgebraic Geometry and Polynomial Optimization
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
Cited In (46)
- Signomial and polynomial optimization via relative entropy and partial dualization
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- Title not available (Why is that?)
- A multilevel analysis of the Lasserre hierarchy
- Moment Problem and Its Applications to Risk Assessment
- On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
- A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs
- Homogenization for polynomial optimization with unbounded sets
- On the tightness of semidefinite relaxations for rotation estimation
- Alternative SDP and SOCP approximations for polynomial optimization
- Lasserre hierarchy for large scale polynomial optimization in real and complex variables
- Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
- On polynomial optimization over non-compact semi-algebraic sets
- New dependencies of hierarchies in polynomial optimization
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
- A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- A new algorithm for concave quadratic programming
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
- Certifying convergence of Lasserre's hierarchy via flat truncation
- Algorithm 996
- A hierarchy of spectral relaxations for polynomial optimization
- Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging scheduling
- A new hierarchy of SDP-relaxations for polynomial programming
- LP formulations for polynomial optimization problems
- A Lagrange multiplier expression method for bilevel polynomial optimization
- Computing the Hausdorff boundary measure of semialgebraic sets
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- The moment-SOS hierarchy
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Positive maps and separable matrices
- A sublevel moment-SOS hierarchy for polynomial optimization
- Sparse noncommutative polynomial optimization
- A new approximation hierarchy for polynomial conic optimization
- Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
- SOS is not obviously automatizable, even approximately
- Finding global minima via kernel approximations
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Unconstrained minimization of block-circulant polynomials via semidefinite program in third-order tensor space
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- A Lagrangian relaxation view of linear and semidefinite hierarchies
Uses Software
This page was built for publication: A bounded degree SOS hierarchy for polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397758)
