An algorithm for semi-infinite polynomial optimization

Abstract

We consider the semi-infinite optimization problem:

$$f^*:=\min_{\mathbf{x}\in\mathbf{X}} \bigl\{f(\mathbf{x}):g(\mathbf{x},\mathbf{y}) \leq 0, \forall\mathbf{y}\in\mathbf {Y}_\mathbf{x}\bigr\},$$

where f,g are polynomials and X⊂ℝⁿ 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 ₁-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 $f^{0}_{d}=\min_{\mathbf{x}\in\mathbf{X}} \{f(\mathbf{x}): \varPhi _{d}(\mathbf{x})\leq0\}$ 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^{\epsilon}_{d}$ is bounded above by f ^∗+ε.