×
Stein, O.

On constraint qualifications in nonsmooth optimization. (English) Zbl 1062.49014

J. Optimization Theory Appl. 121, No. 3, 647-671 (2004).
Summary: 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.

Cited in 21 Documents

MSC:

49J52 Nonsmooth analysis
90C34 Semi-infinite programming
90C46 Optimality conditions and duality in mathematical programming

Keywords:

nonsmooth optimization; optimality conditions; Slater condition; constraint qualifications; reverse-convex problems; semi-infinite programming
Cite Review PDF
Full Text: DOI

References:

[1] Merkovsky, R. R., and Ward, D. E., General Constraint Qualifications in Nondifferentiable Programming, Mathematical Programming, Vol. 47, pp. 389–405, 1990. · Zbl 0708.90078 · doi:10.1007/BF01580871
[2] Ward, D. E., A Constraint Qualification in Quasidifferentiable Programming, Optimization, Vol. 22, pp. 661–668, 1991. · Zbl 0741.90069 · doi:10.1080/02331939108843709
[3] Kuntz, L., and Scholtes, S., Constraint Qualifications is in Quasidifferentiable Optimization, Mathematical Programming, Vol. 60, pp. 339–347, 1993. · Zbl 0784.90080 · doi:10.1007/BF01580618
[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. · Zbl 0810.90136 · doi:10.1007/BF02193099
[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. · Zbl 0842.90109
[7] Laurent, P. J., Approximation et Optimization, Hermann, Paris, France, 1972.
[8] Bonnans, J. F., and Shapiro, A., Perturbation Analysis of Optimization Problems, Springer, New York, NY, 2000. · Zbl 0966.49001
[9] Hettich, R., and Zencke, P., Numerische Methoden der Approximation und Semi-Infiniten Optimierung, Teubner, Stuttgart, Germany, 1982. · Zbl 0481.65033
[10] Stein, O., Bilevel Strategies in Semi-Infinite Programming, Kluwer Academic Publishers, Boston, MA, 2003. · Zbl 1103.90094
[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. · Zbl 0149.16701 · doi:10.1016/0022-247X(67)90163-1
[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. · doi:10.1137/1015075
[14] Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[15] Guddat, J., Jongen, H. T., Structural Stability in Nonlinear Optimization, Optimization, Vol. 18, pp. 617–631, 1987. · Zbl 0638.90093 · doi:10.1080/02331938708843275
[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. · Zbl 0621.49016 · doi:10.1017/S033427000000518X
[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. · Zbl 0807.90113 · doi:10.1007/BF00939841
[18] Rockafellar, R. T., and Wets, R. J. B., Variational Analysis, Springer, Berlin, Germany, 1998 · Zbl 0888.49001
[19] Berge, C., Topological Spaces, Oliver and Boyd, Edinburgh, Scotland, 1963. · Zbl 0114.38602
[20] Hogan, W. W., Point-to-Set Maps in Mathematical Programming, SIAM Review, Vol. 15, pp. 591–603, 1973. · Zbl 0256.90042 · doi:10.1137/1015073
[21] Gould, F. J., and Tolle, J. W., Geometry of Optimality Conditions and Constraint Qualifications, Mathematical Programming, Vol. 2, pp. 1–18, 1972. · Zbl 0288.90068 · doi:10.1007/BF01584534
[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. · Zbl 0182.53101 · doi:10.1137/0307016
[23] Wolkowicz, H.,Geometry of Optimality Conditions and Constraint Qualifications: The Convex Case, Mathematical Programming, Vol. 19, pp. 32–60, 1980. · Zbl 0436.90082 · doi:10.1007/BF01581627
[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. · Zbl 1073.90562 · doi:10.1287/moor.26.3.565.10583
[25] Cheney, E. W., Introduction to Approximation Theory, McGraw-Hill, New York, NY, 1966. · Zbl 0161.25202
[26] Goberna, M. A., and López, M. A., Linear Semi-Infinite Optimization,Wiley, Chichester, England, 1998. · Zbl 0909.90257
[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.
[28] Hettich, R., and Kortanek, K. O., Semi-Infinite Programming: Theory, Methods and Applications, SIAM Review, Vol. 35, pp. 380–429, 1993. · Zbl 0784.90090 · doi:10.1137/1035089
[29] Danskin, J. M., The Theory of Max-Min and Its Applications to Weapons Allocation Problems, Springer, New York, NY, 1967. · Zbl 0154.20009
[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.
[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 · Zbl 0344.90029
[32] Lempio, F., and Maurer, H., Differential Stability in Infinite-Dimensional Nonlinear Programming, Applied Mathematics and Optimization, Vol. 6, pp. 139–152, 1980. · Zbl 0426.90072 · doi:10.1007/BF01442889
[33] Borwein, J. M., and Lewis, A. S., Partially-Finite Convex Programming, Part 1: Duality Theory, Mathematical Programming, Vol. 57, pp. 15–48, 1992. · Zbl 0778.90049
[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. · Zbl 0778.90050 · doi:10.1007/BF01581073
[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.
[36] Borwein, J. M., and Wolkowicz, H., A Simple Constraint Qualification in Infinite-Dimensional Programming, Mathematical Programming, Vol. 35, pp. 83–96, 1986. · Zbl 0597.90056 · doi:10.1007/BF01589443
[37] Karney, D. F., A Duality Theorem for Semi-Infinite Convex Programs and Their Finite Subprograms, Mathematical Programming, Vol. 27, pp. 75–82, 1983. · Zbl 0527.49027 · doi:10.1007/BF02591965
[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. · Zbl 0999.90045 · doi:10.1137/S1052623499355247
[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. · Zbl 0278.90062 · doi:10.1287/opre.21.1.188
[40] Still, G., Generalized Semi-Infinite Programming: Numerical Aspects, Optimization, Vol. 49, pp. 223–242, 2001. · Zbl 1039.90083 · doi:10.1080/02331930108844531
[41] Gauvin, J., and Dubeau, F., Differential Properties of the Marginal Function in Mathematical Programming, Mathematical Programming Study, Vol. 19, pp. 101–119, 1982. · Zbl 0502.90072 · doi:10.1007/BFb0120984
[42] Kyparisis, J., On Uniqueness of Kuhn-Tucker Multipliers in Nonlinear Programming, Mathematical Programming, Vol. 32, pp. 242–246, 1985. · Zbl 0566.90085 · doi:10.1007/BF01586095
[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. · Zbl 0553.49019 · doi:10.1007/BFb0121211
[44] Gauvin, J., and Tolle, J. W., Differential Stability in Nonlinear Programming, SIAM Journal on Control and Optimization, Vol. 15, pp. 294–311, 1977 · Zbl 0374.90062 · doi:10.1137/0315020
[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. · Zbl 0964.90047 · doi:10.1023/A:1004622015901
[46] Weber, G. W., Structural Stability in Generalized Semi-Infinite Optimization, Vychislitel’nye Tekhnologii, Vol. 6, pp. 25–46, 2001. · Zbl 0997.90089
[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. · Zbl 0956.90055 · doi:10.1023/A:1021746305759
[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 · Zbl 0949.90090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.