Search Advanced

AIMS Mathematics

2022, Volume 7, Issue 9: 16112-16146. doi: 10.3934/math.2022882
Previous Article Next Article
Research article

An active-set with barrier method and trust-region mechanism to solve a nonlinear Bilevel programming problem

  • 1.
    Department of Mathematics and Computer Science, Alexandria University, Faculty of Science, Egypt
  • 2.
    Department of basic science, Tenth of Ramadan City, Higher Technological Institute, Egypt
  • Received: 17 March 2022 Revised: 26 April 2022 Accepted: 14 May 2022 Published: 01 July 2022

  • MSC : 49N10, 49N35, 65K05, 93D22, 93D52

  • Nonlinear Bilevel programming (NBLP) problem is a hard problem and very difficult to be resolved by using the classical method. In this paper, Karush-Kuhn-Tucker (KKT) condition is used with Fischer-Burmeister function to convert NBLP problem to an equivalent smooth single objective nonlinear programming (SONP) problem. An active-set strategy is used with Barrier method and trust-region technique to solve the smooth SONP problem effectively and guarantee a convergence to optimal solution from any starting point. A global convergence theory for the active-set barrier trust-region (ACBTR) algorithm is studied under five standard assumptions. An applications to mathematical programs are introduced to clarify the effectiveness of ACBTR algorithm. The results show that ACBTR algorithm is stable and capable of generating approximal optimal solution to the NBLP problem.

    Citation: B. El-Sobky, G. Ashry, Y. Abo-Elnaga. An active-set with barrier method and trust-region mechanism to solve a nonlinear Bilevel programming problem[J]. AIMS Mathematics, 2022, 7(9): 16112-16146. doi: 10.3934/math.2022882

    Related Papers:

  • Nonlinear Bilevel programming (NBLP) problem is a hard problem and very difficult to be resolved by using the classical method. In this paper, Karush-Kuhn-Tucker (KKT) condition is used with Fischer-Burmeister function to convert NBLP problem to an equivalent smooth single objective nonlinear programming (SONP) problem. An active-set strategy is used with Barrier method and trust-region technique to solve the smooth SONP problem effectively and guarantee a convergence to optimal solution from any starting point. A global convergence theory for the active-set barrier trust-region (ACBTR) algorithm is studied under five standard assumptions. An applications to mathematical programs are introduced to clarify the effectiveness of ACBTR algorithm. The results show that ACBTR algorithm is stable and capable of generating approximal optimal solution to the NBLP problem.


    加载中


    [1] D. Aksen, S. Akca, N. Aras, A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Comput. Oper. Res., 41 (2014), 346–358. https://doi.org/10.1016/j.cor.2012.08.013 doi: 10.1016/j.cor.2012.08.013
    [2] Y. Abo-Elnaga, M. El-Shorbagy, Multi-sine cosine algorithm for solving nonlinear bilevel programming problems, Int. J. Comput. Int. Sys., 13 (2020), 421–432. https://doi.org/10.2991/ijcis.d.200411.001 doi: 10.2991/ijcis.d.200411.001
    [3] A. Burgard, P. Pharkya, C. Maranas, Optknock: A bilevel programming framework for identifying gene knockout strategies formicrobial strain optimization, Biotechnol. Bioeng., 84 (2003), 647–657. https://doi.org/10.1002/bit.10803 doi: 10.1002/bit.10803
    [4] M. Bazaraa, H. Sherali, C. Shetty, Nonlinear programming theory and algorithms, Hoboken: John Wiley and Sons, 2006.
    [5] O. Ben-Ayed, O. Blair, Computational difficulty of bilevel linear programming, Oper. Res., 38 (1990), 556–560. https://doi.org/10.1287/opre.38.3.556 doi: 10.1287/opre.38.3.556
    [6] R. Byrd, Omojokun, Robust trust-region methods for nonlinearly constrained optimization, The second SIAM conference on optimization, 1987.
    [7] R. Byrd, J. Gilbert, J. Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89 (2000), 149–185. https://doi.org/10.1007/PL00011391 doi: 10.1007/PL00011391
    [8] J. Chen, The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, J. Glob. Optim., 36 (2006), 565–580. https://doi.org/10.1007/s10898-006-9027-y doi: 10.1007/s10898-006-9027-y
    [9] J. Chen, On some NCP-functions based on the generalized Fischer-Burmeister function, Asia Pac. J. Oper. Res., 24 (2007), 401–420. https://doi.org/10.1142/S0217595907001292 doi: 10.1142/S0217595907001292
    [10] J. Chen, S. Pan, A family of NCP-functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl., 40 (2008), 389–404. https://doi.org/10.1007/s10589-007-9086-0 doi: 10.1007/s10589-007-9086-0
    [11] J. Dennis, M. Heinkenschloss, L. Vicente. Trust-region interior-point SQP algorithms for a class of nonlinear programming problems. SIAM J. Control Optim., 36 (1998), 1750–1794. https://doi.org/10.1137/S036012995279031
    [12] J. Dennis, M. El-Alem, K. Williamson, A trust-region approach to nonlinear systems of equalities and inequalities, SIAM J. Optim., 9 (1999), 291–315. https://doi.org/10.1137/S1052623494276208 doi: 10.1137/S1052623494276208
    [13] S. Dempe, Foundation of bilevel programming, London: Kluwer Academic Publishers, 2002.
    [14] T. Edmunds, J. Bard, Algorithms for nonlinear bilevel mathematical programs, IEEE T. Syst. Man Cy., 21 (1991), 83–89. https://doi.org/10.1109/21.101139 doi: 10.1109/21.101139
    [15] B. El-Sobky, A robust trust-region algorithm for general nonlinear constrained optimization problems, PhD thesis, Alexandria University, 1998.
    [16] B. El-Sobky, A global convergence theory for an active trust region algorithm for solving the general nonlinear programming problem, Appl. Math. Comput., 144 (2003), 127–157. https://doi.org/10.1016/S0096-3003(02)00397-1 doi: 10.1016/S0096-3003(02)00397-1
    [17] B. El-Sobky, A Multiplier active-set trust-region algorithm for solving constrained optimization problem, Appl. Math. Comput., 219 (2012), 928–946. https://doi.org/10.1016/j.amc.2012.06.072 doi: 10.1016/j.amc.2012.06.072
    [18] B. El-Sobky, An interior-point penalty active-set trust-region algorithm, J. Egypt. Math. Soc., 24 (2016), 672–680. https://doi.org/10.1016/j.joems.2016.04.003 doi: 10.1016/j.joems.2016.04.003
    [19] B. El-Sobky, An active-set interior-point trust-region algorithm, Pac. J. Optim., 14 (2018), 125–159.
    [20] B. El-Sobky, A. Abotahoun, An active-set algorithm and a trust-region approach in constrained minimax problem, Comp. Appl. Math., 37 (2018), 2605–2631. https://doi.org/10.1007/s40314-017-0468-3 doi: 10.1007/s40314-017-0468-3
    [21] B. El-Sobky, A. Abotahoun, A trust-region algorithm for solving mini-max problem, J. Comput. Math., 36 (2018), 776–791. https://doi.org/10.4208/jcm.1705-m2016-0735 doi: 10.4208/jcm.1705-m2016-0735
    [22] B. El-Sobky, Y. Abouel-Naga, Multi-objective optimal load flow problem with interior-point trust-region strategy, Electr. Pow. Syst. Res., 148 (2017), 127–135. https://doi.org/10.1016/j.epsr.2017.03.014 doi: 10.1016/j.epsr.2017.03.014
    [23] B. El-Sobky, Y. Abouel-Naga, A penalty method with trust-region mechanism for nonlinear bilevel optimization problem, J. Comput. Appl. Math., 340 (2018), 360–374. https://doi.org/10.1016/j.cam.2018.03.004 doi: 10.1016/j.cam.2018.03.004
    [24] B. El-Sobky, Y.Abo-Elnaga, A. Mousa, A. El-Shorbagy, Trust-region based penalty barrier algorithm for constrained nonlinear programming problems: An application of design of minimum cost canal sections, Mathematics, 9 (2021), 1551. https://doi.org/10.3390/math9131551 doi: 10.3390/math9131551
    [25] B. El-Sobky, G. Ashry, An interior-point trust-region algorithm to solve a nonlinear bilevel programming problem, AIMS Mathematics, 7 (2022), 5534–5562. https://doi.org/10.3934/math.2022307 doi: 10.3934/math.2022307
    [26] A. Fiacco, G. McCormick. Nonlinear programming: Sequential unconstrained minimization techniques, New York: John Wiley and Sons, 1968.
    [27] J. Falk, J. M. Liu, On bilevel programming, Part I: General nonlinear cases, Math. Program., 70 (1995), 47–72. https://doi.org/10.1007/BF01585928 doi: 10.1007/BF01585928
    [28] F. Facchinei, H. Y. Jiang, L. Q. Qi, A smoothing method for mathematical programming with equilibrium constraints, Math. Program., 85 (1999), 107–134. https://doi.org/10.1007/s10107990015a doi: 10.1007/s10107990015a
    [29] H. Gumus, A. Flouda, Global optimization of nonlinear bilevel programming problems, J. Global Optim., 20 (2001), 1–31. https://doi.org/10.1023/A:1011268113791 doi: 10.1023/A:1011268113791
    [30] J. L. Gonzalez Velarde, J. F. Camacho-Vallejo, G. Pinto Serranoo, A scatter search algorithm for solving a bilevel optimization model for determining highway tolls, Comput. Syst., 19 (2015), 5–16. https://doi.org/10.13053/CyS-19-1-1916 doi: 10.13053/CyS-19-1-1916
    [31] M. Hestenes, Muliplier and gradient methods, J. Optim. Theorey Appl., 4 (1969), 303–320. https://doi.org/10.1007/BF00927673 doi: 10.1007/BF00927673
    [32] G. Hibino, M. Kainuma, Y. Matsuoka, Two-level mathematical programming for analyzing subsidy options to reduce greenhouse-gas emissions, IIASA Working Paper, 1996.
    [33] D. Kouri, M. Heinkenschloss, D. Ridzal, B. van Bloemen Waanders, A trust-region algorithm with adaptive stochastic collocation for PDE optimization under uncertainty, SIAM J. Sci. Comput., 35 (2013), A1847–A1879. https://doi.org/10.1137/120892362 doi: 10.1137/120892362
    [34] H. Li, Y. C. Jiao, L. Zhang, Orthogonal genetic algorithm for solving quadratic bilevel programming problems. J. Syst. Eng. Electron., 21 (2010), 763–770. https://doi.org/10.3969/j.issn.1004-4132.2010.05.008
    [35] Y. B. Lv, T. S. Hu, G. M. Wang, Z. P. Wan, A neural network approach for solving nonlinear bilevel programming problem, Comput. Math. Appl., 55 (2008), 2823–2829. https://doi.org/10.1016/j.camwa.2007.09.010 doi: 10.1016/j.camwa.2007.09.010
    [36] N. N. Li, D. Xue, W. Y. Sun, J. Wang, A stochastic trust-region method for unconstrained optimization problems, Math. Probl. Eng., 2019 (2019), 8095054. https://doi.org/10.1155/2019/8095054 doi: 10.1155/2019/8095054
    [37] L. M. Ma, G. M. Wang, A Solving algorithm for nonlinear bilevel programing problems based on human evolutionary model, Algorithms, 13 (2020), 260. https://doi.org/10.3390/a13100260 doi: 10.3390/a13100260
    [38] E. Omojokun, Trust-region strategies for optimization with nonlinear equality and inequality constraints, PhD thesis, University of Colorado, 1989.
    [39] T. Steihaug, The conjugate gradient method and trust-region in large scale optimization, SIAM J. Numer. Anal., 20 (1983), 626–637. https://doi.org/10.1137/0720042 doi: 10.1137/0720042
    [40] G. Savard, J. Gauvin, The steepest descent direction for the nonlinear bilevel programming problem, Oper. Res. Lett., 15 (1994), 265–272. https://doi.org/10.1016/0167-6377(94)90086-8 doi: 10.1016/0167-6377(94)90086-8
    [41] S. Sadatrasou, M. Gholamian, K. Shahanaghi, An application of data mining classification and bi-level programming for optimal credit allocation, Decis. Sci. Lett., 4 (2015), 35–50. https://doi.org/10.5267/j.dsl.2014.9.005 doi: 10.5267/j.dsl.2014.9.005
    [42] N. Thoai, Y. Yamamoto, A. Yoshise, Global optimization method for solving mathematical programs with linear complementarity constraints, Mathematical programs with complementarity, 2002.
    [43] M. Ulbrich, S. Ulbrich, L. N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100 (2004), 379–410. https://doi.org/10.1007/s10107-003-0477-4 doi: 10.1007/s10107-003-0477-4
    [44] Y. L. Wang, Y. C. Jiao, H. Li, An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme, IEEE T. Syst. Man Cy. C, 35 (2005), 221–232. https://doi.org/10.1109/TSMCC.2004.841908 doi: 10.1109/TSMCC.2004.841908
    [45] X. Wang, Y. X. Yuan, A trust region method based on a new affine scaling technique for simple bounded optimization, Optim. Method. Softw., 28 (2013), 871–888. https://doi.org/10.1080/10556788.2011.622378 doi: 10.1080/10556788.2011.622378
    [46] X. Wang, Y. X. Yuan, An augmented Lagrangian trust region method for equality constrained optimization, Optim. Method. Softw., 30 (2015), 559–582. https://doi.org/10.1080/10556788.2014.940947 doi: 10.1080/10556788.2014.940947
    [47] Y. X. Yuan, Recent advances in trust region algorithms. Math. Program., 151 (2015), 249–281. https://doi.org/10.1007/s10107-015-0893-2
    [48] M. Zeng, Q. Ni, A new trust region method for nonlinear equations involving fractional mode. Pac. J. Optim., 15 (2019), 317–329.
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(1324) PDF downloads(81) Cited by(2)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(4)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog