American Institute of Mathematical Sciences

Advanced
  • Previous Article
    On the Hölder continuity of approximate solution mappings to parametric weak generalized Ky Fan Inequality
  • JIMO Home
  • This Issue
  • Next Article
    Optimal selection of cleaner products in a green supply chain with risk aversion
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

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 and 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-170.

[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-408. 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-571. 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-1173. doi: 10.1109/9.58565.

[5]

J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications, Kluwer Academic, Dordrecht, 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-255. 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-141. 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-107. 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-256. doi: 10.1007/s10479-007-0176-2.

[10]

S. Dassanayaka, Methods of Variational Analysis in Pessimistic Bilevel Programming, PhD Thesis, Wayne State University, 2010.

[11]

S. Dempe, Foundations of Bilevel Programming, Nonconvex Optimization and its Applications Series, Kluwer Academic, Dordrecht, 2002.

[12]

S. Dempe, Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints, Optimization, 52 (2003), 333-359. 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-473. 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-533. doi: 10.1080/02331934.2012.696641.

[15]

J. L. Goffin, On convergence rates of subgradient optimization methods, Mathematical Programming, 13 (1977), 329-347. 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-1217. doi: 10.1137/0913069.

[17]

P. Loridan and J. Morgan, Weak via strong Stackelberg problem: New results, Journal of Global Optimization, 8 (1996), 263-287. doi: 10.1007/BF00121269.

[18]

L. Mallozzi and J. Morgan, Hierarchical systems with weighted reaction set, Nonlinear Optimization and Applications, Plenum Press, New York, (1996), 271-282.

[19]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970.

[20]

K. Shimizu, Y. Ishizuka and J. F. Bard, Nondifferentiable and Two-Level Mathematical Programming, Kluwer Academic, Dordrecht, 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-249. 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-306. doi: 10.1007/BF01096458.

[23]

G. Wang, Z. Wan and X. Wang, Bibliography on bilevel programming, Advances in Mathematics(in Chinese), 36 (2007), 513-529.

[24]

U. P. Wen and S. T. Hsu, Linear bilevel programming problems-a review, Journal of Operational Research Society, 42 (1991), 125-133.

[25]

D. J. White and G. Anandalingam, A penalty function approach for solving bi-level linear programs, Journal of Global Optimization, 3 (1993), 397-419. doi: 10.1007/BF01096412.

[26]

W. Wiesemann, A. Tsoukalas, P. Kleniati and B. Rustem, Pessimistic bilevel optimisation, SIAM Journal on Optimization, 23 (2013), 353-380. 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-1905. 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-170.

[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-408. 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-571. 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-1173. doi: 10.1109/9.58565.

[5]

J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications, Kluwer Academic, Dordrecht, 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-255. 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-141. 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-107. 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-256. doi: 10.1007/s10479-007-0176-2.

[10]

S. Dassanayaka, Methods of Variational Analysis in Pessimistic Bilevel Programming, PhD Thesis, Wayne State University, 2010.

[11]

S. Dempe, Foundations of Bilevel Programming, Nonconvex Optimization and its Applications Series, Kluwer Academic, Dordrecht, 2002.

[12]

S. Dempe, Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints, Optimization, 52 (2003), 333-359. 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-473. 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-533. doi: 10.1080/02331934.2012.696641.

[15]

J. L. Goffin, On convergence rates of subgradient optimization methods, Mathematical Programming, 13 (1977), 329-347. 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-1217. doi: 10.1137/0913069.

[17]

P. Loridan and J. Morgan, Weak via strong Stackelberg problem: New results, Journal of Global Optimization, 8 (1996), 263-287. doi: 10.1007/BF00121269.

[18]

L. Mallozzi and J. Morgan, Hierarchical systems with weighted reaction set, Nonlinear Optimization and Applications, Plenum Press, New York, (1996), 271-282.

[19]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970.

[20]

K. Shimizu, Y. Ishizuka and J. F. Bard, Nondifferentiable and Two-Level Mathematical Programming, Kluwer Academic, Dordrecht, 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-249. 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-306. doi: 10.1007/BF01096458.

[23]

G. Wang, Z. Wan and X. Wang, Bibliography on bilevel programming, Advances in Mathematics(in Chinese), 36 (2007), 513-529.

[24]

U. P. Wen and S. T. Hsu, Linear bilevel programming problems-a review, Journal of Operational Research Society, 42 (1991), 125-133.

[25]

D. J. White and G. Anandalingam, A penalty function approach for solving bi-level linear programs, Journal of Global Optimization, 3 (1993), 397-419. doi: 10.1007/BF01096412.

[26]

W. Wiesemann, A. Tsoukalas, P. Kleniati and B. Rustem, Pessimistic bilevel optimisation, SIAM Journal on Optimization, 23 (2013), 353-380. 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-1905. doi: 10.1137/080725088.

[1]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[2]

Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3209-3221. doi: 10.3934/jimo.2020114
[3]

Nazih Abderrazzak Gadhi. A note on the paper "Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem". Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021103
[4]

Qiang Du, Manlin Li. On the stochastic immersed boundary method with an implicit interface formulation. Discrete and Continuous Dynamical Systems - B, 2011, 15 (2) : 373-389. doi: 10.3934/dcdsb.2011.15.373
[5]

Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35
[6]

Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021032
[7]

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 and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[8]

Haiyang Wang, Jianfeng Zhang. Forward backward SDEs in weak formulation. Mathematical Control and Related Fields, 2018, 8 (3&4) : 1021-1049. doi: 10.3934/mcrf.2018044
[9]

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
[10]

Matthew M. Dunlop, Andrew M. Stuart. The Bayesian formulation of EIT: Analysis and algorithms. Inverse Problems and Imaging, 2016, 10 (4) : 1007-1036. doi: 10.3934/ipi.2016030
[11]

Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092
[12]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial and Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[13]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949
[14]

Mehdi Badsi, Martin Campos Pinto, Bruno Després. A minimization formulation of a bi-kinetic sheath. Kinetic and Related Models, 2016, 9 (4) : 621-656. doi: 10.3934/krm.2016010
[15]

Azmy S. Ackleh, Ben G. Fitzpatrick, Horst R. Thieme. Rate distributions and survival of the fittest: a formulation on the space of measures. Discrete and Continuous Dynamical Systems - B, 2005, 5 (4) : 917-928. doi: 10.3934/dcdsb.2005.5.917
[16]

André Nachbin, Roberto Ribeiro-Junior. A boundary integral formulation for particle trajectories in Stokes waves. Discrete and Continuous Dynamical Systems, 2014, 34 (8) : 3135-3153. doi: 10.3934/dcds.2014.34.3135
[17]

Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337
[18]

Lorenzo Brasco, Filippo Santambrogio. An equivalent path functional formulation of branched transportation problems. Discrete and Continuous Dynamical Systems, 2011, 29 (3) : 845-871. doi: 10.3934/dcds.2011.29.845
[19]

Andaluzia Matei, Mircea Sofonea. Dual formulation of a viscoplastic contact problem with unilateral constraint. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1587-1598. doi: 10.3934/dcdss.2013.6.1587
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (132)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy