Skip to main content
SpringerLink
Log in

On Constraint Qualifications in Nonsmooth Optimization

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We introduce extensions of the Mangasarian-Fromovitz and Abadie constraint qualifications to nonsmooth optimization problems with feasibility given by means of lower-level sets. We do not assume directional differentiability, but only upper semicontinuity of the defining functions. By deriving and reviewing primal first-order optimality conditions for nonsmooth problems, we motivate the formulations of the constraint qualifications. Then, we study their interrelation, and we show how they are related to the Slater condition for nonsmooth convex problems, to nonsmooth reverse-convex problems, to the stability of parametric feasible set mappings, and to alternative theorems for the derivation of dual first-order optimality conditions.

In the literature on general semi-infinite programming problems, a number of formally different extensions of the Mangasarian-Fromovitz constraint qualification have been introduced recently under different structural assumptions. We show that all these extensions are unified by the constraint qualification presented here.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Merkovsky, R. R., and Ward, D. E., General Constraint Qualifications in Nondifferentiable Programming, Mathematical Programming, Vol. 47, pp. 389–405, 1990.

    Google Scholar 

  2. Ward, D. E., A Constraint Qualification in Quasidifferentiable Programming, Optimization, Vol. 22, pp. 661–668, 1991.

    Google Scholar 

  3. Kuntz, L., and Scholtes, S., Constraint Qualifications is in Quasidifferentiable Optimization, Mathematical Programming, Vol. 60, pp. 339–347, 1993.

    Google Scholar 

  4. Demyanov, V. F., and Rubinov, A. M., Quasidifferential Calculus, Optimization Software, New York, NY, 1986.

  5. Jourani, A., Constraint Qualifications and Lagrange Multipliers in Nondifferentiable Programming Problems, Journal of Optimization Theory and Applications, Vol. 81, pp. 533–548, 1994.

    Google Scholar 

  6. Kuntz, L., and Scholtes, S.,ANonsmooth Variant of the Mangasarian-Fromovitz Constraint Qualification, Journal of Optimization Theory and Applications, Vol. 82, pp. 59–75, 1994.

    Google Scholar 

  7. Laurent, P. J., Approximation et Optimization, Hermann, Paris, France, 1972.

    Google Scholar 

  8. Bonnans, J. F., and Shapiro, A., Perturbation Analysis of Optimization Problems, Springer, New York, NY, 2000.

    Google Scholar 

  9. Hettich, R., and Zencke, P., Numerische Methoden der Approximation und Semi-Infiniten Optimierung, Teubner, Stuttgart, Germany, 1982.

    Google Scholar 

  10. Stein, O., Bilevel Strategies in Semi-Infinite Programming, Kluwer Academic Publishers, Boston, MA, 2003.

    Google Scholar 

  11. Mangasarian, O. L., and Fromovitz, S., The Fritz John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints, Journal of Mathematical Analysis and Applications, Vol. 17, pp. 37–47, 1967.

    Google Scholar 

  12. Abadie, J. M., On the Kuhn-Tucker Theorem, Nonlinear Programming, Edited by J. Abadie, North Holland, Amsterdam, Holland, pp. 19–36, 1967 JOTA: VOL. 121, NO. 3, JUNE 2004 669

  13. Peterson, D. W., A Review of Constraint Qualifications in Finite-Dimensional Spaces, SIAM Review, Vol. 15, pp. 639–654, 1973.

    Google Scholar 

  14. Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.

    Google Scholar 

  15. Guddat, J., Jongen, H. T., Structural Stability in Nonlinear Optimization, Optimization, Vol. 18, pp. 617–631, 1987.

    Google Scholar 

  16. Guddat, J., Jongen, H. T., and Rückmann, J. J., On Stability and Stationary Points in Nonlinear Optimization, Journal of the Australian Mathematical Society, Vol. 28B, pp. 36–56, 1986.

    Google Scholar 

  17. Jongen, H. T., Twilt, F., and Weber, G. W., Semi-Infinite Optimization: Structure and Stability of the Feasible Set, Journal of Optimization Theory and Applications, Vol. 72, pp. 529–552, 1992.

    Google Scholar 

  18. Rockafellar, R. T., and Wets, R. J. B., Variational Analysis, Springer, Berlin, Germany, 1998

    Google Scholar 

  19. Berge, C., Topological Spaces, Oliver and Boyd, Edinburgh, Scotland, 1963.

    Google Scholar 

  20. Hogan, W. W., Point-to-Set Maps in Mathematical Programming, SIAM Review, Vol. 15, pp. 591–603, 1973.

    Google Scholar 

  21. Gould, F. J., and Tolle, J. W., Geometry of Optimality Conditions and Constraint Qualifications, Mathematical Programming, Vol. 2, pp. 1–18, 1972.

    Google Scholar 

  22. Guignard, M., Generalized Kuhn-Tucker Conditions for Mathematical Programming Problems in a Banach Space, SIAM Journal on Control, Vol. 7, pp. 232–241, 1969.

    Google Scholar 

  23. Wolkowicz, H.,Geometry of Optimality Conditions and Constraint Qualifications: The Convex Case, Mathematical Programming, Vol. 19, pp. 32–60, 1980.

    Google Scholar 

  24. Stein, O., First-Order Optimality Conditions for Degenerate Index Sets in Generalized Semi-Infinite Programming, Mathematics of Operations Research, Vol. 26, pp. 565–582, 2001.

    Google Scholar 

  25. Cheney, E. W., Introduction to Approximation Theory, McGraw-Hill, New York, NY, 1966.

    Google Scholar 

  26. Goberna, M. A., and López, M. A., Linear Semi-Infinite Optimization,Wiley, Chichester, England, 1998.

    Google Scholar 

  27. John, F., Extremum Problems with Inequalities as Subsidiary Conditions, Studies and Essays, R. Courant Anniversary Volume, Interscience, New York, NY, pp. 187–204, 1948.

    Google Scholar 

  28. Hettich, R., and Kortanek, K. O., Semi-Infinite Programming: Theory, Methods and Applications, SIAM Review, Vol. 35, pp. 380–429, 1993.

    Google Scholar 

  29. Danskin, J. M., The Theory of Max-Min and Its Applications to Weapons Allocation Problems, Springer, New York, NY, 1967.

    Google Scholar 

  30. Guerra vasquez, F., and Orozco, J. A., On Constraint Qualifications in Semi-Infinite Optimization, Preprint, Departamento de Física y Matemáticas, Escuela de Ciencias, Universidad de las Américas, Puebla, Mexico, 2001.

    Google Scholar 

  31. Kuhn, H. W., Nonlinear Programming: A Historical View, Nonlinear Programming, Edited by R. W. Cottle and C. E. Lemke, American Mathematical Society, Providence, Rhode Island, pp. 1–26, 1976. 670 JOTA: VOL. 121, NO. 3, JUNE 2004

    Google Scholar 

  32. Lempio, F., and Maurer, H., Differential Stability in Infinite-Dimensional Nonlinear Programming, Applied Mathematics and Optimization, Vol. 6, pp. 139–152, 1980.

    Google Scholar 

  33. Borwein, J. M., and Lewis, A. S., Partially-Finite Convex Programming, Part 1: Duality Theory, Mathematical Programming, Vol. 57, pp. 15–48, 1992.

    Google Scholar 

  34. Borwein, J. M., and Lewis, A. S., Partially-Finite Convex Programming, Part 2: Explicit Lattice Models, Mathematical Programming, Vol. 57, pp. 49–84, 1992.

    Google Scholar 

  35. Borwein, J. M., and Wolkowicz, H., Characterization of Optimality for the Abstract Convex Program with Finite-Dimensional Range, Journal of the Australian Mathematical Society, Vol. 30A, pp. 390–411, 1980/81.

    Google Scholar 

  36. Borwein, J. M., and Wolkowicz, H., A Simple Constraint Qualification in Infinite-Dimensional Programming, Mathematical Programming, Vol. 35, pp. 83–96, 1986.

    Google Scholar 

  37. Karney, D. F., A Duality Theorem for Semi-Infinite Convex Programs and Their Finite Subprograms, Mathematical Programming, Vol. 27, pp. 75–82, 1983.

    Google Scholar 

  38. Li, W., Nahak, C., and Singer, I., Constraint Qualifications for Semi-Infinite Systems of Convex Inequalities, SIAM Journal on Optimization, Vol. 11, pp. 31–52, 2000.

    Google Scholar 

  39. Hogan, W. W., Directional Derivatives for Extremal Value Functions with Applications to the Completely Convex Case, Operations Research, Vol. 21, pp. 188–209, 1973.

    Google Scholar 

  40. Still, G., Generalized Semi-Infinite Programming: Numerical Aspects, Optimization, Vol. 49, pp. 223–242, 2001.

    Google Scholar 

  41. Gauvin, J., and Dubeau, F., Differential Properties of the Marginal Function in Mathematical Programming, Mathematical Programming Study, Vol. 19, pp. 101–119, 1982.

    Google Scholar 

  42. Kyparisis, J., On Uniqueness of Kuhn-Tucker Multipliers in Nonlinear Programming, Mathematical Programming, Vol. 32, pp. 242–246, 1985.

    Google Scholar 

  43. Gauvin, J., and Dubeau, F., Some Examples and Counterexamples for the Stability Analysis of Nonlinear Programming Problems, Mathematical Programming Study, Vol. 21, pp. 69–78, 1983.

    Google Scholar 

  44. Gauvin, J., and Tolle, J. W., Differential Stability in Nonlinear Programming, SIAM Journal on Control and Optimization, Vol. 15, pp. 294–311, 1977

    Google Scholar 

  45. Stein, O., and Still, G., On Optimality Conditions for Generalized Semi-Infinite Programming Problems, Journal of Optimization Theory and Applications, Vol. 104, pp. 443–458, 2000.

    Google Scholar 

  46. Weber, G. W., Structural Stability in Generalized Semi-Infinite Optimization, Vychislitel'nye Tekhnologii, Vol. 6, pp. 25–46, 2001.

    Google Scholar 

  47. Rückmann, J. J., and Shapiro, A., First-Order Optimality Conditions in Generalized Semi-Infinite Programming, Journal of Optimization Theory and Applications, Vol. 101, pp. 677–691, 1999.

    Google Scholar 

  48. Jongen, H. T., Rückmann, J. J., and Stein, O., Generalized Semi-Infinite Optimization: A First Order Optimality Condition and Examples, Mathematical Programming, Vol. 83, pp. 145–158, 1998. JOTA: VOL. 121, NO. 3, JUNE 2004 671

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, RWTH Aachen University, Aachen, Germany

    O. Stein

Authors
  1. O. Stein
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Stein, O. On Constraint Qualifications in Nonsmooth Optimization. Journal of Optimization Theory and Applications 121, 647–671 (2004). https://doi.org/10.1023/B:JOTA.0000037607.48762.45

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:JOTA.0000037607.48762.45

Search

Navigation