Abstract
Recently developed methods of monotonic optimization have been applied successfully for studying a wide class of nonconvex optimization problems, that includes, among others, generalized polynomial programming, generalized multiplicative and fractional programming, discrete programming, optimization over the efficient set, complementarity problems. In the present paper the monotonic approach is extended to the General Bilevel Programming GBP Problem. It is shown that (GBP) can be transformed into a monotonic optimization problem which can then be solved by “polyblock” approximation or, more efficiently, by a branch-reduce-and-bound method using monotonicity cuts. The method is particularly suitable for Bilevel Convex Programming and Bilevel Linear Programming.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bard J.F. (1983) An efficient point algorithm for a linear two-stage optimization problem. Oper. Res. 31, 670–684
Bard J.F. (1988) Convex two-level optimization. Math. Program. 40, 15–27
Bard J.F. (1998) Practical bilevel optimization algorithms and Optimization. Kluwer, Dordrecht
Bard J.F., Falk J. (1982) An explicit solution to the multi-level programming problem. Comp. Oper. Res. 9, 77–100
Baer E., Hiltner A., Morgan R. (1992) Biological and synthetic hierarchical composites. Phys. Today 46, 60–67
Ben-Ayed O. (1993) Bilevel linear programming. Comput. Oper. Res. 20, 485–501
Bialas W.F., Karwan C.H. (1982) On two-level optimization. IEEE Trans. Auto.Cont. Vol. AC-27, 211–214
Brackel J., McGill J. (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21, 37–44
Brackel J., McGill J. (1974) A method for solving mathematical programs with nonlinear programs in the constraints. Oper. Res. 22: 1097–1101
Candler W., Townsley R. (1982) A linear two-level programming problem. Comput. Ops Res. 9, 59–76
Chen Y., Florian M. (1988) Congested O-D trip emand adjustment problem: bilevel programming formulation and optimality conditions. In: Migdalas A., Pardalos P., Värbrand P. (eds) Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht, pp. 1–22
Clark P.A., Westerberg A.W. (1988) A note on the optimality conditions for the bilevel programming problem. Naval Res. Logistics 35, 413–418
Dempe S. (1988) An implicit function approach to bilevel programming problems. In: Migdalas A., Pardalos P., Värbrand P. (eds) Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht, pp. 273–289
Edmunds T., Bard J. (1991) Algorithms for nonlinear bilevel mathematical programming. Trans. Syst. Man Cybernetics 21, 83–89
Falk J.E., Liu J. (1995) On bilevel programming, Part I; general nonlinear cases. Math. Program. 70, 47–72
Floudas C. et al. (1999) Handbook of Test Problems for Local and Global Optimization. Kluwer, Dordrecht
Fülöp J.: On the equivalence between a linear bilevel programming problem and linear optimization over the efficient set. Working paper WP 93-1, LORDS, Computer and Automation Institute, Budapest
Hansen P., Jaumard B., savard G. (1992) New branch and bound rules for linear bilevel programming. SIAM J. Sci. Sta. Comput. 13: 1194–1217
Konno H., Thach P.T., Tuy H. (1997) Optimization on Low Rank Nonconvex structures. Kluwer, Dordrecht
Lignola M.B., Morgan J. (1988) Existence of solutions to generalized bilevel programming problem. In: Migdalas A., Pardalos P., Värbrand P. (eds) Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht, pp. 315–330
Loridan P., Morgan J. (1990) Quasiconvex lower level problem and applications to two level optimization. Lecture Notes in Economics and Mathematical Systems, vol. 345. Springer, Dordrecht, pp. 325–341
Migdalas A., Pardalos P.M. (1995) Nonlinear bilevel problems with convex second level problem – heuristics and descent methods. In: Du D.-Z., Zhang X.-S., Cheng K., (eds) Operations Research and Its Applications. World Publishing Corporation, New York, pp. 194–204
Migdalas A., Pardalos P.M. Hierarchical and bilevel programming. J. Glob. Optim. 8(3) (1996)
Migdalas A., Pardalos P.M., Värbrand P. (eds) (1998) Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht
Pardalos P.M., Deng X.: Complexity issues in hierarchical optimization. In: DIMACs series, vol. 37, American Mathematical Society, pp. 219–224. Providence, RI (1997)
Shimizu K., Ishizuka Y., Bard J.F. (1997) Nondifferentiable and Two-Level Mathematical Programming. Kluwer, Dordrecht
Tuy H. (1998) Bilevel linear programming, multiobjective programming, and monotonic reverse convex programming. In: Migdalas A., Pardalos P.M., Värbrand P. (eds) Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht, pp. 295–314
Tuy H. (1998) Convex Analysis and Global Optimization. Kluwer, Dordrecht
Tuy H., Migdalas A., Värbrand P. (1992) A global optimization approach for the linear two-level program. J. Glob. Optim. 3, 1–23
Tuy H., Migdalas A., Värbrand P. (1994) A quasiconcave minimization method for solving linear two-level programs. J. Glob. Optim. 4, 243–263
Tuy H., Ghannadan s. (1998) A new branch and bound method for bilevel linear programs. In: Migdalas A., Pardalos P.M., Värbrand, P. (eds) Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht, pp. 231–249
Tuy H. (2000) Monotonic optimization: problems and solution approaches. SIAM J. Optim. 11, 464–494
Tuy H. (2001) Convexity and monotonicity in global optimization. In: Hadjisavvas N., Pardalos P.M. (eds) Advances in Convex Analysis and Optimization. Kluwer, Dordrecht, pp. 569–594
Tuy H. (2002) Hierarchical optimization. In: Pardalos P., Resende M. (eds) Handbook of Applied Optimization. Oxford University Press, Oxford, pp. 502–513
Tuy H. (2005) Monotonicity in the framework of generalized convexity. In: Eberhard A., Hadjisavvas N., Luc D.T. (eds) Generalized Convexity, Generalized Monotonicity and Applications. Springer, Berlin, pp. 61–85
Tuy H., Al-Khayyal F., Thach P.T. (2005) Monotonic Optimization: Branch and Cuts Methods. In: Audet C., Hansen P., Savard G. (eds) Essays and Surveys on Global Optimization. Springer, Berlin, pp. 39–78
Tuy H., Hoai-Phuong N.T. (2006) Optimization under composite monotonic constraints and constrained optimization over the efficient set. In: Liberti L., Maculan N. (eds) Global Optimization: from Theory to Implementation. Springer, Berlin, pp. 3–31
Vicente L.N., Calamai P.Y. (1994) Bilevel and multilevel programming: a bibliographic review. J. Glob. Optim. 5, 291–306
Vicentee L., Savard G., Judice J. (1994) Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81, 379
Vincent J.F. (1990) Structural Biomaterials. Princeton University Press, Princeton
White D.J., Anandalingam G. (1993) A penalty function approach for solving bilevel linear programs. J. Glob. Optim. 3, 397–419
Yezza A. (1996) First-order necessary optimality conditions for general bilevel programming problems. J Optim Theory Appl 89, 189–219
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tuy, H., Migdalas, A. & Hoai-Phuong, N.T. A novel approach to Bilevel nonlinear programming. J Glob Optim 38, 527–554 (2007). https://doi.org/10.1007/s10898-006-9093-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-006-9093-1
Keywords
- Bilevel nonlinear programming
- Bilevel convex programming
- Bilevel linear programming
- Leader and follower game
- Monotonic optimization
- Polyblock approximation
- Branch-reduce-and-bound method
- Monotonicity cuts