×

A convergent hierarchy of SDP relaxations for a class of hard robust global polynomial optimization problems. (English) Zbl 1409.90182

Summary: A hierarchy of semidefinite programming (SDP) relaxations is proposed for solving a broad class of hard nonconvex robust polynomial optimization problems under constraint data uncertainty, described by convex quadratic inequalities. This class of robust polynomial optimization problems, in general, does not admit exact semidefinite program reformulations. Convergence of the proposed SDP hierarchy is given under suitable and easily verifiable conditions. Known exact relaxation results are also deduced from the proposed scheme for the special class of robust convex quadratic programs. Numerical examples are provided, demonstrating the results.

MSC:

90C30 Nonlinear programming
90C31 Sensitivity, stability, parametric optimization
90C22 Semidefinite programming

Software:

YALMIP; SFSDP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization (2009), Princeton UP: Princeton UP Princeton · Zbl 1221.90001
[2] Bertsimas, D.; Brown, D. B., Constructing uncertainty sets for robust linear optimization, Oper. Res., 57, 1483-1495 (2009) · Zbl 1228.90061
[3] Bertsimas, D.; Brown, D. B.; Caramanis, C., Theory and applications of robust optimization, SIAM Rev., 53, 464-501 (2011) · Zbl 1233.90259
[4] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1058.90049
[5] Goldfarb, D.; Iyengar, G., Robust convex quadratically constrained programs, Math. Program. Ser. B, 97, 3, 495-515 (2003) · Zbl 1106.90365
[6] Henrion, D.; Lasserre, J. B., Convergent relaxations of polynomial matrix inequalities and static output feedback, IEEE Trans. Automat. Control, 51, 2, 192-202 (2006) · Zbl 1366.93180
[7] Jeyakumar, V.; Kim, S.; Lee, G. M.; Li, G., Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets, J. Global Optim., 65, 175-190 (2016) · Zbl 1369.90136
[8] Jeyakumar, V.; Lasserre, J. B.; Li, G., On polynomial optimization over non-compact semi-algebraic sets, J. Optim. Theory Appl., 163, 707-718 (2014) · Zbl 1302.90208
[9] Jeyakumar, V.; Li, G., Exact SDP relaxations for classes of nonlinear semidefinite programming problems, Oper. Res. Lett., 40, 529-536 (2012) · Zbl 1287.90047
[10] Jeyakumar, V.; Li, G.; Vicente-Pérez, J., Robust SOS-convex polynomial optimization problems: exact SDP relaxations, Optim. Lett., 9, 1-18 (2015) · Zbl 1338.90452
[11] Jeyakumar, V.; Pham, T. S.; Li, G., Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness, Oper. Res. Lett., 42, 34-40 (2014) · Zbl 1408.90227
[12] Kim, S.; Kojima, M., Exploiting sparsity in SDP relaxation of polynomial optimization problems, (Anjos, M.; Lasserre, J. B., Handbook on Semidefinite, Conic and Polynomial Optimization: Theory, Algorithm, Software and Applications (2011)), 499-532 · Zbl 1334.90107
[13] Kim, S.; Kojima, M.; Waki, H.; Yamashita, M., Algorithm 920: SFSDP: a Sparse version of full semi definite programming relaxation for sensor network localization problems, A Matlab package SFSDP, ACM Trans. Math. Softw., 38, 4 (2012) · Zbl 1365.65163
[14] Kojima, M.; Muramatsu, M., An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones, Math. Program. Ser. A, 110, 2, 315-336 (2007) · Zbl 1210.90159
[15] Lasserre, J. B., Robust global optimization with polynomials, Math. Program. Ser. B, 107, 1-2, 275-293 (2006) · Zbl 1134.90031
[16] Lasserre, J. B., Moments, Positive Polynomials and their Applications (2009), Imperial College Press
[17] Löfberg, J., Pre- and post-processing sum-of-squares programs in practice, IEEE Trans. Automat. Control, 54, 1007-1011 (2009) · Zbl 1367.90002
[19] Scherer, C. W.; Hol, C. W.J., Matrix sum-of-squares relaxations for robust semi-definite programs, Math. Program. Ser. B, 107, 1-2, 189-211 (2006) · Zbl 1134.90033
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.