Robust global optimization with polynomials

We consider the optimization problems max_z∈Ω min_x∈K p(z, x) and min_{x ∈ K} max_{z ∈ Ω} p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Ω can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max_{z ∈ Ω} p(z), whereas the second problem is a robust analogue of the generic problem min_{x ∈ K} p(x) of minimizing a polynomial over a semi-algebraic set. We show that the optimal values of both robust optimization problems can be approximated as closely as desired, by solving a hierarchy of SDP relaxations. We also relate and compare the SDP relaxations associated with the max-min and the min-max robust optimization problems.