×

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 \[ \min F(x, y) \quad\text{ s. t. } (x, y)\in X \times \mathbb R^m,\;y \in\Psi(x)\tag{ULP} \] where \(X\) is a closed subset of \(\mathbb R^n\) and \(\Psi(x)\) is the solution set of the lower level problem defined as: \[ \min f(x, y)\quad\text{ s. t. }y \in K(x). \] The functions \(F, f : \mathbb R^n \times \mathbb R^m \to\mathbb R\) are continuous, \(X = \{ x \mid G(x) \leq 0, H(x) = 0\}\), \(K(x) = \{ y\mid g(x, y) \leq 0, h(x, y) = 0\}\), where the functions \(G : \mathbb R^n \to \mathbb R^k\), \(H : \mathbb R^n \to \mathbb R^l\), \(g : \mathbb R^n\times \mathbb R^m \to \mathbb R^p\), \(h : \mathbb R^n \times \mathbb R^m \to \mathbb R^q\) are all continuous. Assuming feasibility of (ULP) the optimal value reformulation is \[ \min F(x, y)\quad \text{ s. t. } x \in X, \;y\in K(x),\;f(x, y) \leq \phi(x)\tag{OV} \] where \(\phi(x)\) is defined as: \(\phi(x) = \min \{ f(x, y) \mid y \in K(x)\}\).
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.
Reviewer: R. N. Kaul (Delhi)

MSC:

90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Dempe, S., Zemkoho, A.B.: The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Submitted for publication · Zbl 1272.90086
[2] Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic, Dordrecht (2002) · Zbl 1038.90097
[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) · Zbl 1140.90049
[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) · Zbl 1133.90015
[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) · Zbl 0582.49001
[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 1278.90437 · 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) · Zbl 0502.90072
[21] Mordukhovich, B.S., Nam, N.M.: Variational stability and marginal functions via generalized differentiation. Math. Oper. Res. 30, 800–816 (2005) · Zbl 1284.90083 · 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) · Zbl 1220.90090
[26] Dempe, S., Zemkoho, A.B.: On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem. Submitted for publication · Zbl 1254.90222
[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 · Zbl 1274.90374
[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) · Zbl 0844.90089
[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
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.