Tight relaxations for polynomial optimization and Lagrange multiplier expressions
From MaRDI portal
Publication:2330641
DOI10.1007/S10107-018-1276-2zbMATH Open1461.65179arXiv1701.01549OpenAlexW2963627984WikidataQ129953487 ScholiaQ129953487MaRDI QIDQ2330641FDOQ2330641
Authors: Jiawang Nie 
Publication date: 22 October 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1701.01549
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
Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- Title not available (Why is that?)
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Title not available (Why is that?)
- Global optimization with polynomials and the problem of moments
- Title not available (Why is that?)
- Global minimization of rational functions and the nearest GCDs
- Global optimization of rational functions: a semidefinite programming approach
- Minimizing polynomials via sum of squares over the gradient ideal
- Minimizing the sum of many rational functions
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- GloptiPoly 3: moments, optimization and semidefinite programming
- Sums of squares, moment matrices and optimization over polynomials
- Positivity and sums of squares: a guide to recent results
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Semidefinite representations for finite varieties
- Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
- Discriminants and nonnegative polynomials
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- An exact Jacobian SDP relaxation for polynomial optimization
- Global Optimization of Polynomials Using the Truncated Tangency Variety and Sums of Squares
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals
- Title not available (Why is that?)
- Sharp Effective Nullstellensatz
- Truncated \(K\)-moment problems in several variables
- Linear optimization with cones of moments and nonnegative polynomials
- Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
- An introduction to polynomial and semi-algebraic optimization
- Certifying convergence of Lasserre's hierarchy via flat truncation
- Polynomial optimization with real varieties
- Convexity in SemiAlgebraic Geometry and Polynomial Optimization
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
- Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
- Bound-constrained polynomial optimization using only elementary calculations
- A bounded degree SOS hierarchy for polynomial optimization
- Optimization over polynomials: selected topics
Cited In (24)
- Approximation bound analysis based on the tight constraints polynomial optimization problems of Lasserre relaxation
- Nonemptiness and compactness of solution sets to generalized polynomial complementarity problems
- On the strength of recursive McCormick relaxations for binary polynomial optimization
- The saddle point problem of polynomials
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Dehomogenization for completely positive tensors
- Learning diagonal Gaussian mixture models and incomplete tensor decompositions
- Rational Generalized Nash Equilibrium Problems
- Hausdorff distance between convex semialgebraic sets
- An SDP method for copositivity of partially symmetric tensors
- How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
- Homogenization for polynomial optimization with unbounded sets
- Lagrangian quadratic bounds in polynomial nonconvex and Boolean models with superfluous constraints
- A Lagrangian Relaxation for Golomb Rulers
- Saddle points of rational functions
- Lagrangian-conic relaxations. II: Applications to polynomial optimization problems
- The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- Border basis relaxation for polynomial optimization
- The multivariate eigenvalues of symmetric tensors
- A Lagrange multiplier expression method for bilevel polynomial optimization
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- A new scheme for approximating the weakly efficient solution set of vector rational optimization problems
- Convex generalized Nash equilibrium problems and polynomial optimization
Uses Software
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)
