Abstract

We examine a robust SOS-convex polynomial program under a general class of bounded uncertainty, called intersection ellipsoidal uncertainty, which is described by the intersection of a family of ellipsoids and covers many commonly used uncertainty classes of robust optimization. The class of SOS-convex polynomials is a numerically tractable subclass of convex polynomials and, in particular, contains convex quadratic functions and convex separable polynomials. We present a conical linear program with a coupled sum-of-squares polynomial and linear matrix inequality constraints as its relaxation problem and show that the relaxation problem can equivalently be reformulated as a semidefinite linear program (SDP). Under a mild well-posedness condition, we establish that the so-called SDP relaxation is tight in the sense that the optimal values of the robust SOS-convex polynomial program and its relaxation problem are equal. We also show, under a general regularity condition, that the SDP relaxation is exact in the sense that the relaxation problem not only shares the same optimal value with the robust SOS-convex polynomial program but also attains its optimum, extending the corresponding known results in the robust optimization literature to the general class of intersection ellipsoidal uncertainty.

Author information

Contact details are reproduced from the original publication and may be historical.

Thai Doan Chuong

School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia

chuongthaidoan@yahoo.com

Vaithilingam Jeyakumar

School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia

v.jeyakumar@unsw.edu.au

Keywords

  • Robust optimization
  • semi-infinite convex program
  • convex polynomial
  • semidefinite linear program
  • SDP relaxation

Mathematics Subject Classification

49K99, 65K10, 90C29, 90C46

References

  1. A. A. Ahmadi, P. A. Parrilo: A complete characterization of the gap between convexity and sos-convexity, SIAM J. Optim. 23(2) (2013) 811–833.https://doi.org/10.1137/110856010Google Scholar
  2. E. G. Belousov, D. Klatte: A Frank-Wolfe type theorem for convex polynomial programs, Comput. Optim. Appl. 22(1) (2002) 37–48.https://doi.org/10.1023/A:1014813701864Google Scholar
  3. A. Ben-Tal, L. El Ghaoui, A. Nemirovski: Robust Optimization, Princeton Ser. Appl. Math., Princeton University Press, Princeton (2009).https://doi.org/10.1515/9781400831050Google Scholar
  4. A. Ben-Tal, A. Nemirovski: Robust convex optimization, Math. Oper. Res. 23(4) (1998) 769–805.https://doi.org/10.1287/moor.23.4.769Google Scholar
  5. A. Ben-Tal, A. Nemirovski: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, SIAM, Philadelphia (2001).https://doi.org/10.1137/1.9780898718829Google Scholar
  6. D. Bertsimas, D. B. Brown, C. Caramanis: Theory and applications of robust optimization, SIAM Review 53 (2011) 464–501.https://doi.org/10.1137/080734510Google Scholar
  7. M. J. Canovas, M. A. López, B. S. Mordukhovich, J. Parra: Variational analysis in semi-infinite and infinite programming. I. Stability of linear inequality systems of feasible solutions, SIAM J. Optim. 20 (2009) 1504–1526.https://doi.org/10.1137/090765948Google Scholar
  8. T. D. Chuong, V. Jeyakumar: A generalized Farkas lemma with a numerical certificate and linear semi-infinite programs with SDP duals, Linear Algebra Appl. 515 (2017) 38–52.https://doi.org/10.1016/j.laa.2016.11.008Google Scholar
  9. T. D. Chuong, V. Jeyakumar: Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints, J. Optim. Theory Appl. 173(2) (2017) 683–703.https://doi.org/10.1007/s10957-017-1069-4Google Scholar
  10. T. D. Chuong, V. Jeyakumar: Convergent hierarchy of SDP relaxations for a class of semi-infinite convex polynomial programs and applications, Appl. Math. Comput. 315 (2017) 381–399.https://doi.org/10.1016/j.amc.2017.07.076Google Scholar
  11. J. W. Helton, J. Nie: Semidefinite representation of convex sets, Math. Program. Ser. A 122(1) (2010) 21–64.https://doi.org/10.1007/s10107-008-0240-yGoogle Scholar
  12. J.-B. Hiriart-Urruty, C. Lemarechal: Convex analysis and minimization algorithms. I: Fundamentals, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  13. M. A. Goberna, M. A. López: Linear Semi-Infinite Optimization, Wiley, Chichester (1998).Google Scholar
  14. M. A. Goberna, M. A. López: Post-Optimal Analysis in Linear Semi-Infinite Optimization, Springer Briefs, Springer, New York (2014).https://doi.org/10.1007/978-1-4899-8044-1Google Scholar
  15. D. Goldfarb, G. Iyengar: Robust convex quadratically constrained programs, Math. Program. 97 (2003) 495–515.https://doi.org/10.1007/s10107-003-0425-3Google Scholar
  16. M. Grant, S. Boyd: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx, March 2014.Google Scholar
  17. V. Jeyakumar, S. Kim, G. M. Lee, G. Li: Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and semialgebraic feasible sets, J. Global Optim. 65 (2016) 175–190.https://doi.org/10.1007/s10898-015-0356-6Google Scholar
  18. V. Jeyakumar, J.-B. Lasserre, G. Li: On polynomial optimization over noncompact semi-algebraic sets, J. Optim. Theory Appl. 163 (2014) 707–718.https://doi.org/10.1007/s10957-014-0545-3Google Scholar
  19. V. Jeyakumar, J.-B. Lasserre, G. Li, T. S. Pham: Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems, SIAM J. Optim. 26 (2016) 753–780.https://doi.org/10.1137/15M1017922Google Scholar
  20. V. Jeyakumar, G. Li, J. Vicente-Perez: Robust SOS-convex polynomial programs: Exact SDP relaxations, Optim. Lett. 9(1) (2015) 1–18.https://doi.org/10.1007/s11590-014-0732-zGoogle Scholar
  21. V. Jeyakumar, J. Vicente-Perez: Dual semidefinite programs without duality gaps for a class of convex minimax programs, J. Optim. Theor. Appl. 162 (2014) 735–753.https://doi.org/10.1007/s10957-013-0496-0Google Scholar
  22. V. Jeyakumar, T. S. Pham, G. Li: Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness, Oper. Res. Lett. 42(1) (2014) 34–40.https://doi.org/10.1016/j.orl.2013.11.005Google Scholar
  23. V. Jeyakumar, H. Wolkowicz: Zero duality gaps in infinite-dimensional programming, J. Optim. Theory Appl. 67(1) (1990) 87–108.https://doi.org/10.1007/BF00939737Google Scholar
  24. N. Kanzi, M. Soleimani-damaneh: Slater CQ, optimality and duality for quasiconvex semi-infinite optimization problems, J. Math. Anal. Appl. 434(1) (2016) 638–651.https://doi.org/10.1016/j.jmaa.2015.08.013Google Scholar
  25. P. Krokhmal, A. Prokopyev: Optimization Letters best paper award for 2015, Optim. Lett. 11(1) (2016) 1–2.https://doi.org/10.1007/s11590-016-1099-0Google Scholar
  26. J. B. Lasserre: Moments, Positive Polynomials and Their Applications, Imperial College Press, London (2009).https://doi.org/10.1142/p665Google Scholar
  27. J. B. Lasserre: An algorithm for semi-infinite polynomial optimization, TOP 20 (2012) 119–129.https://doi.org/10.1007/s11750-011-0172-1Google Scholar
  28. C. Li, K. F. Ng, T. K. Pong: Constraint qualifications for convex inequality systems with applications in constrained optimization, SIAM J. Optim. 19(1) (2008) 163–187.https://doi.org/10.1137/060676982Google Scholar
  29. C. Li, X. Zhao, Y. Hu: Quasi-Slater and Farkas-Minkowski qualifications for semi-infinite programming with applications, SIAM J. Optim. 23(4) (2013) 2208–2230.https://doi.org/10.1137/130911287Google Scholar
  30. B. S. Mordukhovich, N. M. Nam: An Eeasy Path to Convex Analysis and Applications, Synthesis Lectures on Mathematics and Statistics 14, Morgan and Claypool, Williston (2014).https://doi.org/10.1007/978-3-031-02406-1Google Scholar
  31. Y. Pandey, S. K. Mishra: On strong KKT type sufficient optimality conditions for nonsmooth multiobjective semi-infinite mathematical programming problems with equilibrium constraints, Oper. Res. Lett. 44(1) (2016) 148–151.https://doi.org/10.1016/j.orl.2015.12.007Google Scholar
  32. P. A. Parrilo: Polynomial optimization, sums of squares, and applications, in: Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Ser. Optim. 13, SIAM, Philadelphia (2013) 47–157.https://doi.org/10.1137/1.9781611972290.ch3Google Scholar
  33. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  34. M. Sion: On general minimax theorems, Pacific J. Math. 8 (1958) 171–176.https://doi.org/10.2140/pjm.1958.8.171Google Scholar
  35. L. Wang, F. Guo: Semidefinite relaxations for semi-infinite polynomial programming, Comput. Optim. Appl. 58(1) (2014) 133–159.https://doi.org/10.1007/s10589-013-9612-1Google Scholar
  36. Y. Xu, W. Sun, L. Qi: On solving a class of linear semi-infinite programming by SDP method, Optimization 64 (2015) 603–616.Google Scholar

Suggested citation

T. D. Chuong, V. Jeyakumar. “Tight SDP Relaxations for a Class of Robust SOS-Convex Polynomial Programs without the Slater Condition.” Journal of Convex Analysis 25 (2018), No. 4, 1159–1182. https://doi.org/10.68381/jca25073

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2018. Rights now held by Banach Press LLC.