×

A novel approach to bilevel nonlinear programming. (English) Zbl 1145.90083

Summary: 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.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bard J.F. (1983) An efficient point algorithm for a linear two-stage optimization problem. Oper. Res. 31, 670–684 · Zbl 0525.90086 · doi:10.1287/opre.31.4.670
[2] Bard J.F. (1988) Convex two-level optimization. Math. Program. 40, 15–27 · Zbl 0655.90060 · doi:10.1007/BF01580720
[3] Bard J.F. (1998) Practical bilevel optimization algorithms and Optimization. Kluwer, Dordrecht · Zbl 0943.90078
[4] Bard J.F., Falk J. (1982) An explicit solution to the multi-level programming problem. Comp. Oper. Res. 9, 77–100 · doi:10.1016/0305-0548(82)90007-7
[5] Baer E., Hiltner A., Morgan R. (1992) Biological and synthetic hierarchical composites. Phys. Today 46, 60–67 · doi:10.1063/1.881344
[6] Ben-Ayed O. (1993) Bilevel linear programming. Comput. Oper. Res. 20, 485–501 · Zbl 0783.90068 · doi:10.1016/0305-0548(93)90013-9
[7] Bialas W.F., Karwan C.H. (1982) On two-level optimization. IEEE Trans. Auto.Cont. Vol. AC-27, 211–214 · Zbl 0487.90005 · doi:10.1109/TAC.1982.1102880
[8] Brackel J., McGill J. (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21, 37–44 · Zbl 0263.90029 · doi:10.1287/opre.21.1.37
[9] Brackel J., McGill J. (1974) A method for solving mathematical programs with nonlinear programs in the constraints. Oper. Res. 22: 1097–1101 · Zbl 0294.90070 · doi:10.1287/opre.22.5.1097
[10] Candler W., Townsley R. (1982) A linear two-level programming problem. Comput. Ops Res. 9, 59–76 · doi:10.1016/0305-0548(82)90006-5
[11] 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
[12] Clark P.A., Westerberg A.W. (1988) A note on the optimality conditions for the bilevel programming problem. Naval Res. Logistics 35, 413–418 · Zbl 0653.90045 · doi:10.1002/1520-6750(198810)35:5<413::AID-NAV3220350505>3.0.CO;2-6
[13] 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 · Zbl 0897.90175
[14] Edmunds T., Bard J. (1991) Algorithms for nonlinear bilevel mathematical programming. Trans. Syst. Man Cybernetics 21, 83–89 · doi:10.1109/21.101139
[15] Falk J.E., Liu J. (1995) On bilevel programming, Part I; general nonlinear cases. Math. Program. 70, 47–72 · Zbl 0841.90112
[16] Floudas C. et al. (1999) Handbook of Test Problems for Local and Global Optimization. Kluwer, Dordrecht · Zbl 0943.90001
[17] 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
[18] Hansen P., Jaumard B., savard G. (1992) New branch and bound rules for linear bilevel programming. SIAM J. Sci. Sta. Comput. 13: 1194–1217 · Zbl 0760.65063 · doi:10.1137/0913069
[19] Konno H., Thach P.T., Tuy H. (1997) Optimization on Low Rank Nonconvex structures. Kluwer, Dordrecht · Zbl 0879.90171
[20] 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 · Zbl 0896.90164
[21] 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 · Zbl 0726.90111
[22] 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
[23] Migdalas A., Pardalos P.M. Hierarchical and bilevel programming. J. Glob. Optim. 8(3) (1996)
[24] Migdalas A., Pardalos P.M., Värbrand P. (eds) (1998) Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht · Zbl 0881.00028
[25] Pardalos P.M., Deng X.: Complexity issues in hierarchical optimization. In: DIMACs series, vol. 37, American Mathematical Society, pp. 219–224. Providence, RI (1997) · Zbl 0893.90189
[26] Shimizu K., Ishizuka Y., Bard J.F. (1997) Nondifferentiable and Two-Level Mathematical Programming. Kluwer, Dordrecht · Zbl 0878.90088
[27] 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 · Zbl 0897.90147
[28] Tuy H. (1998) Convex Analysis and Global Optimization. Kluwer, Dordrecht · Zbl 0904.90156
[29] Tuy H., Migdalas A., Värbrand P. (1992) A global optimization approach for the linear two-level program. J. Glob. Optim. 3, 1–23 · Zbl 0771.90108 · doi:10.1007/BF01100237
[30] Tuy H., Migdalas A., Värbrand P. (1994) A quasiconcave minimization method for solving linear two-level programs. J. Glob. Optim. 4, 243–263 · Zbl 0792.90075 · doi:10.1007/BF01098360
[31] 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 · Zbl 0897.90148
[32] Tuy H. (2000) Monotonic optimization: problems and solution approaches. SIAM J. Optim. 11, 464–494 · Zbl 1010.90059 · doi:10.1137/S1052623499359828
[33] 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 · Zbl 1049.90067
[34] Tuy H. (2002) Hierarchical optimization. In: Pardalos P., Resende M. (eds) Handbook of Applied Optimization. Oxford University Press, Oxford, pp. 502–513
[35] 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 · Zbl 1070.26014
[36] 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 · Zbl 1136.90446
[37] 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 · Zbl 1130.90385
[38] Vicente L.N., Calamai P.Y. (1994) Bilevel and multilevel programming: a bibliographic review. J. Glob. Optim. 5, 291–306 · Zbl 0822.90127 · doi:10.1007/BF01096458
[39] Vicentee L., Savard G., Judice J. (1994) Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81, 379 · Zbl 0819.90076 · doi:10.1007/BF02191670
[40] Vincent J.F. (1990) Structural Biomaterials. Princeton University Press, Princeton
[41] White D.J., Anandalingam G. (1993) A penalty function approach for solving bilevel linear programs. J. Glob. Optim. 3, 397–419 · Zbl 0791.90047 · doi:10.1007/BF01096412
[42] Yezza A. (1996) First-order necessary optimality conditions for general bilevel programming problems. J Optim Theory Appl 89, 189–219 · Zbl 0866.90119 · doi:10.1007/BF02192648
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.