×

zbMATH — the first resource for mathematics

Necessary optimality conditions for bilevel set optimization problems. (English) Zbl 1190.90178
Summary: Bilevel programming problems are hierarchical optimization problems where in the upper level problem a function is minimized subject to the graph of the solution set mapping of the lower level problem. In this paper necessary optimality conditions for such problems are derived using the notion of a convexificator by Luc and Jeyakumar. Convexificators are subsets of many other generalized derivatives. Hence, our optimality conditions are stronger than those using e.g., the generalized derivative due to Clarke or Michel-Penot. Using a certain regularity condition Karush-Kuhn-Tucker conditions are obtained.

MSC:
90C29 Multi-objective and goal programming
90C46 Optimality conditions and duality in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amahroq T. and Gadhi N. (2003). Second order optimality conditions for an extremal problem under inclusion constraints. J. Math. Anal. Appl. 285: 74–85 · Zbl 1029.49014 · doi:10.1016/S0022-247X(03)00399-8
[2] Amahroq, T., Gadhi, N., Riahi, H.: Epi-differentiability and optimality conditions for an extremal problem. J. Inequal. Pure Appl. Math., Victoria University, ISSN electronic 1443–5756 4(2) Article 41 (2003) · Zbl 1126.49306
[3] Babahadda, H., Gadhi, N.: Necessary optimality conditions for bilevel optimization problems using convexificators (To appear) in J. Global. Optim. · Zbl 1090.49021
[4] Bard J.F. (1991). Some properties of the bilevel programming problem. J. Optim. Theory Appl. 68: 371–378 · Zbl 0696.90086 · doi:10.1007/BF00941574
[5] Bank B., Guddat J., Klatte D., Kummer B. and Tammer K. (1982). Nonlinear Parametric Optimization. Akademie-Verlag, Berlin · Zbl 0502.49002
[6] Chanas S., Delgado M., Verdegay J.L. and Vila M.A. (1993). Interval and fuzzy extensions of classical transportation problems. Transport. Plan. Technol. 17: 203–218 · Zbl 0778.94013 · doi:10.1080/03081069308717511
[7] Chen, Y., Florian, M.: On the geometry structure of linear bilevel programs: A dual approach, Technical Report CRT-867, Centre de Recherche sur les transports. Université de Montreal, Montreal, Quebec, Canada (1992)
[8] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley-Interscience (1983) · Zbl 0582.49001
[9] Clarke, F.H.: Necessary conditions for a general control problem in calculus of variations and control. In: Russel D. (ed.) Mathematics research center, Pub.36. University of Wisconsin, pp. 259–278, New York Academy (1976)
[10] Craven B.D., Ralph D. and Glover B.M. (1995). Small convex-valued subdifferentials in mathematical programming. Optimization 32: 1–21 · Zbl 0816.49007 · doi:10.1080/02331939508844032
[11] Dantzig G.B., Folkman J. and Shapiro N. (1967). On the continuity of the minimum set of a continuous function. J. Math. Anal. Appl. 17: 512–548 · Zbl 0153.49201 · doi:10.1016/0022-247X(67)90139-4
[12] Demyanov V.F. and Jeyakumar V. (1997). Hunting for a smaller convex subdifferential. J. Global Optim. 10: 305–326 · Zbl 0872.90083 · doi:10.1023/A:1008246130864
[13] Dempe S. (1992). A necessary and a sufficient optimality condition for bilevel programming problems. Optimization 25: 341–354 · Zbl 0817.90104 · doi:10.1080/02331939208843831
[14] Dempe S. (2002). Foundations of Bilevel Programming. Kluwer Academie Publishers, Dordrecht · Zbl 1038.90097
[15] Dempe S. (1997). First-order necessary optimality conditions for general bilevel programming problems. J. Optim. Theory Appl. 95: 735–739 · Zbl 0903.90148 · doi:10.1023/A:1022646611097
[16] Dempe S. and Schmidt H. (1996). On an algorithm solving two-level programming problems with nonunique lower level solutions. Comput. Optim. Appl. 6: 227–249 · Zbl 0858.90116
[17] Dien P.H. (1983). Locally Lipschitzian set-valued maps and general extremal problems with inclusion constraints. Acta. Math. Vietnam. 1: 109–122 · Zbl 0563.49017
[18] Dien P.H. (1985). On the regularity condition for the extremal problem under locally Lipschitz inclusion constraints. Appl. Math. Appl. 13: 151–161 · Zbl 0589.49017
[19] Ekeland I. (1974). On the variational principle. J. Math. Anal. Appl. 47: 324–353 · Zbl 0286.49015 · doi:10.1016/0022-247X(74)90025-0
[20] Gadhi N. (2005). Necessary optimality conditions for Lipschitz multiobjective optimization problems. Georgian Math. J. 12: 65–74 · Zbl 1139.90418
[21] Huang H.X. and Pardalos P.M. (2002). A multivariate partition approach to optimization problems. Cybernet. Syst. Anal. 38: 265–275 · Zbl 1033.90127 · doi:10.1023/A:1016351614255
[22] Ioffe A.D. (1989). Approximate subdifferential and applications.. III : the metric theory. Mathematika 36: 1–38 · Zbl 0713.49022
[23] Jahn J. (2004). Vector optimization. Springer, Berlin · Zbl 1055.90065
[24] Jahn J. and Rauh R. (1997). Contingent epiderivatives and set-valued optimization. Math. Method. Oper. Res. 46: 193–211 · Zbl 0889.90123 · doi:10.1007/BF01217690
[25] Jeyakumar V. and Luc D.T. (1998). Approximate Jacobian matrices for continuous maps and C1-Optimization. SIAM J. Control Optim. 36: 1815–1832 · Zbl 0923.49012 · doi:10.1137/S0363012996311745
[26] Jeyakumar V., Luc D.T. and Schaible S. (1998). Characterizations of generalized monotone nonsmooth continuous maps using approximate Jacobians. J. Convex Anal. 5: 119–132 · Zbl 0911.49014
[27] Jeyakumar V. and Luc D.T. (1999). Nonsmooth calculus, minimality and monotonicity of convexificators. J. Optim. Theory Appl. 101: 599–621 · Zbl 0956.90033 · doi:10.1023/A:1021790120780
[28] Klose J. (1992). Sensitivity analysis using the tangent derivative. Numer. Funct. Anal. Optimiz. 13: 143–153 · Zbl 0773.49009 · doi:10.1080/01630569208816467
[29] Kuroiwa D. (1998). Natural criteria of set-valued optimization, Manuscript. Shimane University, Japan · Zbl 0939.90570
[30] Li Z. (1999). A theorem of the alternative and its application to the optimization of set-valued maps. J. Optim. Theory Appl. 100: 365–375 · Zbl 0915.90253 · doi:10.1023/A:1021786303883
[31] Loewen P.D. (1992). Limits of Frechet normals in nonsmooth analysis. Optimization and Nonlinear Analysis. Pitman Research Notes Math, Ser. 244: 178–188 · Zbl 0766.49013
[32] Luc D.T. (1991). Contingent derivatives of set-valued maps and applications to vector optimization. Math. Program. 50: 99–111 · Zbl 0718.90080 · doi:10.1007/BF01594928
[33] Luc D.T. and Malivert C. (1992). Invex optimization problems. Bull. Austral. Math. Soc. 46: 47–66 · Zbl 0755.90072 · doi:10.1017/S0004972700011679
[34] Marti K. (2005). Stochastic Optimization Methods. Springer, Berlin · Zbl 1059.90110
[35] Michel, P., Penot, J-P.: Calcul sous-differentiel pour des fonctions Lipschitziennes et non Lipschitziennes. C.R. Acad. Sc. Paris 298 (1984) · Zbl 0567.49008
[36] Michel P. and Penot J-P. (1992). A generalized derivative for calm and stable functions. Diff. Integral Eq. 5(2): 433–454 · Zbl 0787.49007
[37] Migdalas, A., Pardalos, P.M., Värbrand, P.: Multilevel optimization : algorithms and applications. Kluwer Academic Publishers (1997)
[38] Mordukhovich, B.S.: Variational analysis and generalized differentiation. Vol. I, II, Springer Verlag, Berlin et al. (2006)
[39] Mordukhovich B.S. and Shao Y. (1995). On nonconvex subdifferential calculus in Banach spaces. J. Convex Anal. 2: 211–228 · Zbl 0838.49013
[40] Outrata J.V. (1993). On necessary optimality conditions for Stackelberg problems. J. Optim. Theory Appl. 76: 306–320 · Zbl 0802.49007 · doi:10.1007/BF00939610
[41] Outrata J.V. (1993). Optimality problems with variational inequality constraints. SIAM J. Optim. 4: 340–357 · Zbl 0826.90114 · doi:10.1137/0804019
[42] Penot J.P. (1988). On the mean-value theorem. Optimization 19: 147–156 · Zbl 0661.49008 · doi:10.1080/02331938808843330
[43] Ralph D. and Dempe S. (1995). Directional derivatives of the solution of a parametric nonlinear program. Math. Program. 70: 159–172 · Zbl 0844.90089
[44] Thibault L. (1991). On subdifferentials of optimal value functions. SIAM J. Control Optim. 29: 1019–1036 · Zbl 0734.90093 · doi:10.1137/0329056
[45] Treiman J.S. (1995). The linear nonconvex generalized gradient and Lagrange multipliers. SIAM J. Optim. 5: 670–680 · Zbl 0829.49017 · doi:10.1137/0805033
[46] Wang S., Wang Q. and Romano-Rodriguez S. (1993). Optimality conditions and an algorithm for linear-quadratic bilevel programs. Optimization 4: 521–536
[47] Ye J.J. and Zhu D.L. (1995). Optimality conditions for bilevel programming problems. Optimization 33: 9–27 · Zbl 0820.65032 · doi:10.1080/02331939508844060
[48] Ye, J.J.: Constraint qualifications and KKT conditions for bilevel programming problems. Math. Oper. Res. (2007, to appear) · Zbl 1278.90437
[49] Zhang R. (1993). Problems of hierarchical optimization in finite dimensions. SIAM J. Optim. 4: 521–536 · Zbl 0819.90107 · doi:10.1137/0804029
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.