An Exact Jacobian SDP Relaxation for Polynomial Optimization

2010/06/11 by Nie, Jiawang · 2 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1006.2418

Abstract

Given polynomials f(x), g_i(x), h_j(x), we study how to minimize f on the semialgebraic set S = x ∈ Rⁿ: h₁(x)=...=h_m1(x) =0, g₁(x) >= 0, ..., g_m2(x) >= 0. Let f_min be the minimum of f on S. Suppose S is nonsingular and f_min is achievable on S,which is true generically. The paper proposes a new semidefinite programming (SDP) relaxation for this problem. First we construct a set of new polynomials φ₁(x), …, φ_r(x), by using the Jacobian of f,h_i,g_j, such that the above problem is unchanged by adding new equations φ_j(x)=0. Then we prove that for all N big enough, the standard N-th order Lasserre's SDP relaxation is exact for solving this equivalent problem, that is, it returns a lower bound that is equal to f_min. Some variations and examples are also shown.

Cited by

• Small Resultant Systems via Linear Combinations
• Lagrange multiplier expressions for matrix polynomial optimization and tight relaxations

Related

• Exact relaxation for polynomial optimization on semi-algebraic sets
• An algorithm for semi-infinite polynomial optimization
• Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction
• Minimizing Rational Functions by Exact Jacobian SDP Relaxation Applicable to Finite Singularities
• A bounded degree SOS hierarchy for polynomial optimization