2011/01/21 by Jean B. Lasserre, Lasserre, Jean
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · doi:10.48550/arxiv.1101.4122
openalex publication_date 2011/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the semi-infinite optimization problem: f^*:=minx∈ X \f(x): g(x,y) ≤ 0, \forally∈ Yx\, where f,g are polynomials and X⊂ Rn as well as Y_\x⊂ Rp, x∈ X, are compact basic semi-algebraic sets. To approximate f^* we proceed in two steps. First, we use the "joint+marginal" approach of the author to approximate from above the function x↦Φ(x)=sup \g(x,y): y∈ Yx\ by a polynomial Φd≥Φ, of degree at most 2d, with the strong property that Φd converges to Φ for the L1-norm, as d→∞ (and in particular, almost uniformly for some subsequence (d_ℓ), ℓ∈\N). Then we solve the polynomial optimization problem f^*d=minx∈ X \f(x): Φd(x)≤0\ via a (by now standard) hierarchy of semidefinite relaxations. It turns out that the optimal value f^*d≥ f^* converges to f^* as d→∞. In practice we let d be fixed, small, and relax the constraint Φd≤0 to Φd(x)≤ε with ε>0, allowing to change ε dynamically.