Robust global optimization with polynomials. (English) Zbl 1134.90031

Lasserre, Jean B.

Math. Program. 107, No. 1-2 (B), 275-293 (2006).

Summary: We consider the optimization problems
\[ \max_{z\in\Omega} \min_{x\in\mathbf K} p(z,x)\quad\text{and}\quad \min_{x\in\mathbf K} \max_{z\in\Omega} p(z,x), \]
where the criterion \(p\) is a polynomial, linear in the variables \(z\), the set \(\Omega\) can be described by LMIs, and \(\mathbf K\) is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem \(\max_{z\in\Omega}p(z)\), whereas the second problem is a robust analogue of the generic problem \(\min_{x\in\mathbf 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.

MSC:

90C22	Semidefinite programming
90C26	Nonconvex programming, global optimization
90C30	Nonlinear programming
90C31	Sensitivity, stability, parametric optimization
90C47	Minimax problems in mathematical programming

Keywords:

robust optimization; semidefinite programming; semidefinite relaxations

Software:

GloptiPoly; SeDuMi

References:

[1]	Basu, S., Pollack, R., Roy, M-F.: Algorithms in real algebraic geometry, Springer, Berlin, 2003 · Zbl 1031.14028
[2]	Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robustness. In Wolkowicz, A., Saigal, R., Vandenberghe, L. (eds.), Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Kluwer Academic Publishers, Boston, 2000
[3]	Bertsimas, Math. Prog. Series B, 98, 49 (2003) · Zbl 1082.90067
[4]	Bertsimas, Oper. Res., 52, 35 (2004) · Zbl 1165.90565
[5]	Goemans, J. ACM, 42, 1115 (1995) · Zbl 0885.68088
[6]	Henrion, ACM Trans. Math. Soft., 29, 165 (2003) · Zbl 1070.65549
[7]	Henrion, IEEE Contr. Syst. Mag., 24, 72 (2004)
[8]	Lasserre, SIAM J. Optim., 11, 796 (2001) · Zbl 1010.90061
[9]	Lasserre, SIAM J. Optim., 12, 756 (2002) · Zbl 1007.90046
[10]	Lasserre, J.B.: A unified criterion for positive definiteness and semidefiniteness. Technical report 05283, LAAS-CNRS, Toulouse, France, 2005
[11]	Parrilo, Math. Progr. Ser.B, 96, 293 (2003) · Zbl 1043.14018
[12]	Putinar, Indiana Univ. Math. J., 42, 969 (1993) · Zbl 0796.12002
[13]	Todd, Acta Numerica, 10, 515 (2000)
[14]	Vandenberghe, SIAM Rev., 38, 49 (1996) · Zbl 0845.65023