Abstract

A condition number of mathematical programming problems is defined as a measure of the sensitivity of their global optimal solutions under general perturbations described by parameters acting on their data. A (pseudo-) distance among problems fulfilling prescribed bounds is defined via the corresponding augmented Kojima functions. A characterisation of well-conditioning is obtained. It is shown that the distance to ill-conditioning is bounded from above by a multiple of the reciprocal of the condition number. This upper bound extends to general perturbed problems known results dealing with canonical perturbations.

Author information

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

Keywords

  • Condition number
  • condition number theorem
  • mathematical programming with data perturbations

Mathematics Subject Classification

90C30, 90C31

References

  1. M. Bianchi, G. Kassay, R. Pini: Conditioning for optimization problems under general perturbations, Nonlin. Analysis 75 (2013) 37–45.https://doi.org/10.1016/j.na.2011.07.061Google Scholar
  2. M. Bianchi, E. Miglierina, E. Molho, R. Pini: Some results on condition numbers in convex multiobjective optimization, Set-Valued Var. Analysis 21 (2013) 47–65.https://doi.org/10.1007/s11228-012-0207-2Google Scholar
  3. 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
  4. P. Bürgisser, F. Cucker: Condition, Springer, Berlin (2013).https://doi.org/10.1007/978-3-642-38896-5Google Scholar
  5. M. J. Cánovas, A. Hantoute, M. A. López, J. Parra: Lipschitz modulus in convex semi-infinite optimization via d.c. functions, ESAIM: Control Optim. Calc. Var. 15 (2009) 763–781.https://doi.org/10.1051/cocv:2008052Google Scholar
  6. A. L. Dontchev, R. T. Rockafellar: Characterizations of Lipschitzian stability in nonlinear programming, Lecture Notes in Pure Appl. Math. 195, Dekker, New York (1998), 65-82.https://doi.org/10.1201/9781003072119-4Google Scholar
  7. 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
  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. Oper. Res. 77 (2013) 291–304.https://doi.org/10.1007/s00186-013-0429-6Google Scholar
  10. A. B. Levy, R. A. Poliquin, R. T. Rockafellar: Stability of locally optimal solutions, SIAM J. Optim. 10 (2000) 580–604.https://doi.org/10.1137/S1052623498348274Google 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. Programming 65 (1994) 73–91.https://doi.org/10.1007/BF01581690Google Scholar
  13. J. Renegar: Linear programming, complexity theory and elementary functional analysis, Math. Programming 70 (1995) 279–351.https://doi.org/10.1007/BF01585941Google Scholar
  14. R. T. Rockafellar: Lipschitzian stability in optimization: the role of nonsmooth analysis, Lecture Notes Econ. Math. Systems 255, Springer, Berlin (1985) 55–73.https://doi.org/10.1007/978-3-662-12603-5_6Google Scholar
  15. T. Zolezzi: On the distance theorem in quadratic optimization, J. Convex Analysis 9 (2002) 693–700.https://doi.org/10.68381/jca09040Google Scholar
  16. T. Zolezzi: Condition number theorems in optimization, SIAM J. Optim. 14 (2003) 507–516.https://doi.org/10.1137/S1052623402411885Google Scholar
  17. 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
  18. T. Zolezzi: A condition number theorem in convex programming, Math. Programming, Ser. A 149 (2015) 195–207.https://doi.org/10.1007/s10107-014-0745-5Google Scholar
  19. T. Zolezzi: A condition number theorem in convex programming without uniqueness, J. Convex Analysis 23 (2016) 1247–1262.https://doi.org/10.68381/jca23047Google Scholar
  20. T. Zolezzi: On condition number theorems in mathematical programming, J. Optim. Theory Appl. 175 (2017) 597–623.https://doi.org/10.1007/s10957-017-1191-3Google Scholar

Suggested citation

T. Zolezzi. “A Partial Condition Number Theorem in Mathematical Programming.” Journal of Convex Analysis 27 (2020), No. 2, 777–790. https://doi.org/10.68381/jca27039

Download BibTeXPublished by Heldermann Verlag.

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