Search Advanced

AIMS Mathematics

2022, Volume 7, Issue 4: 5534-5562. doi: 10.3934/math.2022307
Previous Article Next Article
Research article

An interior-point trust-region algorithm to solve a nonlinear bilevel programming problem

  • Department of Mathematics and Computer Science, Alexandria University, Faculty of Science, Egypt
  • Received: 22 September 2021 Revised: 16 December 2021 Accepted: 29 December 2021 Published: 10 January 2022

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

  • In this paper, a nonlinear bilevel programming (NBLP) problem is transformed into an equivalent smooth single objective nonlinear programming (SONP) problem utilized slack variable with a Karush-Kuhn-Tucker (KKT) condition. To solve the equivalent smooth SONP problem effectively, an interior-point Newton's method with Das scaling matrix is used. This method is locally method and to guarantee convergence from any starting point, a trust-region strategy is used. The proposed algorithm is proved to be stable and capable of generating approximal optimal solution to the nonlinear bilevel programming problem.

    A global convergence theory of the proposed algorithm is introduced and applications to mathematical programs with equilibrium constraints are given to clarify the effectiveness of the proposed approach.

    Citation: B. El-Sobky, G. Ashry. An interior-point trust-region algorithm to solve a nonlinear bilevel programming problem[J]. AIMS Mathematics, 2022, 7(4): 5534-5562. doi: 10.3934/math.2022307

    Related Papers:

  • In this paper, a nonlinear bilevel programming (NBLP) problem is transformed into an equivalent smooth single objective nonlinear programming (SONP) problem utilized slack variable with a Karush-Kuhn-Tucker (KKT) condition. To solve the equivalent smooth SONP problem effectively, an interior-point Newton's method with Das scaling matrix is used. This method is locally method and to guarantee convergence from any starting point, a trust-region strategy is used. The proposed algorithm is proved to be stable and capable of generating approximal optimal solution to the nonlinear bilevel programming problem.

    A global convergence theory of the proposed algorithm is introduced and applications to mathematical programs with equilibrium constraints are given to clarify the effectiveness of the proposed approach.


    加载中


    [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] Y. Abo-Elnaga, S. Nasr, Modified Evolutionary Algorithm and Chaotic Search for Bilevel Programming Problems, Symmetry, 12 (2020), 1–29. https://doi.org/10.3390/sym12050767 doi: 10.3390/sym12050767
    [4] Y. Abo-Elnag, S. Nasr, K-means cluster interactive algorithm-basedevolutionary approach for solving bilevel multi-objective programming problems, Alexandria Engineering Journal, 61 (2022), 811–827. https://doi.org/10.1016/j.aej.2021.04.098 doi: 10.1016/j.aej.2021.04.098
    [5] M. Bazaraa, H. Sherali, C. Shetty, Nonlinear programming theory and algorithms, John Wiley and Sons, 2006. https://doi.org/10.1002/0471787779
    [6] R. Byrd, Omojokun, Robust trust-region methods for nonlinearly constrained optimization, A talk presented at the Second SIAM Conference on Optimization, Houston, TX, 1987.
    [7] 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
    [8] 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
    [9] R. Byrd, M. Hribar, J. Nocedal, An interior point algorithm for largescale nonlinear programming, SIAM J. Optim., 9 (1999), 877–900. https://doi.org/10.1137/S1052623497325107 doi: 10.1137/S1052623497325107
    [10] 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
    [11] F. E. Curtis, O. Schenk, A. Wachter, An interior-point algorithm for large-scale nonlinear optimization with inexact step computations, SIAM J. Sci. Comput., 32 (2010), 3447–3475. https://doi.org/10.1137/090747634 doi: 10.1137/090747634
    [12] I. Das, An interior point algorithm for the general nonlinear programming problem with trust region globlization, Technical Report 96-61, Institute for Computer Applications in Science and Engineering, NASA Langley Research Center Hampton, VA, USA, 1996.
    [13] 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 doi: 10.1137/S036012995279031
    [14] S. Dempe, Foundations of Bilevel Programming, Kluwer Academic Publishers, London, 2002.
    [15] H. Esmaeili, M. Kimiaei, An efficient implementation of a trust-region method for box constrained optimization, J. Appl. Math. Comput., 48 (2015), 495–517. https://doi.org/10.1007/s12190-014-0815-0 doi: 10.1007/s12190-014-0815-0
    [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, Journal of the Egyptian Mathematical Society, 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, 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
    [21] 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
    [22] B. El-Sobky, A. Abotahoun, An active-set algorithm and a trust-region approach in constrained minimax problem, Comput. Appl. Math., 37 (2018), 2605–2631. https://doi.org/10.1007/s40314-017-0468-3 doi: 10.1007/s40314-017-0468-3
    [23] B. El-Sobky, A. Abotahoun, A Trust-Region Algorithm for Solving Mini-Max Problem, J. Comput. Math., 36 (2018), 881–902. https://doi.org/10.4208/jcm.1705-m2016-0735 doi: 10.4208/jcm.1705-m2016-0735
    [24] T. Edmunds, J. Bard, Algorithms for nonlinear bilevel mathematical programs, IEEE transactions on Systems, Man, and Cybernetics, 21 (1991), 83–89. https://doi.org/10.1109/21.101139 doi: 10.1109/21.101139
    [25] J. Falk, J. Liu, On bilevel programming, Part Ⅰ: general nonlinear cases, Math. Program., 70 (1995), 47–72. https://doi.org/10.1007/BF01585928 doi: 10.1007/BF01585928
    [26] M. Hestenes, Muliplier and gradient methods, J. Optimiz. Theory App., 4 (1969), 303–320. https://doi.org/10.1007/BF00927673 doi: 10.1007/BF00927673
    [27] Z. H. Gumus, C. A. Flouda, Global Optimization of Nonlinear Bilevel Programming Problems, J. Global Optim., 20 (2001), 1–31.
    [28] V. Gonzlez, J. Vallejo, G. Serrano, A scatter search algorithm for solving a bilevel optimization model for determining highway tolls, Comput. Syst., 19 (2015), 3529–3549. https://doi.org/10.13053/cys-19-1-1916 doi: 10.13053/cys-19-1-1916
    [29] G. Hibino, M. Kainuma, Y. Matsuoka, Two-level mathematical programming for analyzing subsidy options to reduce greenhouse-gas emissions, Tech. Report WP-96-129, IIASA, Laxenburg, Austria, 1996.
    [30] 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 (2020), 1847–1879. https://doi.org/10.1137/120892362 doi: 10.1137/120892362
    [31] H. Li, Y. 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 doi: 10.3969/j.issn.1004-4132.2010.05.008
    [32] N. Li, D. Xue, W. Sun, J. Wang, A stochastic trust-region method for unconstrained optimization problems, Math. Probl. Eng., (2019). https://doi.org/10.1155/2019/8095054 doi: 10.1155/2019/8095054
    [33] Y. Lva, T. Hua, G. Wanga, Z. Wanb, 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
    [34] W. Ma, M. Wang, X. Zhu, Improved particle swarm optimization based approach for bilevel programming problem-an application on supply chain model, Int. J. Mach. Learn. Cyber, 5 (2014), 281–290. https://doi.org/10.1007/s13042-013-0167-3 doi: 10.1007/s13042-013-0167-3
    [35] L. Ma, G. Wang, A Solving Algorithm for Nonlinear Bilevel Programing Problems Based on Human Evolutionary Model, Algorithms, 13 (2020), 1–12. https://doi.org/10.3390/a13100260 doi: 10.3390/a13100260
    [36] L. F. Niu, Y. Yuan, A new trust region algorithm for nonlinear constrained optimization, J. Comput. Math., 28 (2010), 72–86. https://doi.org/10.4208/jcm.2009.09-m2924 doi: 10.4208/jcm.2009.09-m2924
    [37] E. Omojokun, Trust-region strategies for optimization with nonlinear equality and inequality constraints, PhD thesis, Department of Computer Science, University of Colorado, Boulder, Colorado, 1989.
    [38] 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
    [39] 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
    [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] N. Thoai, Y. Yamamoto, A. Yoshise, Global optimization method for solving mathematical programs with linear complementarity constraints, Discussion Paper No. 987, Institute of Policy and Planning Sciences, University of Tsukuba, Japan, 2002.
    [42] X. Wang, Y. Yuan, A trust region method based on a new affine scaling technique for simple bounded optimization, Optimization Methods and Software, 28 (2013), 871–888. https://doi.org/10.1080/10556788.2011.622378 doi: 10.1080/10556788.2011.622378
    [43] X. Wang, Y. Yuan, An augmented Lagrangian trust region method for equality constrained optimization, Optimization Methods and Software, 30 (2015), 559–582. https://doi.org/10.1080/10556788.2014.940947 doi: 10.1080/10556788.2014.940947
    [44] Y. Wang, Y. 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] Y. Yuan, Recent advances in trust region algorithms, Math. Program. Ser. B, 151 (2015), 249–281. https://doi.org/10.1007/s10107-015-0893-2 doi: 10.1007/s10107-015-0893-2
    [46] 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
2.2 3

Metrics

Article views(1408) PDF downloads(58) Cited by(3)

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