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 & 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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications,, Kluwer Academic, (1998).  doi: 10.1007/978-1-4757-2836-1.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

S. Dassanayaka, Methods of Variational Analysis in Pessimistic Bilevel Programming,, PhD Thesis, (2010).   Google Scholar

[11]

S. Dempe, Foundations of Bilevel Programming,, Nonconvex Optimization and its Applications Series, (2002).   Google Scholar

[12]

S. Dempe, Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints,, Optimization, 52 (2003), 333.  doi: 10.1080/0233193031000149894.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

J. L. Goffin, On convergence rates of subgradient optimization methods,, Mathematical Programming, 13 (1977), 329.  doi: 10.1007/BF01584346.  Google Scholar

[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.  Google Scholar

[17]

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

[18]

L. Mallozzi and J. Morgan, Hierarchical systems with weighted reaction set,, Nonlinear Optimization and Applications, (1996), 271.   Google Scholar

[19]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

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

[24]

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

[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.  Google Scholar

[26]

W. Wiesemann, A. Tsoukalas, P. Kleniati and B. Rustem, Pessimistic bilevel optimisation,, SIAM Journal on Optimization, 23 (2013), 353.  doi: 10.1137/120864015.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

A. Aboussoror and P. Loridan, Strong-weak Stackelberg problems in finite dimentional spaces,, Serdica Mathematical Journal, 21 (1995), 151.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications,, Kluwer Academic, (1998).  doi: 10.1007/978-1-4757-2836-1.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

S. Dassanayaka, Methods of Variational Analysis in Pessimistic Bilevel Programming,, PhD Thesis, (2010).   Google Scholar

[11]

S. Dempe, Foundations of Bilevel Programming,, Nonconvex Optimization and its Applications Series, (2002).   Google Scholar

[12]

S. Dempe, Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints,, Optimization, 52 (2003), 333.  doi: 10.1080/0233193031000149894.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

J. L. Goffin, On convergence rates of subgradient optimization methods,, Mathematical Programming, 13 (1977), 329.  doi: 10.1007/BF01584346.  Google Scholar

[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.  Google Scholar

[17]

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

[18]

L. Mallozzi and J. Morgan, Hierarchical systems with weighted reaction set,, Nonlinear Optimization and Applications, (1996), 271.   Google Scholar

[19]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

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

[24]

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

[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.  Google Scholar

[26]

W. Wiesemann, A. Tsoukalas, P. Kleniati and B. Rustem, Pessimistic bilevel optimisation,, SIAM Journal on Optimization, 23 (2013), 353.  doi: 10.1137/120864015.  Google Scholar

[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.  Google Scholar

[1]

He Zhang, John Harlim, Xiantao Li. Estimating linear response statistics using orthogonal polynomials: An RKHS formulation. Foundations of Data Science, 2020, 2 (4) : 443-485. doi: 10.3934/fods.2020021
[2]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018
[3]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[4]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[5]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[6]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006
[7]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020178
[8]

Andy Hammerlindl, Jana Rodriguez Hertz, Raúl Ures. Ergodicity and partial hyperbolicity on Seifert manifolds. Journal of Modern Dynamics, 2020, 0: 331-348. doi: 10.3934/jmd.2020012
[9]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170
[10]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073
[11]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264
[12]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404
[13]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253
[14]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468
[15]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[16]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[17]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[18]

Yantao Wang, Linlin Su. Monotone and nonmonotone clines with partial panmixia across a geographical barrier. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 4019-4037. doi: 10.3934/dcds.2020056
[19]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[20]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (66)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences