Publication:2330641

DOI10.1007/S10107-018-1276-2zbMATH Open1461.65179arXiv1701.01549OpenAlexW2963627984WikidataQ129953487 ScholiaQ129953487MaRDI QIDQ2330641FDOQ2330641

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

zbMATH Keywords

critical pointoptimality conditionLagrange multiplierLasserre's relaxationtight relaxation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Global optimization with polynomials and the problem of moments
• 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
• 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
• Sharp Effective Nullstellensatz
• 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

Cited In (22)

• 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
• Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph
• Homogenization for polynomial optimization with unbounded sets
• A Lagrange Multiplier Expression Method for Bilevel Polynomial Optimization
• Lagrangian quadratic bounds in polynomial nonconvex and Boolean models with superfluous constraints
• A Lagrangian Relaxation for Golomb Rulers
• Saddle points of rational functions
• 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 new scheme for approximating the weakly efficient solution set of vector rational optimization problems
• Convex generalized Nash equilibrium problems and polynomial optimization

Uses Software

• SINGULAR
• SeDuMi
• GloptiPoly

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems 👍 👎
• Lagrangian bounds in multiextremal polynomial and discrete optimization problems 👍 👎
• An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization 👍 👎
• On the Lasserre Hierarchy of Semidefinite Programming Relaxations of Convex Polynomial Optimization Problems 👍 👎
• Polynomial Programming: LP-Relaxations Also Converge 👍 👎
• On linear programming relaxations for solving polynomial programming problems 👍 👎
• Polinomiális optimalizálási feladatok és relaxációik 👍 👎

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)