Min-max and robust polynomial optimization

摘要

We consider the robust (or min-max) optimization problem J* := max min{f(x, y) : (x, y)∈△} y∈Ω where f is a polynomial and ⊂ R~n × R~p as well as Ω R~p are compact basic semi-algebraic sets. We first provide a sequence of polynomial lower approximations (J_i) ⊂ R[y] of the optimal value function J(y) := min_x{f(x, y) : (x, y) ∈△}. The polynomial J_i∈R[y] is obtained from an optimal (or nearly optimal) solution of a semidefinite program, the ith in the "joint+marginal" hierarchy of semidefinite relaxations associated with the parametric optimization problem y →J(y), recently proposed in Lasserre (SIAM J Optim 20, 1995-2022, 2010). Then for fixed i, we consider the polynomial optimization problem J_i~* := max_y{J_i,(y) : y ∈Ω} and prove that J_i~*(:= max_(τ=1..._iJ_τ~*) converges to J~* as i→∞. Finally, for fixed τ≤ i, each J_τ~* (and hence J_i~*) can be approximated by solving a hierarchy of semidefinite relaxations as already described in Lasserre (SIAM J Optim 11, 796-817, 2001; Moments, Positive Polynomials and Their Applications. Imperial College Press, London 2009).