×

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm. (English) Zbl 1237.90176

The author proposes an enumeration sequential quadratic programming algorithm to solve convex bilevel programming problems in an optimistic approach. The upper and lower level objective functions are convex and the feasible region is a polyhedron. From monotonicity principles a new concept of monotonicity networks is introduced. A monotonicity path is used to express the tightness of some subsets of the primal and dual lower level constraints, depending on the current rational solution. At each step of the algorithm, monotonicity paths are used to compute an improving rational solution within the tightness of primal-dual lower level constraints. Given a feasible or rational solution in a branch and bound framework, the method performs a sequential investigation on some indexes of lower level primal-dual variables in order to compute some improved rational solutions.

MSC:

90C20 Quadratic programming
90C25 Convex programming
90C55 Methods of successive quadratic programming type
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdou-Kandil H., Bertrand P.: Government-private sector relations as a stackelberg game: a degenerate case. J. Econ. Dyn. Control 11, 513–517 (1987). doi: 10.1016/S0165-1889(87)80004-0 · Zbl 0638.90021 · doi:10.1016/S0165-1889(87)80004-0
[2] Audet C., Hansen P., Jaumard B., Savard G.: Links between linear bilevel and mixed 0–1 programming problems. J. Optim. Theory Appl. 93(2), 273–300 (1997). doi: 10.1023/A:1022645805569 · Zbl 0901.90153 · doi:10.1023/A:1022645805569
[3] Bard J.F., Moore J.T.: A branch and bound algorithm for the bilevel programming problem. SIAM J. Sci. Stat. Comput. 11, 281–292 (1990). doi: 10.1137/0911017 · Zbl 0702.65060 · doi:10.1137/0911017
[4] Bard J.F.: Convex two-level programming. Math. Program. 40(1), 15–28 (1988). doi: 10.1007/BF01580720 · Zbl 0655.90060 · doi:10.1007/BF01580720
[5] Bard J.F.: Optimality conditions for the bilevel programming problem. Nav. Res. Logist. Q. 31, 13–26 (1984). doi: 10.1002/nav.3800310104 · Zbl 0537.90087 · doi:10.1002/nav.3800310104
[6] Bard J.F., Plummer J.C., Sourie J.C.: A bilevel programming approach to determining tax credits for biofuel production. Eur. J. Oper. Res. 120, 30–43 (2000). doi: 10.1016/S0377-2217(98)00373-7 · Zbl 0976.90099 · doi:10.1016/S0377-2217(98)00373-7
[7] Ben-Ayed O., Blair C.: Computational difficulties of bilevel linear programming. Oper. Res. 38, 556–560 (1990). doi: 10.1287/opre.38.3.556 · Zbl 0708.90052 · doi:10.1287/opre.38.3.556
[8] Bertier, P., Roy, B.: Procédures de résolution pour une classe de problème pouvant avoir un caractère combinatoire. Cahier du centre d’études de recherche opérationnelle, 6 (1964) · Zbl 0204.18903
[9] Bialas W.F., Karwan M.H.: Two-level linear programming. Manage. Sci. 30(8), 1004–1020 (1984). doi: 10.1287/mnsc.30.8.1004 · Zbl 0559.90053 · doi:10.1287/mnsc.30.8.1004
[10] Brotcorne L., Labbé M., Marcotte P., Savard G.: A bilevel model and solution algorithm for a freight tariff setting problem. Transp. Sci. 34, 289–302 (2000). doi: 10.1287/trsc.34.3.289.12299 · Zbl 0991.90573 · doi:10.1287/trsc.34.3.289.12299
[11] Calvete H.I., Gale C.: On the quasiconcave bilevel programming problem. J. Optim. Theory Appl. 98(3), 613–622 (1998). doi: 10.1023/A:1022624029539 · Zbl 0913.90240 · doi:10.1023/A:1022624029539
[12] Campêlo M., Dantas S., Scheimberg S.: A note on a penalty function approach for solving bilevel linear programs. J. Glob. Optim. 16, 245–255 (2000). doi: 10.1023/A:1008308218364 · Zbl 0971.90064 · doi:10.1023/A:1008308218364
[13] Candler, W., Norton, R.: Multi-level programming and development policy. World bank development research center discussion paper, vol. 258, Washington, May (1977b)
[14] Candler, W., Norton, R.: Multi-level programming. World bank development research center discussion paper, vol. 20, Washington, January (1977a)
[15] Candler W., Townsley R.: A linear two-level programming problem. Comput. Oper. Res. 9, 57–76 (1982). doi: 10.1016/0305-0548(82)90006-5 · doi:10.1016/0305-0548(82)90006-5
[16] Chen Y., Florian M.: The nonlinear bilevel programming problem: formulation, regularity and optimality conditions. Optimization 32, 193–309 (1995). doi: 10.1080/02331939508844048 · Zbl 0812.00045 · doi:10.1080/02331939508844048
[17] Clarke L.E.: On cayley’s formula for counting trees. Proc. Camb. Philos. Soc. 59, 509–517 (1963). doi: 10.1017/S0305004100037178 · doi:10.1017/S0305004100037178
[18] Colson B., Marcotte P., Savard G.: Bilevel programming: a survey. 4OR Q. J. Oper. Res. 4(R 3), 87–107 (2005) · Zbl 1134.90482 · doi:10.1007/s10288-005-0071-0
[19] Dempe S.: A simple algorithm for the linear bilevel programming problem. Optimization 18, 373–385 (1987). doi: 10.1080/02331938708843247 · Zbl 0634.90075 · doi:10.1080/02331938708843247
[20] Dempe S.: A necessary and sufficient optimality for bilevel programming problem. Optimization 2, 341–354 (1992). doi: 10.1080/02331939208843831 · Zbl 0817.90104 · doi:10.1080/02331939208843831
[21] Dempe S.: Annoted bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52, 333–359 (2003). doi: 10.1080/0233193031000149894 · Zbl 1140.90493 · doi:10.1080/0233193031000149894
[22] Etoa, E.J.B.: Contribution à la résolution des programmes mathématiques à deux niveaux et des programmes mathématiques avec contraintes d’équilibre, PhD Thesis, École Polytechnique de Montréal, December (2005)
[23] Facchinei F., Fischer A., Kanzow C.: On the accurate identification of active constraints. SIAM J. Optim. 9, 14–32 (1998). doi: 10.1137/S1052623496305882 · Zbl 0960.90080 · doi:10.1137/S1052623496305882
[24] Falk J.E., Liu J.: On bilevel programming, part I: general nonlinear case. Math. Program. 70, 47–72 (1995) · Zbl 0841.90112
[25] Gümüs Z.H., Floudas C.H.: Global optimization of nonlinear bilevel programming problems. J. Glob. Optim. 20, 1–31 (2001). doi: 10.1023/A:1011268113791 · Zbl 1049.90092 · doi:10.1023/A:1011268113791
[26] Hansen P., Jaumard B., Lu S.H.: A frame work for algorithms in globally optimal design. ASME J. Mech. Autom. Transm. 111, 353–360 (1989)
[27] Hansen P., Jaumard B., Savard G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13, 1194–1217 (1992). doi: 10.1137/0913069 · Zbl 0760.65063 · doi:10.1137/0913069
[28] Jeroslow R.G.: The polynomial hierarchy and simple model for competitive analysis. Math. Program. 32, 146–164 (1985). doi: 10.1007/BF01586088 · Zbl 0588.90053 · doi:10.1007/BF01586088
[29] Kolstad C.D., Lasdon L.: Derivative evaluation and computational experience with large bilevel mathematical programs. J. Optim. Theory Appl. 65, 485–499 (1990). doi: 10.1007/BF00939562 · Zbl 0676.90101 · doi:10.1007/BF00939562
[30] Kornaj J., Liptak T.: Two-level planning. Econometrica 33, 141–169 (1965). doi: 10.2307/1911892 · Zbl 0127.36703 · doi:10.2307/1911892
[31] Labbé M., Marcotte P., Savard G.: A bilevel model of taxation and its application to optimal highway pricing. Manage. Sci. 44, 1608–1622 (1998). doi: 10.1287/mnsc.44.12.1608 · Zbl 0989.90014 · doi:10.1287/mnsc.44.12.1608
[32] Lin, G.H., Fukushima, M.: Hybrid algorithms with active set identification for mathematical programs with complementarity constraints, Technical Report 2002–2008, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan (2003) · Zbl 1130.90047
[33] Little, J.D.C., Murty, K.G., Sweeney, D.W., Karel, C.: An algorithm for the traveling salesman problem. J. OSRA, 11 (1963) · Zbl 0161.39305
[34] Marcotte, P., Savard, G.: Bilevel programming: a combinatorial perspective, graph theory and combinatorial Optimization. In: Avis, D., Hertz, A., Marcotte, O. (eds.) Springer, Berlin (2005) · Zbl 1098.90059
[35] Muu L.D., Quy N.V.: A global optimization method for solving convex quadratic bilevel programming problems. J. Glob. Optim. 26, 199–219 (2003). doi: 10.1023/A:1023047900333 · Zbl 1053.90104 · doi:10.1023/A:1023047900333
[36] Rockafellar R.T.: Convex analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[37] Ross S.A.: The economic theory of agency: the principal’s problem. AER 63, 134–139 (1973)
[38] Savard G., Gauvin J.: The steepest descent direction for the nonlinear bilevel programming problem. Oper. Res. Lett. 1, 265–272 (1994). doi: 10.1016/0167-6377(94)90086-8 · Zbl 0816.90122 · doi:10.1016/0167-6377(94)90086-8
[39] Savard, G.: Contribution à la programmation mathématique à deux niveaux, PhD Thesis, École Polytechnique de Montréal (1989)
[40] Still G.: Linear bilevel problems: genericity results and efficient method for computing local minima. Math. Methods Oper. Res. 5, 383–400 (2002). doi: 10.1007/s001860200189 · Zbl 1115.90364 · doi:10.1007/s001860200189
[41] Vicente L.N., Calamai P.H.: Bilevel and multilevel programming, a bibliography review. J. Glob. Optim. 5(3), 291–306 (1994). doi: 10.1007/BF01096458 · Zbl 0822.90127 · doi:10.1007/BF01096458
[42] Vicente L.N., Savard G., Jùdice J.: Descent approach for quadratic bilevel programming. J. Optim. Theory Appl. 81, 379–399 (1994). doi: 10.1007/BF02191670 · Zbl 0819.90076 · doi:10.1007/BF02191670
[43] Wang S., Lootsma F.A.: A hierarchical optimization model of resource allocation. Optimization 28, 351–365 (1994). doi: 10.1080/02331939408843928 · Zbl 0819.90027 · doi:10.1080/02331939408843928
[44] Wang, G.M., Wan, Z.P., Wang, X.J.: Genetic algorithm for solving convex quadratic bilevel programming problems, working paper. AMS, MOS subject classifications: 90C30 (2003)
[45] Wilde D.: Monotonicity and dominance in optimal hydraulic cylinder design. J. Eng. Ind. 97(4), 13–26 (1975)
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.