Abstract

We introduce the notion of ρ-SOS-convexity, extending the numerically checkable concept of SOS-convexity of a real polynomial. The class of ρ-SOS-convex polynomials includes the important class of (not necessarily convex) quadratic functions. We provide various characterizations of ρ-SOS-convexity in terms of SOS-convexity. Consequently, we establish strong duality results for classes of nonconvex polynomial optimization problems involving strong SOS-convex (where ρ > 0) and weak SOS-convex (where ρ < 0) polynomials. These classes of problems include some polynomial optimization problems, involving SOS-convex polynomials, minimax quadratic optimization problems with quadratic constraints, fractional programming problems and robust optimization problems. Our results also provide necessary and sufficient conditions for strong duality of some classes of minimax quadratic optimization problems and extended trust-region problems.

Author information

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

Vaithilingam Jeyakumar

Dept. of Applied Mathematics, University of New South Wales, Sydney 2052, Australia

v.jeyakumar@unsw.edu.au

Gue Myung Lee

Dept. of Applied Mathematics, Pukyong National University, Busan 608-737, Korea

gmlee@pknu.ac.kr

Jae Hyoung Lee

Dept. of Applied Mathematics, Pukyong National University, Busan 608-737, Korea

mc7558@naver.com

Keywords

  • Strong duality
  • rho-SOS-convex polynomials
  • SOS-convex polynomials
  • non-convex quadratic optimization
  • extended trust-region problems

Mathematics Subject Classification

26A51, 90C25, 47N10

References

  1. A. A. Ahmadi, P. A. Parrilo: A convex polynomial that is not SOS-convex, Math. Program. 135 (2012) 275–292.https://doi.org/10.1007/s10107-011-0457-zGoogle Scholar
  2. 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
  3. W. Ai, S. Zhang: Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J. Optim. 19(4) (2009) 1735–1756.https://doi.org/10.1137/07070601XGoogle Scholar
  4. M. Anjos, J. B. Lasserre: Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, New York (2012).https://doi.org/10.1007/978-1-4614-0769-0Google Scholar
  5. A. Beck, Y. C. Eldar: Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim. 17 (2006) 844–860.https://doi.org/10.1137/050644471Google Scholar
  6. A. Beck: Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming, J. Optim. Theory Appl. 142 (2009) 1–29.https://doi.org/10.1007/s10957-009-9539-yGoogle Scholar
  7. A. Ben-Tal, L. E. Ghaoui, A. Nemirovski: Robust Optimization, Princeton Series in Applied Mathematics, Princeton University Press, Princeton (2009).https://doi.org/10.1515/9781400831050Google Scholar
  8. A. Ben-Tal, A. Nemirovski: Lectures on Modern Convex Optimization. Analysis, Algorithms and Engineering Applications, SIAM-MPS, Philadelphia (2000).https://doi.org/10.1137/1.9780898718829Google Scholar
  9. S. Burer, K. M. Anstreicher: Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim. 23(1) (2013) 432–451.https://doi.org/10.1137/110826862Google Scholar
  10. M. Castellani, M. Pappalardo: Characterizations of ρ-convex functions, in: Generalized Convexity, Generalized Monotonicity: Recent Results (Luminy, 1996), J.-P. Crouzeix et al. (ed.), Nonconvex Optim. Appl. 27, Kluwer, Dordrecht (1998) 219–233.https://doi.org/10.1007/978-1-4613-3341-8_9Google Scholar
  11. A. R. Conn, N. I. M. Gould, P. L. Toint: Trust-Region Methods, MPS-SIAM Series in Optimization 1, SIAM, Philadelphia (2000).https://doi.org/10.1137/1.9780898719857Google Scholar
  12. A. M. Geoffrion: Duality in nonlinear programming: a simplified applications-oriented develoment, in: Perspectives on Optimization, A. M. Geoffrion (ed.), Addison-Wesley, Reading (1972) 65–101.Google Scholar
  13. J. W. Helton, J. W. Nie: Semidefinite representation of convex sets, Math. Program. 122(1) (2010) 21–64.https://doi.org/10.1007/s10107-008-0240-yGoogle Scholar
  14. V. Jeyakumar: On subgradient duality with strong and weak convex functions, J. Aust. Math. Soc., Ser. A 40 (1986) 143–152.https://doi.org/10.1017/S1446788700027130Google Scholar
  15. V. Jeyakumar, G. M. Lee, G. Y. Li: Alternative theorems for quadratic inequality systems and global quadratic optimization, SIAM J. Optim. 20(2) (2009) 983–1001.https://doi.org/10.1137/080736090Google Scholar
  16. V. Jeyakumar, G. Li: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Math. Program. 147 (2014) 171–206.https://doi.org/10.1007/s10107-013-0716-2Google Scholar
  17. V. Jeyakumar, G. Li: Exact SDP relaxations for classes of nonlinear semidefinite programming problems, Oper. Res. Lett. 40 (2012) 529–536.https://doi.org/10.1016/j.orl.2012.09.006Google Scholar
  18. V. Jeyakumar, G. Li, J. Vicente-Pérez: Robust SOS-convex polynomial optimization problems: exact SDP relaxations, Optim. Lett. 9(1) 2015 1–18.https://doi.org/10.1007/s11590-014-0732-zGoogle Scholar
  19. V. Jeyakumar, J. Vicente-Pérez: Dual semidefinite programs without duality gaps for a class of convex minimax programs, J. Optim. Theory Appl. 162 (2014) 735–753.https://doi.org/10.1007/s10957-013-0496-0Google Scholar
  20. V. Jeyakumar, G. Li, G. M. Lee: Robust duality for generalized convex programming problems under data uncertainty, Nonlinear Anal. 75 (2012) 1362–1373.https://doi.org/10.1016/j.na.2011.04.006Google Scholar
  21. J. B. Lasserre: Moments, Positive Polynomials and Their Applications, Imperial College Press, London (2009).https://doi.org/10.1142/p665Google Scholar
  22. O. L. Mangasarian: Nonlinear Programming, SIAM, Philadelphia (1994).https://doi.org/10.1137/1.9781611971255Google Scholar
  23. B. T. Polyak: Convexity of quadratic transformations and its use in control and optimization, J. Optim. Theory Appl. 99 (1998) 563–583.https://doi.org/10.1023/A:1021798932766Google Scholar
  24. J.-Ph. Vial: Strong and weak convexity of sets and functions, Math. Oper. Res. 8 (1983) 231–259.https://doi.org/10.1287/moor.8.2.231Google Scholar
  25. J.-Ph. Vial: Strong convexity of sets and functions, J. Math. Econ. 9 (1982) 187–205.https://doi.org/10.1016/0304-4068(82)90026-XGoogle Scholar
  26. Z. Y. Wu: Sufficient optimality conditions for weakly convex minimization problems, J. Glob. Optim. 39 (2007) 427–440.https://doi.org/10.1007/s10898-007-9147-zGoogle Scholar

Suggested citation

V. Jeyakumar, G. M. Lee, J. H. Lee. “Generalized SOS-Convexity and Strong Duality with SDP Dual Programs in Polynomial Optimization.” Journal of Convex Analysis 22 (2015), No. 4, 999–1023. https://doi.org/10.68381/jca22053

Download BibTeXPublished by Heldermann Verlag.

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