Abstract

A condition number of mathematical programming problems with convex data is defined as a suitable measure of the sensitivity of their optimal solutions under canonical perturbations. A pseudo-distance among mathematical programming problems is introduced via the corresponding Kojima functions. Characterizations of well-conditioning are obtained. We prove that the distance to ill-conditioning is bounded from above by a multiple of the reciprocal of the condition number, thereby generalizing previous results dealing with problems with a unique optimal solution.

Author information

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

Tullio Zolezzi

Dipartimento di Matematica, Università di Genova, via Dodecaneso 35, 16146 Genova, Italy

zolezzi@dima.unige.it

Keywords

  • Convex programming
  • condition number
  • distance to ill-conditioning
  • condition number theorem

Mathematics Subject Classification

90C31, 90C25

References

  1. D. Amelunxen, P. Bürgisser: A coordinate-free condition number for convex programming, SIAM J. Optim. 22 (2012) 1029–1041.https://doi.org/10.1137/110835177Google Scholar
  2. M. Bianchi, G. Kassay, R. Pini: Conditioning for optimization problems under general perturbations, Nonlinear Anal. 75 (2013) 37–45.https://doi.org/10.1016/j.na.2011.07.061Google Scholar
  3. M. Bianchi, E. Miglierina, E. Molho, R. Pini: Some results on condition numbers in convex multiobjective optimization, Set-Valued Var. Anal. 21 (2013) 47–65.https://doi.org/10.1007/s11228-012-0207-2Google Scholar
  4. L. Blum, F. Cucker, M. Shub, S. Smale: Complexity and Real Computation, Springer, New York (1998).https://doi.org/10.1007/978-1-4612-0701-6Google Scholar
  5. P. Bürgisser, F. Cucker: Condition, Springer, Berlin (2013).https://doi.org/10.1007/978-3-642-38896-5Google Scholar
  6. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings, Springer, New York (2009).https://doi.org/10.1007/978-0-387-87821-8Google Scholar
  7. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  8. D. Klatte, B. Kummer: Nonsmooth Equations in Optimization, Kluwer, Dordrecht (2002).Google Scholar
  9. D. Klatte, B. Kummer: Aubin property and uniqueness of solutions in cone constrained optimization, Math. Meth. Oper. Res. 77 (2013) 291–304.https://doi.org/10.1007/s00186-013-0429-6Google Scholar
  10. O. L. Mangasarian, T.- H. Shiau: Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems, SIAM J. Control Optim. 25 (1987) 583–595.https://doi.org/10.1137/0325033Google Scholar
  11. B. Mordukhovich: Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctions, Trans. Amer. Math. Soc. 340 (1993) 1–35.https://doi.org/10.1090/S0002-9947-1993-1156300-4Google Scholar
  12. J. Renegar: Some perturbation theory for linear programming, Math. Program. 65 (1994) 73–91.https://doi.org/10.1007/BF01581690Google Scholar
  13. J. Renegar: Linear programming, complexity theory and elementary functional analysis, Math. Program. 70 (1995) 279–351.https://doi.org/10.1007/BF01585941Google Scholar
  14. S. M. Robinson: A characterization of stability in linear programming, Oper. Res. 25 (1977) 435–447.https://doi.org/10.1287/opre.25.3.435Google Scholar
  15. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  16. T. Zolezzi: On the distance theorem in quadratic optimization, J. Convex Analysis 9 (2002) 693–700.https://doi.org/10.68381/jca09040Google Scholar
  17. T. Zolezzi: Condition number theorems in optimization, SIAM J. Optim. 14 (2003) 507–516.https://doi.org/10.1137/S1052623402411885Google Scholar
  18. T. Zolezzi: Condition number theorems in linear-quadratic optimization, Numer. Funct. Anal. Optim. 32 (2011) 1381–1404.https://doi.org/10.1080/01630563.2011.594369Google Scholar
  19. T. Zolezzi: A condition number theorem in convex programming, Math. Program. 149 (2015) 195–207.https://doi.org/10.1007/s10107-014-0745-5Google Scholar

Suggested citation

T. Zolezzi. “A Condition Number Theorem in Convex Programming without Uniqueness.” Journal of Convex Analysis 23 (2016), No. 4, 1247–1262. https://doi.org/10.68381/jca23047

Download BibTeXPublished by Heldermann Verlag.

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