Abstract

We examine the duality gap between the robust counterpart of a primal uncertain convex optimization problem and the optimistic counterpart of its uncertain Lagrangian dual and identify the classes of uncertain problems which do not have a duality gap. The absence of a duality gap (or equivalently zero duality gap) means that the primal worst value equals the dual best value. We first present a new constraint qualification characterizing zero duality gap for convex programming problems under uncertainty. We then show that the constraint qualification always holds for several important classes of robust convex programming problems. They include convex programs with separable inequality constraints under scenario uncertainty, convex optimization problems over faithfully convex inequality constraints under scenario uncertainty and convex programs with quadratic inequality constraints under spectral norm uncertainty.

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

Guo Yin Li

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

g.li@unsw.edu.au

Jinhua Wang

Department of Applied Mathematics, University of New South Wales, Sydney 2052, Australia
and: Dept. of Mathematics, Zhejiang University of Technology, Hangzhou 310032, P. R. China

wjh@zjut.edu.cn

Keywords

  • Robust convex programming
  • zero duality gap
  • robust optimization
  • convex optimization under uncertainty

Mathematics Subject Classification

90C20,90C30,90C26,90C46

References

  1. A. Auslender, M. Teboulle: Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer Monographs in Mathematics, Springer, New York (2003).Google Scholar
  2. A. Beck, A. Ben-Tal: Duality in robust optimization: primal worst equals dual best, Oper. Res. Lett. 37 (2009) 1–6.https://doi.org/10.1016/j.orl.2008.09.010Google Scholar
  3. A. Ben-Tal, A. Nemirovski: Robust optimization–methodology and applications, Math. Program., Ser. B 92 (2002) 453–480.https://doi.org/10.1007/s101070100286Google Scholar
  4. 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
  5. A. Ben-Tal, A. Nemirovski: Selected topics in robust convex optimization, Math. Program., Ser. B 112 (2008) 125–158.https://doi.org/10.1007/s10107-006-0092-2Google Scholar
  6. A. Ben-Tal, S. Boyd, A. Nemirovski: Extending scope of robust optimization: comprehensive robust counterparts of uncertain problems, Math. Program., Ser. 107(1–2) (2006) 63–89.https://doi.org/10.1007/s10107-005-0679-zGoogle Scholar
  7. S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge University Press, Cambridge (2004).https://doi.org/10.1017/CBO9780511804441Google Scholar
  8. T. Champion: Duality gap in convex programming, Math. Progam., Ser. A 99 (2004) 487–498.https://doi.org/10.1007/s10107-003-0461-zGoogle Scholar
  9. V. Jeyakumar: Constraint qualifications characterizing Lagrangian duality in convex optimization, J. Optim. Theory Appl. 136 (2008) 31–41.https://doi.org/10.1007/s10957-007-9294-xGoogle Scholar
  10. V. Jeyakumar, G. M. Lee, N. Dinh: New sequential Lagrange multiplier conditions characterizing optimality without constraint qualification for convex programs, SIAM J. Optim. 14 (2003) 534–547.https://doi.org/10.1137/S1052623402417699Google Scholar
  11. V. Jeyakumar, G. Li: Strong duality in robust convex programming: complete characterizations, SIAM J. Optim. 20 (2010) 3384–3407.https://doi.org/10.1137/100791841Google Scholar
  12. V. Jeyakumar, G. Li: Characterizing robust set containments and solutions of uncertain linear programs without qualifications, Oper. Res. Lett. 38 (2010) 188–194.https://doi.org/10.1016/j.orl.2009.12.004Google Scholar
  13. V. Jeyakumar, G. Li: Stable zero duality gaps in convex programming: complete dual characterisations with applications to semidefinite programs, J. Math. Anal. Appl. 360(1) (2009) 156–167.https://doi.org/10.1016/j.jmaa.2009.06.043Google Scholar
  14. V. Jeyakumar, G. Li: New dual constraint qualifications characterizing zero duality gaps of convex programs and semidefinite Programs, Nonlinear Anal. 71(12) (2009) 2239–2249.https://doi.org/10.1016/j.na.2009.05.009Google Scholar
  15. B. Kummer: Stability and weak duality in convex programming without regularity, Wiss. Z. Humboldt-Univ. Berlin, Math.-Naturw. R. 30(5) (1981) 381–386.https://doi.org/10.1512/iumj.1981.30.30022Google Scholar
  16. C. Li, K. F. Ng, T. K. Pong: Constraint qualifications for convex inequality systems with applications in constrained optimization, SIAM J. Optim. 19 (2008) 163–187.https://doi.org/10.1137/060676982Google Scholar
  17. C. Li, D. H. Fang, G. López, M. A. López: Stable and total Fenchel duality for convex optimization problems in locally convex spaces, SIAM J. Optim. 20 (2009) 1032–1051.https://doi.org/10.1137/080734352Google Scholar
  18. G. Li, V. Jeyakumar: Qualification-free optimality conditions for convex programs with separable inequality constraints, J. Convex Analysis 16(3&4) (2009) 845–856.https://doi.org/10.68381/jca16051Google Scholar
  19. G. Li, K. F. Ng: On extension of Fenchel duality and its application, SIAM J. Optim. 19 (2008) 1489–1509.https://doi.org/10.1137/080716803Google Scholar
  20. P. Tseng: Some convex programs without a duality gap, Math. Progam., Ser. B 116 (2009) 553–578.https://doi.org/10.1007/s10107-007-0110-zGoogle Scholar
  21. R. T. Rockafellar: Convex Analysis, Princeton Univ. Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  22. R. T. Rockafellar: Ordinary convex programs without a duality gap, J. Optim. Theory Appl. 7 (1971) 143–148.https://doi.org/10.1007/BF00932472Google Scholar

Suggested citation

V. Jeyakumar, G. Y. Li, J. Wang. “Some Robust Convex Programs without a Duality Gap.” Journal of Convex Analysis 20 (2013), No. 2, 377–394. https://doi.org/10.68381/jca20024

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2013. Rights now held by Banach Press.