A new method for strong-weak linear bilevel programming problem

Previous Article
Optimal selection of cleaner products in a green supply chain with risk aversion
JIMO Home
This Issue
Next Article
On the Hölder continuity of approximate solution mappings to parametric weak generalized Ky Fan Inequality

April 2015, 11(2): 529-547. doi: 10.3934/jimo.2015.11.529

A new method for strong-weak linear bilevel programming problem

Yue Zheng ^1, , Zhongping Wan ^2, , Shihui Jia ^3, and Guangmin Wang ^4,

1.	College of Mathematics and Physics, Huanggang Normal University, Huanggang 438000, China
2.	School of Mathematics and Statistics, Wuhan University, Wuhan, 430072
3.	School of Science, Wuhan University of Science and Technology, Wuhan 430081, China
4.	School of Economics and Management, China University of Geosciences, Wuhan 430074, China

Received October 2012 Revised April 2014 Published September 2014

Abstract
Related Papers

We first propose an exact penalty method to solve strong-weak linear bilevel programming problem (for short, SWLBP) for every fixed cooperation degree from the follower. Then, we prove that the solution of penalized problem is also that of the original problem under some conditions. Furthermore, we give some properties of the optimal value function (as a function of the follower's cooperation degree) of SWLBP. Finally, we develop a method to acquire the critical points of the optimal value function without enumerating all values of the cooperation degree from the follower, and thus this function is also achieved. Numerical results show that the proposed methods are feasible.

Keywords: partial cooperation, pessimistic formulation, penalty method, critical point., optimistic formulation, Bilevel programming.

Mathematics Subject Classification: Primary: 90C26, 90C3.

Citation: Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

References:

[1]	A. Aboussoror and P. Loridan, Strong-weak Stackelberg problems in finite dimentional spaces,, Serdica Mathematical Journal, 21 (1995), 151.
[2]	A. Aboussoror and A. Mansouri, Weak linear bilevel programming problems: Existence of solutions via a penalty method,, Journal of Mathematical Analysis and Applications, 304* (2005), 399. doi: 10.1016/j.jmaa.2004.09.033.*
[3]	A. Aboussoror, S. Adly and V. Jalby, Weak nonlinear bilevel problems: Existence of solutions via reverse convex and convex maximization problems,, Journal of Industrial and Management Optimization, 7 (2011), 559. doi: 10.3934/jimo.2011.7.559.
[4]	G. Anandalingam and D. J. White, A solution for the linear static Stackelberg problem using penalty function,, IEEE Transactions Automatic Control, 35 (1990), 1170. doi: 10.1109/9.58565.
[5]	J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications,, Kluwer Academic, (1998). doi: 10.1007/978-1-4757-2836-1.
[6]	M. Campelo, S. Dantas and S. Scheimberg, A note on a penalty function approach for solving bi-level linear programs,, Journal of Global Optimization, 16 (2000), 245. doi: 10.1023/A:1008308218364.
[7]	D. Cao and L. C. Leung, A partial cooperation model for non-unique linear two-level decision problems,, European Journal of Operational Research, 140* (2002), 134. doi: 10.1016/S0377-2217(01)00225-9.*
[8]	B. Colson, P. Marcotte and G. Savard, Bilevel programming: A survey,, 4OR: Q. J. Oper. Res., 3 (2005), 87. doi: 10.1007/s10288-005-0071-0.
[9]	B. Colson, P. Marcotte and G. Savard, An overview of bilevel optimization,, Ann. Oper. Res., 153* (2007), 235. doi: 10.1007/s10479-007-0176-2.*
[10]	S. Dassanayaka, Methods of Variational Analysis in Pessimistic Bilevel Programming,, PhD Thesis, (2010).
[11]	S. Dempe, Foundations of Bilevel Programming,, Nonconvex Optimization and its Applications Series, (2002).
[12]	S. Dempe, Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints,, Optimization, 52 (2003), 333. doi: 10.1080/0233193031000149894.
[13]	S. Dempe and A. B. Zemkoho, The bilevel programming problem: Reformulations, constraint qualifications and optimality conditions,, Mathematical Programming, 138* (2013), 447. doi: 10.1007/s10107-011-0508-5.*
[14]	S. Dempe, B. S. Mordukhovich and A. B. Zemkoho, Necessary optimality conditions in pessimistic bilevel programming,, Optimization, 63 (2014), 505. doi: 10.1080/02331934.2012.696641.
[15]	J. L. Goffin, On convergence rates of subgradient optimization methods,, Mathematical Programming, 13 (1977), 329. doi: 10.1007/BF01584346.
[16]	P. Hansen, B. Jaumard and G. Savard, New branch-and-bound rules for linear bilevel programming,, SIAM J. on Scientific and Statistical Computing, 13 (1992), 1194. doi: 10.1137/0913069.
[17]	P. Loridan and J. Morgan, Weak via strong Stackelberg problem: New results,, Journal of Global Optimization, 8 (1996), 263. doi: 10.1007/BF00121269.
[18]	L. Mallozzi and J. Morgan, Hierarchical systems with weighted reaction set,, Nonlinear Optimization and Applications, (1996), 271.
[19]	R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).
[20]	K. Shimizu, Y. Ishizuka and J. F. Bard, Nondifferentiable and Two-Level Mathematical Programming,, Kluwer Academic, (1997). doi: 10.1007/978-1-4615-6305-1.
[21]	M. Tawarmalani and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization,, Mathematical Programming, 103 (2005), 225. doi: 10.1007/s10107-005-0581-8.
[22]	L. N. Vicente and P. H. Calamai, Bilevel and multilevel programming: A bibliography review,, Journal of Global Optimization, 5 (1994), 291. doi: 10.1007/BF01096458.
[23]	G. Wang, Z. Wan and X. Wang, Bibliography on bilevel programming,, Advances in Mathematics(in Chinese), 36 (2007), 513.
[24]	U. P. Wen and S. T. Hsu, Linear bilevel programming problems-a review,, Journal of Operational Research Society, 42 (1991), 125.
[25]	D. J. White and G. Anandalingam, A penalty function approach for solving bi-level linear programs,, Journal of Global Optimization, 3 (1993), 397. doi: 10.1007/BF01096412.
[26]	W. Wiesemann, A. Tsoukalas, P. Kleniati and B. Rustem, Pessimistic bilevel optimisation,, SIAM Journal on Optimization, 23 (2013), 353. doi: 10.1137/120864015.
[27]	J. Ye and D. Zhu, New necessary optimality conditions for bilevel programs by combining the mpec and value function approaches,, SIAM Journal on Optimization, 20 (2010), 1885. doi: 10.1137/080725088.

show all references

References:

[1]	A. Aboussoror and P. Loridan, Strong-weak Stackelberg problems in finite dimentional spaces,, Serdica Mathematical Journal, 21 (1995), 151.
[2]	A. Aboussoror and A. Mansouri, Weak linear bilevel programming problems: Existence of solutions via a penalty method,, Journal of Mathematical Analysis and Applications, 304* (2005), 399. doi: 10.1016/j.jmaa.2004.09.033.*
[3]	A. Aboussoror, S. Adly and V. Jalby, Weak nonlinear bilevel problems: Existence of solutions via reverse convex and convex maximization problems,, Journal of Industrial and Management Optimization, 7 (2011), 559. doi: 10.3934/jimo.2011.7.559.
[4]	G. Anandalingam and D. J. White, A solution for the linear static Stackelberg problem using penalty function,, IEEE Transactions Automatic Control, 35 (1990), 1170. doi: 10.1109/9.58565.
[5]	J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications,, Kluwer Academic, (1998). doi: 10.1007/978-1-4757-2836-1.
[6]	M. Campelo, S. Dantas and S. Scheimberg, A note on a penalty function approach for solving bi-level linear programs,, Journal of Global Optimization, 16 (2000), 245. doi: 10.1023/A:1008308218364.
[7]	D. Cao and L. C. Leung, A partial cooperation model for non-unique linear two-level decision problems,, European Journal of Operational Research, 140* (2002), 134. doi: 10.1016/S0377-2217(01)00225-9.*
[8]	B. Colson, P. Marcotte and G. Savard, Bilevel programming: A survey,, 4OR: Q. J. Oper. Res., 3 (2005), 87. doi: 10.1007/s10288-005-0071-0.
[9]	B. Colson, P. Marcotte and G. Savard, An overview of bilevel optimization,, Ann. Oper. Res., 153* (2007), 235. doi: 10.1007/s10479-007-0176-2.*
[10]	S. Dassanayaka, Methods of Variational Analysis in Pessimistic Bilevel Programming,, PhD Thesis, (2010).
[11]	S. Dempe, Foundations of Bilevel Programming,, Nonconvex Optimization and its Applications Series, (2002).
[12]	S. Dempe, Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints,, Optimization, 52 (2003), 333. doi: 10.1080/0233193031000149894.
[13]	S. Dempe and A. B. Zemkoho, The bilevel programming problem: Reformulations, constraint qualifications and optimality conditions,, Mathematical Programming, 138* (2013), 447. doi: 10.1007/s10107-011-0508-5.*
[14]	S. Dempe, B. S. Mordukhovich and A. B. Zemkoho, Necessary optimality conditions in pessimistic bilevel programming,, Optimization, 63 (2014), 505. doi: 10.1080/02331934.2012.696641.
[15]	J. L. Goffin, On convergence rates of subgradient optimization methods,, Mathematical Programming, 13 (1977), 329. doi: 10.1007/BF01584346.
[16]	P. Hansen, B. Jaumard and G. Savard, New branch-and-bound rules for linear bilevel programming,, SIAM J. on Scientific and Statistical Computing, 13 (1992), 1194. doi: 10.1137/0913069.
[17]	P. Loridan and J. Morgan, Weak via strong Stackelberg problem: New results,, Journal of Global Optimization, 8 (1996), 263. doi: 10.1007/BF00121269.
[18]	L. Mallozzi and J. Morgan, Hierarchical systems with weighted reaction set,, Nonlinear Optimization and Applications, (1996), 271.
[19]	R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).
[20]	K. Shimizu, Y. Ishizuka and J. F. Bard, Nondifferentiable and Two-Level Mathematical Programming,, Kluwer Academic, (1997). doi: 10.1007/978-1-4615-6305-1.
[21]	M. Tawarmalani and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization,, Mathematical Programming, 103 (2005), 225. doi: 10.1007/s10107-005-0581-8.
[22]	L. N. Vicente and P. H. Calamai, Bilevel and multilevel programming: A bibliography review,, Journal of Global Optimization, 5 (1994), 291. doi: 10.1007/BF01096458.
[23]	G. Wang, Z. Wan and X. Wang, Bibliography on bilevel programming,, Advances in Mathematics(in Chinese), 36 (2007), 513.
[24]	U. P. Wen and S. T. Hsu, Linear bilevel programming problems-a review,, Journal of Operational Research Society, 42 (1991), 125.
[25]	D. J. White and G. Anandalingam, A penalty function approach for solving bi-level linear programs,, Journal of Global Optimization, 3 (1993), 397. doi: 10.1007/BF01096412.
[26]	W. Wiesemann, A. Tsoukalas, P. Kleniati and B. Rustem, Pessimistic bilevel optimisation,, SIAM Journal on Optimization, 23 (2013), 353. doi: 10.1137/120864015.
[27]	J. Ye and D. Zhu, New necessary optimality conditions for bilevel programs by combining the mpec and value function approaches,, SIAM Journal on Optimization, 20 (2010), 1885. doi: 10.1137/080725088.

[1]	Qiang Du, Manlin Li. On the stochastic immersed boundary method with an implicit interface formulation. Discrete & Continuous Dynamical Systems - B, 2011, 15 (2) : 373-389. doi: 10.3934/dcdsb.2011.15.373
[2]	Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35
[3]	Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[4]	Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092
[5]	François Gay-Balmaz, Tudor S. Ratiu. Clebsch optimal control formulation in mechanics. Journal of Geometric Mechanics, 2011, 3 (1) : 41-79. doi: 10.3934/jgm.2011.3.41
[6]	Matthew M. Dunlop, Andrew M. Stuart. The Bayesian formulation of EIT: Analysis and algorithms. Inverse Problems & Imaging, 2016, 10 (4) : 1007-1036. doi: 10.3934/ipi.2016030
[7]	Haiyang Wang, Jianfeng Zhang. Forward backward SDEs in weak formulation. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1021-1049. doi: 10.3934/mcrf.2018044
[8]	Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[9]	Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949
[10]	Mehdi Badsi, Martin Campos Pinto, Bruno Després. A minimization formulation of a bi-kinetic sheath. Kinetic & Related Models, 2016, 9 (4) : 621-656. doi: 10.3934/krm.2016010
[11]	Azmy S. Ackleh, Ben G. Fitzpatrick, Horst R. Thieme. Rate distributions and survival of the fittest: a formulation on the space of measures. Discrete & Continuous Dynamical Systems - B, 2005, 5 (4) : 917-928. doi: 10.3934/dcdsb.2005.5.917
[12]	André Nachbin, Roberto Ribeiro-Junior. A boundary integral formulation for particle trajectories in Stokes waves. Discrete & Continuous Dynamical Systems - A, 2014, 34 (8) : 3135-3153. doi: 10.3934/dcds.2014.34.3135
[13]	Lorenzo Brasco, Filippo Santambrogio. An equivalent path functional formulation of branched transportation problems. Discrete & Continuous Dynamical Systems - A, 2011, 29 (3) : 845-871. doi: 10.3934/dcds.2011.29.845
[14]	Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337
[15]	Andaluzia Matei, Mircea Sofonea. Dual formulation of a viscoplastic contact problem with unilateral constraint. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1587-1598. doi: 10.3934/dcdss.2013.6.1587
[16]	Francesco Demontis, Cornelis Van der Mee. Novel formulation of inverse scattering and characterization of scattering data. Conference Publications, 2011, 2011 (Special) : 343-350. doi: 10.3934/proc.2011.2011.343
[17]	Wenjun Xia, Jinzhi Lei. Formulation of the protein synthesis rate with sequence information. Mathematical Biosciences & Engineering, 2018, 15 (2) : 507-522. doi: 10.3934/mbe.2018023
[18]	Christian Hofer, Georg Jäger, Manfred Füllsack. Critical transitions and Early Warning Signals in repeated Cooperation Games. Journal of Dynamics & Games, 2018, 5 (3) : 223-230. doi: 10.3934/jdg.2018014
[19]	Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[20]	Manh Hong Duong, Hoang Minh Tran. On the fundamental solution and a variational formulation for a degenerate diffusion of Kolmogorov type. Discrete & Continuous Dynamical Systems - A, 2018, 38 (7) : 3407-3438. doi: 10.3934/dcds.2018146

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences