# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
The generalized Mangasarian-Fromowitz constraint qualification and optimality conditions for bilevel programs. (English) Zbl 1223.90061

The authors introduce a bilevel programming problem in terms of an upper level problem

$minF\left(x,y\right)\phantom{\rule{1.em}{0ex}}\phantom{\rule{4.pt}{0ex}}\text{s.}\phantom{\rule{4.pt}{0ex}}\text{t.}\phantom{\rule{4.pt}{0ex}}\left(x,y\right)\in X×{ℝ}^{m},\phantom{\rule{4pt}{0ex}}y\in {\Psi }\left(x\right)\phantom{\rule{2.em}{0ex}}\left(\mathrm{ULP}\right)$

where $X$ is a closed subset of ${ℝ}^{n}$ and ${\Psi }\left(x\right)$ is the solution set of the lower level problem defined as:

$minf\left(x,y\right)\phantom{\rule{1.em}{0ex}}\phantom{\rule{4.pt}{0ex}}\text{s.}\phantom{\rule{4.pt}{0ex}}\text{t.}\phantom{\rule{4.pt}{0ex}}y\in K\left(x\right)·$

The functions $F,f:{ℝ}^{n}×{ℝ}^{m}\to ℝ$ are continuous, $X=\left\{x\mid G\left(x\right)\le 0,H\left(x\right)=0\right\}$, $K\left(x\right)=\left\{y\mid g\left(x,y\right)\le 0,h\left(x,y\right)=0\right\}$, where the functions $G:{ℝ}^{n}\to {ℝ}^{k}$, $H:{ℝ}^{n}\to {ℝ}^{l}$, $g:{ℝ}^{n}×{ℝ}^{m}\to {ℝ}^{p}$, $h:{ℝ}^{n}×{ℝ}^{m}\to {ℝ}^{q}$ are all continuous. Assuming feasibility of (ULP) the optimal value reformulation is

$minF\left(x,y\right)\phantom{\rule{1.em}{0ex}}\phantom{\rule{4.pt}{0ex}}\text{s.}\phantom{\rule{4.pt}{0ex}}\text{t.}\phantom{\rule{4.pt}{0ex}}x\in X,\phantom{\rule{4pt}{0ex}}y\in K\left(x\right),\phantom{\rule{4pt}{0ex}}f\left(x,y\right)\le \phi \left(x\right)\phantom{\rule{2.em}{0ex}}\left(\mathrm{OV}\right)$

where $\phi \left(x\right)$ is defined as: $\phi \left(x\right)=min\left\{f\left(x,y\right)\mid y\in K\left(x\right)\right\}$.

The authors contend that the problems (ULP) and (OV) are locally and globally equivalent. It is shown that the Mangasarian-Fromowitz constraint qualification in terms of basic generalized differentiation constructions of Mordukhovich fails and a weakened form of the same is used to derive Karush-Kuhn-Tucker optimality conditions for (ULP). They also suggest new sufficient conditions for the partial calmness based on a more general notion of the weak sharp minimum.

##### MSC:
 90C30 Nonlinear programming 90C46 Optimality conditions, duality
##### References:
 [1] Dempe, S., Zemkoho, A.B.: The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Submitted for publication [2] Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic, Dordrecht (2002) [3] Dempe, S., Dutta, J., Lohse, S.: Optimality conditions for bilevel programming problems. Optimization 55, 505–524 (2006) · Zbl 1156.90457 · doi:10.1080/02331930600816189 [4] Dempe, S., Kalashnikov, V.V., Kalashnykova, N.: Optimality conditions for bilevel programming problems. In: Dempe, S., Kalashnikov, V.V. (eds.) Optimization with Multivalued Mappings, vol. 2, pp. 3–28. Springer, New York (2006) [5] Dutta, J., Dempe, S.: Bilevel programming with convex lower level problems. In: Dempe, S., Kalashnikov, V.V. (eds.) Optimization with Multivalued Mappings, vol. 2, pp. 51–71. Springer, New York (2006) [6] Ye, J.J., Zhu, D.L.: Optimality conditions for bilevel programming problems. Optimization 33, 9–27 (1995) · Zbl 0820.65032 · doi:10.1080/02331939508844060 [7] Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM Classics in Applied Mathematics, vol. 5. Wiley, New York (1983). Reprint, Philadelphia (1994) [8] Ye, J.J., Zhu, D.L.: A note on optimality conditions for bilevel programming problems. Optimization 39, 361–366 (1997) · Zbl 0879.90173 · doi:10.1080/02331939708844290 [9] Ye, J.J.: Nondifferentiable multiplier rules for optimization and bilevel optimization problems. SIAM J. Optim. 15, 252–274 (2004) · Zbl 1077.90077 · doi:10.1137/S1052623403424193 [10] Ye, J.J.: Constraint qualifications and KKT conditions for bilevel programming problems. Math. Oper. Res. 31, 811–824 (2006) · Zbl 05279704 · doi:10.1287/moor.1060.0219 [11] Babahadda, H., Gadhi, N.: Necessary optimality conditions for bilevel optimization problems using convexificators. J. Glob. Optim. 34, 535–549 (2006) · Zbl 1090.49021 · doi:10.1007/s10898-005-1650-5 [12] Amahroq, T., Gadhi, N.: On the regularity condition for vector programming problems. J. Glob. Optim. 21, 433–441 (2001) · Zbl 1175.90409 · doi:10.1023/A:1012748412618 [13] Dempe, S., Dutta, J., Mordukhovich, B.S.: New necessary optimality conditions in optimistic bilevel programming. Optimization 56, 577–604 (2007) · Zbl 1172.90481 · doi:10.1080/02331930701617551 [14] Henrion, R., Outrata, J.: A subdifferential condition for calmness of multifunctions. J. Math. Anal. Appl. 258, 110–130 (2001) · Zbl 0983.49010 · doi:10.1006/jmaa.2000.7363 [15] Henrion, R., Jourani, A., Outrata, J.: On the calmness of a class of multifunctions. SIAM J. Optim. 13, 603–618 (2002) · Zbl 1028.49018 · doi:10.1137/S1052623401395553 [16] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation. I: Basic Theory, II: Applications. Springer, Berlin (2006) [17] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998) [18] Zheng, X.Y., Ng, K.F.: Calmness for L-subsmooth multifunctions in Banach spaces. SIAM J. Optim. 19, 1648–1673 (2009) · Zbl 1188.49019 · doi:10.1137/080714129 [19] Mangasarian, O.L., Fromowitz, S.: The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17, 37–47 (1967) · Zbl 0149.16701 · doi:10.1016/0022-247X(67)90163-1 [20] Gauvin, J., Dubeau, F.: Differential properties of the marginal function in mathematical programming. Math. Program. Stud. 18, 101–119 (1982) [21] Mordukhovich, B.S., Nam, N.M.: Variational stability and marginal functions via generalized differentiation. Math. Oper. Res. 30, 800–816 (2005) · Zbl 05279643 · doi:10.1287/moor.1050.0147 [22] Klatte, D., Kummer, B.: Stability properties of infima and optimal solutions of parametric optimization problems. Nondifferentiable optimization: motivations and applications. In: Proc. IIASA Workshop, Sopron/Hung, 1984. Lect. Notes Econ. Math. Syst, vol. 255, pp. 215–229. Springer, Berlin (1985) [23] Rockafellar, R.T.: Lagrange multipliers and optimality. SIAM Rev. 35, 183–238 (1993) · Zbl 0779.49024 · doi:10.1137/1035044 [24] Mangasarian, O.L.: Nonlinear Programming. SIAM Classics in Applied Mathematics, vol. 10. McGraw-Hill, New York (1969). Reprint, Philadelphia (1994) [25] Dempe, S., Dinh, N., Dutta, J.: Optimality conditions for a simple convex bilevel programming problem. In: Burachik, R.S., Yao, J.-C. (eds.) Variational Analysis and Generalized Differentiation in Optimization and Control. Springer, Berlin (2010) [26] Dempe, S., Zemkoho, A.B.: On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem. Submitted for publication [27] Henrion, R., Outrata, J., Surowiec, T.: On the co-derivative of normal cone mappings to inequality systems. Nonlinear Anal. 71, 1213–1226 (2009) · Zbl 1176.90568 · doi:10.1016/j.na.2008.11.089 [28] Moldovan, A., Pellegrini, L.: On regularity for constrained extremum problems. I: Sufficient optimality conditions. J. Optim. Theory Appl. 142, 147–163 (2009) · Zbl 1198.90391 · doi:10.1007/s10957-009-9518-3 [29] Moldovan, A., Pellegrini, L.: On regularity for constrained extremum problems. II: Necessary optimality conditions. J. Optim. Theory Appl. 142, 165–183 (2009) · Zbl 1205.90294 · doi:10.1007/s10957-009-9521-8 [30] Dempe, S., Zemkoho, A.B.: Bilevel road pricing: Theoretical analysis and optimality conditions. Submitted for publication [31] Ye, J.J.: New uniform parametric error bounds. J. Optim. Theory Appl. 98, 197–219 (1998) · Zbl 0908.90248 · doi:10.1023/A:1022649217032 [32] Ye, J.J., Zhu, D.L., Zhu, Q.J.: Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM J. Optim. 7, 481–507 (1997) · Zbl 0873.49018 · doi:10.1137/S1052623493257344 [33] Heerda, J., Kummer, B.: Characterization of calmness for Banach space mappings. Preprint, Humboldt-Universität zu Berlin (2006) [34] Kojima, M.: Strongly stable stationary solutions in nonlinear programs. Analysis and computation of fixed points. Proc. Symp., Univ. Wis. 1979, 93–138 (1980) [35] Ralph, D., Dempe, S.: Directional derivatives of the solution of a parametric nonlinear program. Math. Program. 70, 159–172 (1995) [36] Mordukhovich, B.S.: Generalized differential calculus for nonsmooth and set-valued mappings. J. Math. Anal. Appl. 183, 250–288 (1994) · Zbl 0807.49016 · doi:10.1006/jmaa.1994.1144 [37] Dempe, S., Vogel, S.: The generalized Jacobian of the optimal solution in parametric optimization. Optimization 50, 387–405 (2001) · Zbl 1054.90074 · doi:10.1080/02331930108844570