Tight relaxations for polynomial optimization and Lagrange multiplier expressions
From MaRDI portal
Publication:2330641
Abstract: This paper proposes tight semidefinite relaxations for polynomial optimization. The optimality conditions are investigated. We show that generally Lagrange multipliers can be expressed as polynomial functions in decision variables over the set of critical points. The polynomial expressions can be determined by linear equations. Based on these expressions, new Lasserre type semidefinite relaxations are constructed for solving polynomial optimization. We show that the hierarchy of new relaxations has finite convergence, or equivalently, the new relaxations are tight for a finite relaxation order.
Recommendations
- Polynomial optimization problems and their relaxations
- Lagrangian-conic relaxations. II: Applications to polynomial optimization problems
- On linear programming relaxations for solving polynomial programming problems
- An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization
- Lagrangian bounds in multiextremal polynomial and discrete optimization problems
- Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems
- Polynomial Programming: LP-Relaxations Also Converge
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- Approximation bound analysis based on the tight constraints polynomial optimization problems of Lasserre relaxation
Cites work
- scientific article; zbMATH DE number 1726532 (Why is no real title available?)
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 1206370 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- scientific article; zbMATH DE number 1827070 (Why is no real title available?)
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- A bounded degree SOS hierarchy for polynomial optimization
- An exact Jacobian SDP relaxation for polynomial optimization
- An introduction to polynomial and semi-algebraic optimization
- Bound-constrained polynomial optimization using only elementary calculations
- Certifying convergence of Lasserre's hierarchy via flat truncation
- Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
- Convexity in SemiAlgebraic Geometry and Polynomial Optimization
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Discriminants and nonnegative polynomials
- Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
- Global Optimization of Polynomials Using the Truncated Tangency Variety and Sums of Squares
- Global minimization of rational functions and the nearest GCDs
- Global optimization of rational functions: a semidefinite programming approach
- Global optimization with polynomials and the problem of moments
- GloptiPoly 3: moments, optimization and semidefinite programming
- Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
- Linear optimization with cones of moments and nonnegative polynomials
- Minimizing polynomials via sum of squares over the gradient ideal
- Minimizing the sum of many rational functions
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Optimization over polynomials: selected topics
- Polynomial optimization with real varieties
- Positivity and sums of squares: a guide to recent results
- Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals
- Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Semidefinite representations for finite varieties
- Sharp Effective Nullstellensatz
- Sums of squares, moment matrices and optimization over polynomials
- Truncated \(K\)-moment problems in several variables
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(24)- A Lagrange multiplier expression method for bilevel polynomial optimization
- On the strength of recursive McCormick relaxations for binary polynomial optimization
- Lagrangian-conic relaxations. II: Applications to polynomial optimization problems
- Homogenization for polynomial optimization with unbounded sets
- Rational Generalized Nash Equilibrium Problems
- Approximation bound analysis based on the tight constraints polynomial optimization problems of Lasserre relaxation
- The saddle point problem of polynomials
- A new scheme for approximating the weakly efficient solution set of vector rational optimization problems
- The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
- Lagrangian quadratic bounds in polynomial nonconvex and Boolean models with superfluous constraints
- Nonemptiness and compactness of solution sets to generalized polynomial complementarity problems
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- A Lagrangian Relaxation for Golomb Rulers
- Saddle points of rational functions
- The multivariate eigenvalues of symmetric tensors
- Learning diagonal Gaussian mixture models and incomplete tensor decompositions
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Dehomogenization for completely positive tensors
- Hausdorff distance between convex semialgebraic sets
- An SDP method for copositivity of partially symmetric tensors
- Border basis relaxation for polynomial optimization
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- Convex generalized Nash equilibrium problems and polynomial optimization
- How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
This page was built for publication: Tight relaxations for polynomial optimization and Lagrange multiplier expressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330641)
