Tight Relaxations for Polynomial Optimization and Lagrange Multiplier Expressions

2017/01/06 by Jiawang Nie, Nie, Jiawang · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1701.01549

openalex publication_date 2017/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem

Related

• A Lagrangian relaxation view of linear and semidefinite hierarchies
• Lagrange multiplier expressions for matrix polynomial optimization and tight relaxations
• Convergence of the Lasserre Hierarchy of SDP Relaxations for Convex Polynomial Programs without Compactness
• Optimality Conditions and Finite Convergence of Lasserre's Hierarchy
• Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction