Robust global optimization with polynomials. (English) Zbl 1134.90031

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.


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


GloptiPoly; SeDuMi
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.