Resumen de An algorithm for semi-infinite polynomial optimization

J.B. Lasserre

• We consider the semi-infinite optimization problem:

  f∗:=minx∈X{f(x):g(x,y)≤0,∀y∈Yx}, where f,g are polynomials and X⊂ℝ n as well as Y x ⊂ℝ p , x∈X, are compact basic semi-algebraic sets. To approximate f ∗ we proceed in two steps. First, we use the “joint+marginal” approach of Lasserre (SIAM J. Optim. 20:1995–2022, 2010) to approximate from above the function x↦Φ(x)=sup {g(x,y):y∈Y x } by a polynomial Φ d ≥Φ, of degree at most 2d, with the strong property that Φ d converges to Φ for the L 1-norm, as d→∞ (and in particular, almost uniformly for some subsequence (d ℓ ), ℓ∈ℕ). Therefore, to approximate f ∗ one may wish to solve the polynomial optimization problem f0d=minx∈X{f(x):Φd(x)≤0} via a (by now standard) hierarchy of semidefinite relaxations, and for increasing values of d. In practice d is fixed, small, and one relaxes the constraint Φ d ≤0 to Φ d (x)≤ε with ε>0, allowing us to change ε dynamically. As d increases, the limit of the optimal value fϵd is bounded above by f ∗+ε.