More Web Proxy on the site http://driver.im/

article

Global Optimization of Nonlinear Bilevel Programming Problems

Authors:

Zeynep H. Gümüş,

Christodoulos A. FloudasAuthors Info & Claims

Journal of Global Optimization, Volume 20, Issue 1

Pages 1 - 31

https://doi.org/10.1023/A:1011268113791

Published: 01 May 2001 Publication History

Abstract

A novel technique that addresses the solution of the general nonlinear bilevel programming problem to global optimality is presented. Global optimality is guaranteed for problems that involve twice differentiable nonlinear functions as long as the linear independence constraint qualification condition holds for the inner problem constraints. The approach is based on the relaxation of the feasible region by convex underestimation, embedded in a branch and bound framework utilizing the basic principles of the deterministic global optimization algorithm, αBB [2, 4, 5, 11]. Epsilon global optimality in a finite number of iterations is theoretically guaranteed. Computational studies on several literature problems are reported.

References

[1]

1. Adjiman, C. S., Androulakis, I. P. and Floudas, C. A. (1997), 'Global Optimization of minlp problems in process synthesis'. Comp. Chem. Engng. 21: S445.

[2]

2. Adjiman, C. S., Androulakis, I. P. and Floudas, C. A. (1998b), 'A Global Optimization Method, ¿BB, for General Twice-Differentiable Constrained NLPs II. Implementation and computational results'. Comp. Chem. Engng. 22(9): 1159-1179.

[3]

3. Adjiman, C. S., Androulakis, I. P. and Floudas, C. A. (2000), 'Global Optimization of Mixed-Integer Nonlinear Problems'. AIChE J. 46(9): 1769-1797.

[4]

4. Adjiman, C. S., Dallwig, S., Floudas, C. A. and Neumaier, A. (1998a), 'A Global Optimization Method, ¿BB, for General Twice-Differentiable Constrained NLPs I. Theoretical Advances'. Comp. Chem. Engng. 22(9): 1137-1158.

[5]

5. Adjiman, C. S. and Floudas, C. A. (1996), Rigorous Convex Underestimators for General Twice-Differentiable Problems. Journal of Global Optimization 9: 23.

[6]

6. Aiyoshi, E. and Shimizu, K. (1996), Hierarchical decentralized systems and its solution by a barrier method. IEEE Trans. on Sys., Man., Cyb. 11(6): 444.

[7]

7. Al-Khayyal, F. A. and Falk, J. E. (1983), Jointly Constrained Biconvex Programming. Maths. Ops. Res. 8: 273.

[8]

8. Al-Khayyal, F. A., Horst, R. and P.P. M., (1992), Global Optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming. Annals of Operations Research 34: 125.

Digital Library

[9]

9. Amouzegar, M. A., (1999), A global optimization method for nonlinear bilevel programming problems. IEEE Trans. Syst., Man, Cyber. 29(6): 771-777.

Digital Library

[10]

10. Anandalingam, G. and White, D. J. (1990), A solution method for the linear static Stackelberg problem using penalty functions. IEEE Trans. Auto. Contr. 35(10): 1170-1173.

[11]

11. Androulakis, I. P., Maranas, C. D. and Floudas, C. A. (1995), ¿bb: A global optimization method for general constrained nonconvex problems. Journal of Global Optimization 7: 337.

[12]

12. Bard, J. F. (1988), Convex two-level optimization. Mathematical Programming 40: 15-27.

Digital Library

[13]

13. Bard, J. F. (1991), Some properties of the bilevel programming problem. Journal of Optimization Theory and Applications 68: 371-378.

Digital Library

[14]

14. Bard, J. F. and Falk, J. (1982), An explicit solution to the multi-level programming problem. Comp. Op. Res. 9: 77-100.

[15]

15. Bard, J. F. and Moore, J. T. (1990), A branch and bound algorithm for the bilevel programming problem. SIAM J. on scientific and statistical computing 11: 281-282.

Digital Library

[16]

16. Bard, J. F., Plummer, J. and S.J. C., (1998), Determining tax credits for converting nonfood crops to biofuels: an application of bilevel programming. In: Migdalas, A., Pardalos, P. M. and Värbrand, P. (eds), Multilevel Optimization: Algorithms and Applications, p. 23. Nonconvex Optimization and Its Applications, p. 23. Kluwer Academic Publishers, Dordrecht/Boston/London.

[17]

17. Ben-Ayed, O. and Blair, C. E. (1990), Computational Difficulties of Bilevel Linear Programming. Operations Research 38: 556-559.

Digital Library

[18]

18. Ben-Ayed, O., Boyce, D. E. and Blair III, C. E. (1988), A general bilevel linear programming problem formulation of the network design problem. Trans. Res. 22B(4): 311.

[19]

19. Bialas, W. F. and Karwan, M. H. (1984), Two-level Linear Programming. Management Science 30: 1004.

Digital Library

[20]

20. Bracken, J. and McGill, J. T. (1973), A convex programming model for optimization problems in the constraints. Operations Research 21.

[21]

21. Brengel, D. D. and Seiderm, W. (1992), Coordinated design and control optimization of nonlinear processes. Comp. Chem. Engng. 16: 861-886.

[22]

22. Calvete, H. J. and Gale, C. (1999), The bilevel linear/linear fractional programming problem. European Journal of Operational Research 114: 188-197.

[23]

23. Candler, W. and Norton, N. (1977), Multi-level programming and development policy. Technical Report Working Paper No. 258, World Bank.

[24]

24. Candler, W. and Townsley, R. (1982), A linear two-level programming problem. Comp. Op. Res. 9(1).

[25]

25. Cassidy, R. G., Kriby, M. J. L. and Raike, W. M. (1971), Efficient distribution of resources through three levels of government. Management Science 17(8): B-462.

[26]

26. Clark, P. A. and Westerberg, A. W. (1990a), Bilevel programming for steady-state chemical process design-I. Fundamentals and Algorithms. Comp. Chem. Engng. 14(1): 87.

[27]

27. Clark, P. A. and Westerberg, A. W. (1990b), Bilevel programming for steady-state chemical process design-II. Performance study for nondegenerate designs. Comp. Chem. Engng. 14(1): 99.

[28]

28. Edmunds, T. A. and Bard, J. F. (1991), Algorithms for nonlinear bilevel mathematical programs. IEEE Trans. on Systems, Man and Cybernetics 21(1): 83-89.

[29]

29. Esposito, W. R. and Floudas, C. A. (1998), Global optimization in parameter estimation of nonlinear algebraic models via the error-in-variables Approach. Ind. Eng. Chem. Res. 37: 1841-1858.

[30]

30. Falk, J. E. and Liu, J. (1995), On Bilevel Programming. 1. General Nonlinear Cases. Mathematical Programming 70: 47-72.

Digital Library

[31]

31. Fiacco, A. V. (1976), Sensitivity analysis for nonlinear programming using penalty methods. Maths. Prog. 10: 287.

Digital Library

[32]

32. Floudas, C. A. (2000), Deterministic Global Optimization: Theory, Methods and Application , Vol. 37 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands.

Digital Library

[33]

33. Floudas, C. A., Pardalos, P. M., Adjiman, C. S., Esposito, W. R., Gümüs., Z. H., Harding, S. T., Klepeis, J. L., Meyer, C. A. and Schweiger, C. A. (1999), Handbook of Test Problems in Local and Global Optimization, Vol. 33 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands.

[34]

34. Floudas, C. A. and Zlobec, S. (1998), Optimality and duality in parametric convex lexicographic programming. In: Migdalas, A., Pardalos, P. M. and Värbrand, P. (eds), Multilevel Optimization: Algorithms and Applications, Vol. 20 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands. pp. 359-379.

[35]

35. Grossmann, I. E. and Floudas, C. A. (1987), Active constraint strategy for flexibility analysis in chemical processes. Comp. Chem. Engng. 11(6): 675.

[36]

36. Gümüs., Z. H. and Ciric, A. R. (1997), Reactive distillation column design with vapor/liquid/liquid equilibria. Comp. Chem. Engng. 21(S): S983.

[37]

37. Hansen, P., Jaumard, B. and Savard, G. (1992), New branch and bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing 13: 1194-1217.

Digital Library

[38]

38. Hobbs, B. F. and Nelson, S. K. (1992), A nonlinear bilevel model for analysis of electric utility demand-side planning issues. Annals of Operations Research 34: 255.

Digital Library

[39]

39. Ierapetritou, M. G. and Pistikopoulos, E. N. (1996), Batch plant design and operations under uncertainty. I&EC Res. 35: 772.

[40]

40. Ishizuka, Y. and Aiyoshi, E. (1992), Double penalty method for bilevel optimization problems. Annals of Operations Research 34: 73-88.

Digital Library

[41]

41. Jeroslow, R. G. (1985), The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32: 146.

[42]

42. Kim, I., Liebman, M. J. and Edgar, T. F. (1990), Robust error-in-variables estimation using nonlinear programming techniques. AIChE J. 36(7): 985-993.

[43]

43. Kolstad, C. D. (1985), A review of the literature on bilevel mathematical programming. Technical Report LA-10284-MS, US-32, Los Alamos National Lab.

[44]

44. LeBlanc, L. J. and Boyce, D. E. (1986), A bilevel programming algorithm for exact solution of the network design problem with user optimal flows. Trans. Res. B. 20B(3): 259.

[45]

45. Luh, P. B., Ho, Y. and Muralidaran, R. (1982), Load adaptive pricing: an emerging tool for electric utilities. IEEE Trans. Auto. Contr. AC-27(2): 320.

[46]

46. Luo, Z. Q., Pang, J. S. and Ralph, D. (1997), Mathematical Programs with Equilibrium Constraints. Cambridge University Press.

[47]

47. Maranas, C. D. and Floudas, C. A. (1994), A Global Optimization Method for Weber's Problem with Attraction and Repulsion. In: Hager, W. W., Hearn, D. W. and Pardalos, P. M. (eds), Large Scale Optimization: State of the Art. Kluwer Academic Publishers, Dordrecht, The Netherlands, p. 259.

[48]

48. Maranas, C. D. and Floudas, C. A. (1995), Finding all solutions of nonlinearly constrained systems of equations. Journal of Global Optimization 7(2): 143-182.

[49]

49. Marcotte, P. and Zhu, D. L. (1996), Exact and Inexact Penalty methods for the generalized bilevel programming problem. Mathematical Programming 74, 141-157.

Digital Library

[50]

50. Migdalas, A. (1995), Bilevel programming in traffic planning: models, methods and challenge. Journal of Global Optimization 7: 381.

[51]

51. Migdalas, A., Pardalos, P. M. and Värbrand, P. (1998), Multilevel optimization: Algorithms and Applications, Vol. 20 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands.

[52]

52. Onal, H., Darmawan, D. H. and Johnson III, S. H. (1995), A multilevel analysis of agricultural credit dstribution in East Java, Indonesia. Comp. Op. Res. 22(2): 227.

Digital Library

[53]

53. Pardalos, P. M. and Deng, X. (1997), Complexity Issues in Hierarchical Optimization. DIMACS Series, Americal Mathematical Society 37: 219-224.

[54]

54. Sahin, K. H. and Ciric, A. R. (1998), A dual temperature simulated annealing approach for solving bilevel programming problems. Comp. Chem. Engng. 23: 11-25.

[55]

55. Savard, G. and Gauvin, J. (1994), The steepest descent direction for the nonlinear bilevel programming problem. Operations Research Letters 15: 265-272.

Digital Library

[56]

56. Schweiger, C. S. and Floudas, C. A. (1998), MINOPT: A modeling language and algorithmic framework for linear, mixed-integer, nonlinear, dynamic and mixed-integer nonlinear optimization , Vol. Version 3.1. Princeton University.

[57]

57. Shimizu, K., Ishizuka, Y. and Bard, J. F. (1997), Nondifferentiable and Two-Level Mathematical Programming. Kluwer Academic Publishers, Dordrecht, The Netherlands.

[58]

58. Simaan, M. and Cruz, J. B. (1973), On the Stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications 11(5): 533.

Digital Library

[59]

59. Tuy, H., Migdalas, A. and Värbrand, P. (1993a), A global optimization approach for the linear two-level program. Journal of Global Optimization 3: 1.

[60]

60. Tuy, H., Migdalas, A. and Värbrand, P. (1993b), A quasiconcave minimization method for solving linear two-level programs. Journal of Global Optimization 4: 243.

[61]

61. Vicente, L. and Calamai, P. (1994), Bilevel and Multilevel Programming: A bibliography review. Journal of Global Optimization 5(2).

[62]

62. Vicente, L., Savard, G. and Judice, J. (1994), Descent approaches for quadratic bilevel programming. Journal of Optimization Theory and Applications 81(2): 379.

Digital Library

[63]

63. Viswanathan, J. and Grossmann, I. E. (1990), DICOPT++: A Program for Mixed Integer Non-linear Optimization, User's Guide. Engineering Design Research Center, Carnegie Mellon University.

[64]

64. Visweswaran, V., Floudas, C. A., Ierapetritou, M. G. and Pistikopoulos, E. N. (1996), A decomposition-based global optimization approach for solving bilevel linear and quadratic programs. In: Floudas, C. A. and Pardalos, P. M. (eds), State of the Art in Global Optimization, Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands, p. 139.

[65]

65. von Stackelberg, H.: (1952), The Theory of Market Economy. Oxford University Press.

[66]

66. White, D. J. and Anandalingam, G. (1993), A penalty function approach for solving bilevel linear programs. Journal of Global Optimization 3: 397-419.

[67]

67. Yang, H. and Yagar, S. (1995), Traffic Assignment and Signal Control in Saturated road networks. Trans. Res. A. 29A(2): 125.

Cited By

Xu WLin GWang TZhu X(2024)Stackelberg Pricing Game for Ride-Hailing Platforms With Combined Travel ModesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.342075125:11(15856-15870)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3420751
Zhang QLangari RTseng HMohan SSzwabowski SFilev D(2024)Stackelberg Differential Lane Change Game Based on MPC and Inverse MPCIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.338679025:8(8473-8485)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3386790
Katagiri HKato KUno THuang XZhang QYang Q(2017)Possibilistic Stackelberg solutions to bilevel linear programming problems with fuzzy parametersJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-16921332:6(4485-4501)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/JIFS-169213
Show More Cited By

Global Optimization of Nonlinear Bilevel Programming Problems
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Convergent Semidefinite Programming Relaxations for Global Bilevel Polynomial Optimization Problems

In this paper, we consider a bilevel polynomial optimization problem where the objective and the constraint functions of both the upper-and the lower-level problems are polynomials. We present methods for finding its global minimizers and global minimum ...
Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower's) ...
Global solution of nonlinear mixed-integer bilevel programs

An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475---513, 2008). The algorithm relies on a convergent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Global Optimization

Journal of Global Optimization Volume 20, Issue 1

May 2001

107 pages

ISSN:0925-5001

Issue’s Table of Contents

Copyright © Copyright © 2001 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 May 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xu WLin GWang TZhu X(2024)Stackelberg Pricing Game for Ride-Hailing Platforms With Combined Travel ModesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.342075125:11(15856-15870)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3420751
Zhang QLangari RTseng HMohan SSzwabowski SFilev D(2024)Stackelberg Differential Lane Change Game Based on MPC and Inverse MPCIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.338679025:8(8473-8485)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3386790
Katagiri HKato KUno THuang XZhang QYang Q(2017)Possibilistic Stackelberg solutions to bilevel linear programming problems with fuzzy parametersJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-16921332:6(4485-4501)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/JIFS-169213
Chuong TJeyakumar V(2017)Finding Robust Global Optimal Values of Bilevel Polynomial Programs with Uncertain Linear ConstraintsJournal of Optimization Theory and Applications10.1007/s10957-017-1069-4173:2(683-703)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s10957-017-1069-4
Kassa AKassa S(2017)Deterministic solution approach for some classes of nonlinear multilevel programs with multiple followersJournal of Global Optimization10.1007/s10898-017-0502-468:4(729-747)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10898-017-0502-4
Ren AWang Y(2017)An approach for solving a fuzzy bilevel programming problem through nearest interval approximation approach and KKT optimality conditionsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2144-821:18(5515-5526)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s00500-016-2144-8
Kassa AKassa S(2016)A branch-and-bound multi-parametric programming approach for non-convex multilevel optimization with polyhedral constraintsJournal of Global Optimization10.1007/s10898-015-0341-064:4(745-764)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s10898-015-0341-0
Jeyakumar VLi G(2015)A bilevel Farkas lemma to characterizing global solutions of a class of bilevel polynomial programsOperations Research Letters10.1016/j.orl.2015.05.00643:4(405-410)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.orl.2015.05.006
Lee YPang JMitchell J(2015)An algorithm for global solution to bi-parametric linear complementarity constrained linear programsJournal of Global Optimization10.1007/s10898-014-0228-562:2(263-297)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s10898-014-0228-5
Jiang YLi XHuang CWu X(2014)An augmented Lagrangian multiplier method based on a CHKS smoothing function for solving nonlinear bilevel programming problemsKnowledge-Based Systems10.1016/j.knosys.2013.08.01755(9-14)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.knosys.2013.08.017
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents