×

zbMATH — the first resource for mathematics

Exact and inexact penalty methods for the generalized bilevel programming problem. (English) Zbl 0855.90120
Summary: We consider a hierarchical system where a leader incorporates into its strategy the reaction of the follower to its decision. The follower’s reaction is quite generally represented as the solution set to a monotone variational inequality. For the solution of this nonconvex mathematical program a penalty approach is proposed, based on the formulation of the lower level variational inequality as a mathematical program. Under natural regularity conditions, we prove the exactness of a certain penalty function, and give strong necessary optimality conditions for a class of generalized bilevel programs.

MSC:
90C30 Nonlinear programming
93A13 Hierarchical systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hierarchical Optimization,Annals of Operations Research 34 (1992).
[2] G. Anandalingam and D.J. White, ”A solution method for the linear static Stackelberg problem using penalty functions,”IEEE Transactions on Automatic Control AC-35 (1990) 1170–1173. · Zbl 0721.90098 · doi:10.1109/9.58565
[3] J.F. Bard, ”An efficient point algorithm for a linear two-stage optimization problem,”Operations Research 31 (1983) 670–684. · Zbl 0525.90086 · doi:10.1287/opre.31.4.670
[4] Z. Bi, P. Calamai and A. Conn, ”An exact penalty method approach for the nonlinear bilevel programming problem,” Report # 180-0-170591, Department of Systems Design, University of Waterloo (1991).
[5] Computers and Operations Research 9 (1982).
[6] J.M. Danskin, ”The theory of max-min, with applications,”SIAM Journal of Applied Mathematics 14 (1966) 641–664. · Zbl 0144.43301 · doi:10.1137/0114053
[7] J.-P. Dussault and P. Marcotte, ”Conditions de régularité géométrique pour les inéquations variation-nelles,”RAIRO Recherche Opérationnelle 23 (1988) 1–16.
[8] C.S. Fisk, ”A conceptual framework for optimal transportation systems planning with integrated supply and demand models,”Transportation Science 20 (1986) 37–47. · doi:10.1287/trsc.20.1.37
[9] T.L. Friesz, R.T. Tobin, H-J Cho and N.J. Mehta, ”Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints,”Mathematical Programming 48 (1990) 265–284. · Zbl 0723.90070 · doi:10.1007/BF01582259
[10] M. Fukushima, ”Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,”Mathematical Programming 53 (1992) 99–110. · Zbl 0756.90081 · doi:10.1007/BF01585696
[11] M. Gendreau, P. Marcotte and G. Savard, ”A hybrid tabu-ascent algorithm for the linear bilevel programming problem,” forthcoming inJournal of Global Optimization. · Zbl 0859.90097
[12] J. Gauvin and G. Savard, ”The steepest descent method for the nonlinear bilevel programming problem,” Working paper G-9037, GERAD, École Polytechnique de Montréal (1992) (first version). · Zbl 0816.90122
[13] J. Haslinger and P. Neittaanmäki,Finite Element Approximation for Optimal Shape Design, Theory and Application, (Wiley, New York, 1988). · Zbl 0713.73062
[14] D.W. Hearn, ”The gap function of a convex program,”Operations Research Letters 1 (1981) 67–71. · Zbl 0486.90070 · doi:10.1016/0167-6377(82)90049-9
[15] A.J. Hoffman, ”On approximate solutions of systems of linear inequalities,”Journal of Research of the National Bureau of Standards 49 (1952) 263–265. · doi:10.6028/jres.049.027
[16] W. Hogan, ”Directional derivative for extremal value functions with applications to the completely convex case,”Operations Research 21 (1973) 188–209. · Zbl 0278.90062 · doi:10.1287/opre.21.1.188
[17] N.H. Josephy, ”Newton’s method for generalized equations,” Technical Report 1966, Mathematical Research Center, University of Wisconsin, Madison, WI (1979).
[18] P. Marcotte, ”A new algorithm for solving variational inequalities with application to the traffic assignment problem,”Mathematical Progamming 33 (1985) 339–351. · doi:10.1007/BF01584381
[19] P. Marcotte and J.-P. Dussault, ”A sequential linear programming algorithm for solving monotone variational inequalities,”SIAM Journal of Control and Optimization 27 (1989) 1260–1278. · Zbl 0689.90069 · doi:10.1137/0327064
[20] P. Marcotte and J.-P. Dussault, ”A note on a globally convergent method for solving monotone variational inequalities,”Operations Research Letters 6 (1987) 35–42. · Zbl 0623.65073 · doi:10.1016/0167-6377(87)90007-1
[21] Y. Qiu and T. Magnanti, ”Sensitivity analysis for variational inequalities,”Mathematics of Operations Research 17 (1992) 61–76. · Zbl 0756.49009 · doi:10.1287/moor.17.1.61
[22] Y. Ishizuka and E. Aiyoshi, ”Double penalty method for bilevel optimization problems,”Annals of Operations Research 34 (1992) 73–88. · Zbl 0756.90083 · doi:10.1007/BF02098173
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.