Abstract
We consider the approximation of nonlinear bilevel mathematical programs by solvable programs of the same type, i.e., bilevel programs involving linear approximations of the upper-level objective and all constraint-defining functions, as well as a quadratic approximation of the lower-level objective. We describe the main features of the algorithm and the resulting software. Numerical experiments tend to confirm the promising behavior of the method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Aiyoshi and K. Shimizu, “Hierarchical decentralized systems and its new solution by a barrier method,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 11, pp. 444–449, 1981.
E. Aiyoshi and K. Shimizu, “A solution method for the static constrained Stackelberg problem via penalty method,” IEEE Transactions on Automatic Control, vol. 29, pp. 1111–1114, 1984.
F.A. Al-Khayal, R. Horst, and P. M. Pardalos, “Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming,” Annals of Operations Research, vol. 34, pp. 125–147, 1992.
G. Anandalingam and T. Friesz, “Hierarchical optimization: An introduction,” Annals of Operations Research, vol. 34, pp. 1–11, 1992.
G. Anandalingam and D.J. White, “A solution method for the linear static stackelberg problem using penalty funcitons,” IEEE Transactions on Automatic Control, vol. 35, pp. 1170–1173, 1990.
A. Auslender, Optimisation: Méthodes numériques, Masson, Paris, 1976.
J.F. Bard, “Convex two-level optimization,” Mathematical Programming, vol. 40, pp. 15–27, 1988.
J.F. Bard, Practical Bilevel Optimization–-Algorithms and Applications, Kluwer Academic Publishers, 1998.
J.F. Bard and J. Falk, “An explicit solution to the multi-level programming problem,” Computers and Operations Research, vol. 9, pp. 77–100, 1982.
J.F. Bard and J.T. Moore, “A branch and bound algorithm for the bilevel programming problem,” SIAM Journal of Scientific and Statistical Computing, vol. ll, no. 2, pp. 281–292, 1990.
O. Ben-Ayed, “Bilevel linear programming,” Computers and Operations Research, vol. 20, pp. 485–501, 1993.
Z. Bi, P.H. Calamai, and A.R. Conn, “An exact penalty function approach for the linear bilevel programming problem,” Technical Report No. 167-0-310789, Department of Systems Design Engineering, University of Waterloo, 1989.
Z. Bi, P.H. Calamai, and A.R. Conn, “An exact penalty function approach for the nonlinear bilevel programming problem,” Technical Report No, 180-0-170591, Department of Systems Design Engineering, University of Waterloo, 1991.
W. Bialas and M. Karwan, “Two-level linear programming,” Management Science, vol. 30, pp. 1004–1020, 1984.
W. Bialas, M. Karwan, and J. Shaw, “A parametric complementarity pivot approach for two-level linear programming,” Technical Report 80-2, State University of Now York at Buffalo, Operations Research Program, 1980.
J. Bracken and J. McGill, “Mathematical programs with optimization problems in the constraints,” Operations Research, vol. 21, pp. 37–44, 1973.
L. Brotcorne, “Approches opérationnelles et stratégiques des problémes de trafic routier,” PhD thesis, Université Libre de Bruxelles, Brussels, Belgium, 1998.
P.H. Calamai and L.N. Vicente, “Generating linear and linear-quadratic bilevel programming problems,” SIAM Journal on Scientific Computing, vol. 14, pp. 770–782, 1993.
P.H. Calamai and L.N. Vicente, “Algorithm 728: FORTRAN subroutines for generating quadratic bilevel programming problems,” ACM Transactions on Mathematical Software, vol. 20, pp. 120–123, 1994.
P.H. Calamai and L.N. Vicente, “Generating quadratic bilevel programming test problems,” ACM Transactions on Mathematical Software, vol. 20, pp. 103–119, 1994.
P.H. Calamai, L.N. Vicente, and J.J. Júdice, “A new technique for generating quadratic programming test problems,” Mathematical Programming, vol. 61, pp. 215–231, 1993.
W. Candler and R. Norton, “Multilevel programing,” Technical Report 20, World Bank Development Research Center: Washington DC, 1977.
W. Candler and R. Townsley, “A linear two-level programming problem,” Computers and Operations Research, vol. 9, pp. 59–76, 1982.
L.M. Case, An l1 Penalty Function Approach to the Nonlinear Bilevel Programming Problem, PhD thesis, University of Waterloo: Ontario, Canada, 1999.
B. Colson, “Mathematical programs with equilibrium constraints and nonlinear bilevel programming problems,” Master’s thesis, Department of Mathematics, FUNDP, Namur, Belgium, Sept. 1999.
B. Colson, “BIPA (Bilevel programming with approximation methods): Software guide and test problems,” Technical Report CRT-2002-38, Centre de Recherche sur les Transports, Université de Montréal, Montréal, QC, Canada, Oct. 2002.
A.R. Conn, N.I.M. Gould, and Ph.L. Toint, Trust-Region Methods, SIAM Publications: Philadelphia, Pennsylvania, USA, 2000.
S. Dempe, “A necessary and a sufficient optimality condition for bilevel programming problems,” Optimization, vol. 25, pp. 341–354, 1992.
S. Dempe, Foundations of Bilevel Programming, vol. 61 of Nonconvex Optimization and its Applications, Kluwer Academic Publishers: Dordrecht, The Netherlands, 2002.
S. Dempe, “Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints,” Optimization, vol. 52, pp. 333–359, 2003.
J.E. Dennis Jr and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall: Englewood Cliffs, New Jersey, USA, 1983. Reprinted as Classics in Applied Mathematics 16, SI AM Publications: Philadelphia, Pennsylvania, USA, 1996.
T. Edmunds and J.F. Bard, “Algorithms for nonlinear bilevel mathematical programs,” IEEE transactions on Systems, Man, and Cybernetics, vol. 21, no. 1, pp. 83–89, 1991.
F. Facchinei, H. Jiang, and L. Qi, “A smoothing method for mathematical programs with equilibrium constraints,” Technical Report R03-9.6, Università di Roma “La Sapienza,” Dipartimento di Informatica e Sistemistica, 1996.
J.E. Falk and J. Liu, “On bilevel programming, Part I: general nonlinear cases,” Mathematical Programming, vol. 70, no. 1, pp. 47–72, 1995.
R. Fletcher and S. Leyffer, “Nonlinear programming without a penalty function,” Mathematical Programming, vol. 91, pp. 239–269, 2002.
R. Fletcher and S. Leyffer, “Numerical experience with solving MPECs by nonlinear programming methods,” Numerical Analysis Report NA/210, Department of Mathematics, University of Dundee, Dundee, Scotland, 2002.
R. Fletcher, S. Leyffer, D. Ralph, and S. Scholtes, Local Convergence of SQP Methods for Mathematical Programs with Equilibrium Constraints, Numerical Analysis Report NA/209, Department of Mathematics, University of Dundee, Dundee, Scotland, 2002.
C.A. Floudas, P.M. Pardalos, C.S. Adjiman, W.R. Esposito, Z.H. Gumus, S.T. Harding, J.L. Klepeis, C.A. Meyer, and C.A. Schweiger, Handbook of Test Problems in Local and Global Optimization, Kluwer, 1999.
J. Fortuny-Amat and B. McCarl, “A representation and economic interpretation of a two-level programming problem,” Journal of the Operational Research Society, vol. 32, pp. 783–792, 1981.
M. Fukushima, “Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,” Mathematical Programming, vol. 53, pp. 99–110, 1992.
M. Fukushima and J.-S. Pang, “Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints,” Computational Optimization and Applications, vol. 13, pp. 111–136, 1999.
P. Hansen, B. Jaumard, and G. Savard, “New branch-and-bound rules for linear bilevel programming,” SIAM Journal on Scientific and Statistical Computing, vol. 13, no. 5, pp. 1194–1217, 1992.
S. Hsu and U. Wen, “A review of linear bilevel programming problems,” in Proceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering, vol. 13, pp. 53–61, 1989.
ILOG CPLEX Division, CPLEX User’s Guide.
Y. Ishizuka and E. Aiyoshi, “Double penalty method for bilevel optimization problems,” Annals of Operations Research, vol. 34, pp. 73–88, 1992.
B. Jaumard, G. Savard, and J. Xiong, “An exact algorithm for convex quadratic bilevel programming,” Draft paper, Ecole Polytechnique de Montréal, January 2000.
H. Jian and D. Ralph, “Smooth sqp methods for mathematical programs with nonlinear complementarity constraints,” Manuscript, Department of Mathematics and Statistics, University of Melbourne, Dec. 1997.
J. Júdice and A. Faustino, “The solution of the linear bilevel programming problem by using the linear complementarity problem,” Investigaç ão Operational, vol. 8, pp. 77–95, 1988.
J. Júdice and A. Faustino, “A sequential LCP method for bilevel linear programming,” Annals of Operations Research, vol. 34, pp. 89–106, 1992.
C.D. Kolstad, “A review of the literature on bi-level mathematical programming,” Technical Report LA-10284-MS, Los Alamos National Laboratory, Los Alamos, New Mexico, 1985.
C.D. Kolstad and L.S. Lasdon, “Derivative estimation and computational experience with large bilevel mathematical programs,” Journal of Optimization Theory & Applications, vol. 65, pp. 485–499, 1990.
M. Labbé, P. Marcotte, and G. Savard, “A bilevel model of taxation and its applications to optimal highway pricing,” Management Science, vol. 44, pp. 1595–1607, 1998.
S. Leyffer, MacMPEC–-Ampl collection of Mathematical Programs with Equilibrium Constraints, Available at http://wvw-unix.mcs.anl.gov/~leyffer/MacMPEC/.
G. Liu, J. Han, and S. Wang, “A trust region algorithm for bilevel programming problems,” Chinese Science Bulletin, vol. 43, no. 10, pp. 820–824, 1998.
P. Loridan and J. Morgan, “Weak via strong Stackelberg problem: New results,” Journal of Global Optimization, vol. 8, pp. 263–287, 1996.
Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996.
A. Migdalas, “Bilevel programming in traffic planning: Models, methods and challenge,” Journal of Global Optimization, vol. 7, pp. 381–405, 1995.
J. Outrata, “On optimization problems with variational inequality constraints,” SIAM Journal on Optimization, vol. 4, no. 2, pp. 340–357, 1994.
J.V. Outrata, M. Kočvara, and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraintsé. Kluwer Academic Publishers, 1998.
D. Ralph, Optimization with Equilibrium Constraints: A Piecewise SQP Approach, Manuscript, Department of Mathematics and Statistics, University of Melbourne, Nov. 1998.
G. Savard, Contribution à la programmation mathématique à deux niveaux. Ph.D. thesis, Ecole Polytechnique de Montréal, Université de Montréal, April 1989.
G. Savard and J. Gauvin, “The steepest descent direction for the nonlinear bilevel programming problem,” Operations Research Letters, vol. 15, pp. 265–272, 1994.
S. Scholtes, “Convergence properties of a regularisation scheme for mathematical programs with complementarity constraints,” SIAM Journal on Optimization, vol. 11, pp. 918–936, 2001.
S. Scholtes and M. Stöhr, “Exact penalization of mathematical programs with equilibrium constraints,” SIAM Journal on Control and Optimization, vol. 37, no. 2, pp. 617–652, 1999.
K. Shimizu and E. Aiyoshi, “A new computational method for Stackelberg and min-max problems by use of a penalty method,” IEEE Transactions on Automatic Control, vol. 26, pp. 460–466, 1981.
K. Shimizu, Y. Ishizuka, and J.F. Bard, Nondifferentiable and Two-Level Mathematical Programming, Kluwer Academic Publishers, 1997.
A.H. De Silva, Sensitivity Formulas for Nonlinear Factorable Programming and their Application to the Solution of an Implicitly Defined Optimization Model of US Crude Oil Production, Ph.D. thesis, George Washington University, 1978.
P. Spellucci, D0NLP2 Users Guide. Technical University at Darmstadt, Department of Mathematics, 64829 Darmstadt, Germany.
P. Spellucci, “A new technique for inconsistent problems in the SQP method,” Math. Meth. of Oper. Res., vol. 47, pp. 355–400, 1998.
P. Spellucci, “An SQP method for general nonlinear programs using only equality constrained subproblems,” Mathematical Programming, vol. 82, pp. 413–448, 1998.
N.V. Thoai, Y. Yamamoto, and A. Yoshise, “Global optimization method for solving mathematical programs with linear complementarity constraints,” Discussion Paper No. 987, Institute of Policy and Planning Sciences, University of Tsukuba, Japan, May 2002.
H. Tuy, A. Migdalas, and P. Varbrand, “A global optimization approach for the linear two-level rjrogram,” Journal of Global Optimization, vol. 3, pp. 1–23, 1993.
L.N. Vicente and P.H. Calamai, “Bilevel and multilevel programming: A bibliography review,” Journal of Global Optimization, vol. 5, no. 3, pp. 291–306, 1994.
L.N. Vicente, P.H. Calamai, and J.J. Júdice, “Generation of disjointly constrained bilinear programming test problems,” Computational Optimization and applications, vol. 1, pp. 299–306, 1992.
L.N. Vicente, G. Savard, and J.J. Júdice, “Discrete linear bilevel programming problem,” Journal of Optimization Theory and Applications, vol. 89, pp. 597–614, 1996.
U. Wen and S. Hsu, “Linear bi-level programming problems–-A review,” Journal of the Operational Research Society, vol. 42, pp. 125–133, 1991.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Colson, B., Marcotte, P. & Savard, G. A Trust-Region Method for Nonlinear Bilevel Programming: Algorithm and Computational Experience. Comput Optim Applic 30, 211–227 (2005). https://doi.org/10.1007/s10589-005-4612-4
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10589-005-4612-4