We consider the robust (or min-max) optimization problem
$J^*:=max_{mathbf{y}in{Omega}}min_{mathbf{x}}{f(mathbf{x},mathbf{y}): (mathbf{x},mathbf{y})inmathbf{Delta}}$
where
f is a polynomial and
({mathbf{Delta}subsetmathbb{R}^ntimesmathbb{R}^p}) as well as
({{Omega}subsetmathbb{R}^p}) are compact basic semi-algebraic sets. We first provide a sequence of polynomial lower approximations
({(J_i)subsetmathbb{R}[mathbf{y}]}) of the optimal value function
({J(mathbf{y}):=min_mathbf{x}{f(mathbf{x},mathbf{y}): (mathbf{x},mathbf{y})in mathbf{Delta}}}). The polynomial
({J_iinmathbb{R}[mathbf{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
({mathbf{y}mapsto J(mathbf{y})}), recently proposed in Lasserre (SIAM J Optim 20, 1995-2022,
2010). Then for fixed
i, we consider the polynomial optimization problem
({J^*_i:=maxnolimits_{mathbf{y}}{J_i(mathbf{y}):mathbf{y}in{Omega}}}) and prove that
({hat{J}^*_i(:=displaystylemaxnolimits_{ell=1,ldots,i}J^*_ell)}) converges to
J* as
i → ∞. Finally, for fixed
? ≤
i, each
({J^*_ell}) (and hence
({hat{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).
