Abstract

The optimization of convex quadratic forms on Banach spaces is considered. A suitable notion of conditioning under linear perturbations leads to the distance theorem in the free case, thereby extending to the optimization setting the classical Eckart-Young formula: the distance to ill-conditioning equals to the reciprocal of the condition number. Partial results are presented for the linearly constrained case.

Author information

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

T. Zolezzi

Dip. di Matematica, Università di Genova, Via Dodecaneso 35, 16146 Genova, Italy

zolezzi@dima.unige.it

Keywords

  • Conditioning
  • distance theorem
  • condition number theorem
  • convex optimization

Mathematics Subject Classification

49K40

References

  1. J. F. Bonnans, A. Shapiro: Perturbation Analysis of Optimization Problems, Springer (2000).https://doi.org/10.1007/978-1-4612-1394-9Google Scholar
  2. H. Brezis: Analyse Fonctionelle, Masson (1983).Google Scholar
  3. J.-P. Dedieu: Approximate solutions of numerical problems, condition number analysis and the condition number theorem, Lectures in Appl. Math. 32, Amer. Math. Soc. (1996) 263–283.https://doi.org/10.1016/S0024-3795(96)00366-7Google Scholar
  4. J. W. Demmel: On condition numbers and the distance to the nearest ill-posed problem, Numerische Math. 51 (1987) 251–289.https://doi.org/10.1007/BF01400115Google Scholar
  5. N. Dunford, J. Schwartz: Linear Operators, part I, Interscience (1958).Google Scholar
  6. C. Eckart, G. Young: The approximation of one matrix by another of lower rank, Psychometrika 1 (1936) 211–218.https://doi.org/10.1007/BF02288367Google Scholar
  7. W. Kahan: Numerical linear algebra, Canad. Math. Bull. 9 (1966) 757–801.https://doi.org/10.4153/CMB-1966-083-2Google Scholar
  8. T. Kato: Perturbation Theory for Linear Operators, Springer (1966).https://doi.org/10.1007/978-3-642-53393-8Google Scholar
  9. A. S. Lewis: Ill-conditioned convex processes and conic linear systems (preprint).Google Scholar
  10. J. Renegar: Linear programming, complexity theory and elementary functional analysis, Math. Programming 70 (1995) 279–351.https://doi.org/10.1007/BF01585941Google Scholar
  11. J. Renegar: Incorporating condition measures into the complexity theory of linear programming, SIAM J. Optim. 5 (1995) 506–524.https://doi.org/10.1137/0805026Google Scholar

Suggested citation

T. Zolezzi. “On the Distance Theorem in Quadratic Optimization.” Journal of Convex Analysis 9 (2002), No. 2, 693–700. https://doi.org/10.68381/jca09040

Download BibTeXPublished by Heldermann Verlag.

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