Abstract

Given a convex program with C2C^2 functions and a convex set S of solutions to the problem, we give a second order condition which guarantees that the problem does not have solutions outside of S. This condition is interpreted as a characterization for the quadratic growth of the cost function. The crucial role in the proofs is played by a theorem describing a certain uniform regularity property of critical cones in smooth convex programs. We apply these results to the discussion of stability of solutions of a convex program under possibly nonconvex perturbations.

Author information

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

J. Frédéric Bonnans

INRIA-Rocquencourt, Domaine de Voluceau, B.P. 105, 78153 Rocquencourt, France.

Alexander D. Ioffe

Department of Mathematics, Technion Israel Institute of Technology, Haifa 3200 - Israel.

Keywords

  • Convexity
  • Lagrangian
  • composite functions
  • critical cone
  • quadratic growth
  • stability
  • multiple solutions

References

  1. A. Auslender, R. Cominetti: First and second order sensitivity analysis of nonlinear programs under directional constraint qualification condition. Optimization 21, 1990, 351–363.https://doi.org/10.1080/02331939008843555Google Scholar
  2. J.F. Bonnans, A.D. Ioffe: Second-order sufficiency and quadratic growth for non isolated minima. Inria Report 1853. Mathematics of Operations Research, 1993, to appear.Google Scholar
  3. J.F. Bonnans, A.D. Ioffe, A. Shapiro: Expansion of exact and approximate solutions in nonlinear programming. In Lecture Notes in Economics and Mathematical Systems 382, W. Oettli and P. Pallaschke eds., Springer Verlag, 1993, 103–117.https://doi.org/10.1007/978-3-642-51682-5_8Google Scholar
  4. J.F. Bonnans, A.D. Ioffe, A. Shapiro: Développement de solutions exactes et approchées en programmation non linéaire. Comptes Rendus Acad. Sci. Paris Ser. I, 1992, 119–123.Google Scholar
  5. J. Gauvin, R. Janin: Directional behavior of optimal solutions in nonlinear mathematical programming. Mathematics of Operation Research 13, 1988, 629–649.https://doi.org/10.1287/moor.13.4.629Google Scholar
  6. E.G. Gol’stein: Theory of convex programming. Nauka, Moscow, 1970; Transl. Math. Monographs 36, Amer. Mathematics Soc., Providence, R.I., 1972.Google Scholar
  7. A. Hoffmann: On approximate solutions of systems of inequalities, J. Res. National Bureau Standards, Sect. B 49, 1952, 263–265.https://doi.org/10.6028/jres.049.027Google Scholar
  8. A.D. Ioffe: Necessary and sufficient conditions for a local minimum. SIAM J. Control Optimization 17, 1979, 245–288.https://doi.org/10.1137/0317021Google Scholar
  9. A.D. Ioffe: Variational analysis of a composite function : a formula for the lower second order epi-derivative, Mathematics of Analysis Applications 160, 1991, 379–405.https://doi.org/10.1016/0022-247X(91)90312-NGoogle Scholar
  10. A.D. Ioffe: On sensitivity analysis of nonlinear program in Banach spaces : the approach via composite unconstrained optimization, SIAM J. Optimization, 4, 1994, 1–43.https://doi.org/10.1137/0804001Google Scholar
  11. E.S. Levitin, A.A. Miljutin, N.P. Osmolowski: On conditions for a local minimum in problems with constraints, in Mathematical Economics and Functional Analysis, B.S. Mitiagin ed., Nauka, Moscow, 1974, 139–202 (In Russian).Google Scholar
  12. O.L. Mangasarian: A simple characterization of solution sets of convex programs. Oper. Res. Letters 7, 1988, 21–26https://doi.org/10.1016/0167-6377(88)90047-8Google Scholar
  13. S.M. Robinson: Stability theory for systems of inequalities, part 2, SIAM J. Numerical Analysis, 13, 1976, 487–513.https://doi.org/10.1137/0713043Google Scholar
  14. R.T. Rockafellar: Convex Analysis, Princeton University Press 1970.https://doi.org/10.1515/9781400873173Google Scholar
  15. A. Shapiro: Sensitivity analysis of nonlinear programs and differentiability properties of metric projections. SIAM J. Control Optimization 26, 1988, 628–645.https://doi.org/10.1137/0326037Google Scholar
  16. A. Shapiro: Perturbation theory of nonlinear programs when the set of solution is not a singleton. J. Applied Mathematics of Optimization 18, 1988, 215–229.https://doi.org/10.1007/BF01443623Google Scholar
  17. A. Shapiro: Perturbation analysis of optimization problems in Banach spaces. Numerical Functional Analysis and Optimization 13, 1992, 97–116.https://doi.org/10.1080/01630569208816463Google Scholar
  18. D. Klatte: On quantitative stability for non-isolated minima. Control and Cybernetics 23, 1994.Google Scholar

Suggested citation

J. F. Bonnans, A. D. Ioffe. “Quadratic Growth and Stability in Convex Programming Problems with Multiple Solutions.” Journal of Convex Analysis 2 (1995), No. 1&2, 41–57. https://doi.org/10.68381/jca02003

Download BibTeXPublished by Heldermann Verlag.

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