Search Advanced

AIMS Mathematics

2024, Volume 9, Issue 3: 6528-6554. doi: 10.3934/math.2024318
Previous Article Next Article
Research article

A nonmonton active interior point trust region algorithm based on CHKS smoothing function for solving nonlinear bilevel programming problems

  • 1.
    Department of Mathematics, Faculty of Science, Alexandria University, Alexandria, Egypt
  • 2.
    Department of basic science, Tenth of Ramadan City, Higher Technological Institute, Egypt
  • 3.
    Department of Physics and Engineering Mathematics, Faculty of Engineering-Tanta University, Egypt
  • Received: 30 October 2023 Revised: 27 December 2023 Accepted: 29 December 2023 Published: 06 February 2024

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

  • In this paper, an approach is suggested to solve nonlinear bilevel programming (NBLP) problems. In the suggested method, we convert the NBLP problem into a standard nonlinear programming problem with complementary constraints by applying the Karush-Kuhn-Tucker condition to the lower-level problem. By using the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, the nonlinear programming problem is successively smoothed. A nonmonton active interior-point trust-region algorithm is introduced to solve the smoothed nonlinear programming problem to obtain an approximately optimal solution to the NBLP problem. Results from simulations on several benchmark problems and a real-world case about a watershed trading decision-making problem show how the effectiveness of the suggested approach in NBLP solution development.

    Citation: B. El-Sobky, Y. Abo-Elnaga, G. Ashry, M. Zidan. A nonmonton active interior point trust region algorithm based on CHKS smoothing function for solving nonlinear bilevel programming problems[J]. AIMS Mathematics, 2024, 9(3): 6528-6554. doi: 10.3934/math.2024318

    Related Papers:

  • In this paper, an approach is suggested to solve nonlinear bilevel programming (NBLP) problems. In the suggested method, we convert the NBLP problem into a standard nonlinear programming problem with complementary constraints by applying the Karush-Kuhn-Tucker condition to the lower-level problem. By using the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, the nonlinear programming problem is successively smoothed. A nonmonton active interior-point trust-region algorithm is introduced to solve the smoothed nonlinear programming problem to obtain an approximately optimal solution to the NBLP problem. Results from simulations on several benchmark problems and a real-world case about a watershed trading decision-making problem show how the effectiveness of the suggested approach in NBLP solution development.


    加载中


    [1] M. A. Amouzegar, A global optimization method for nonlinear bilevel programming problems, IEEE Trans. Syst. Men Cybernet., 29 (1999), 771–777. https://doi.org/10.1109/3477.809031 doi: 10.1109/3477.809031
    [2] R. Byrd, Omojokun, Robust trust-region methods for nonlinearly constrained optimization, In: Second SIAM Conference on Optimization, Houston, 1987.
    [3] J. F. Bard, Coordination of a multidivisional organization through two levels of management, Omega, 11 (1983), 457–468. https://doi.org/10.1016/0305-0483(83)90038-5 doi: 10.1016/0305-0483(83)90038-5
    [4] J. F. Bard, Convex two-level optimization, Math. Program., 40 (1988), 15–27. https://doi.org/10.1007/BF01580720 doi: 10.1007/BF01580720
    [5] B. Chen, P. T. Harker, A non-interior-point continuation method for linear complementarity problem, SIAM J. Matrix Anal. Appl., 14 (1993), 1168–1190. https://doi.org/10.1137/0614081 doi: 10.1137/0614081
    [6] I. Das, An interior point algorithm for the general nonlinear programming problem with trust region globlization, In: Technical Report, 1996.
    [7] 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
    [8] 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
    [9] N. Y. Deng, Y. Xiao, F. J. Zhou, Nonmonotonic trust region algorithm, J. Optim. Theory Appl., 76 (1993), 259–285. https://doi.org/10.1007/BF00939608 doi: 10.1007/BF00939608
    [10] B. El-Sobky, A multiplier active trust-region algorithm for solving general nonlinear programming problem, Appl. Math. Comput., 219 (2012), 928–946.
    [11] 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
    [12] B. El-Sobky, An active-set interior-point trust-region algorithm, Pacific J. Optim., 14 (2018), 125–159.
    [13] 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
    [14] B. El-Sobky, A. Abotahoun, A trust-region algorithm for solving mini-max problem, J. Comput. Math., 36 (2018), 881–902.
    [15] 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
    [16] 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
    [17] B. El-Sobky, G. Ashry, An interior-point trust-region algorithm to solve a nonlinear bilevel programming problem, AIMS Math., 7 (2022), 5534–5562. http://dx.doi.org/10.3934/math.2022307 doi: 10.3934/math.2022307
    [18] B. El-Sobky, G. Ashry, An Active-set Fischer-Burmeister trust-region algorithm to solve a nonlinear bilevel optimization problem, Fractal Fract., 6 (2022), 412. https://doi.org/10.3390/fractalfract6080412 doi: 10.3390/fractalfract6080412
    [19] 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, AIMS Math., 7 (2022), 16112–16146. http://dx.doi.org/10.3934/math.2022882 doi: 10.3934/math.2022882
    [20] B. El-Sobky, M. F. Zidan, A trust-region based an active-set interior-point algorithm for fuzzy continuous Static Games, AIMS Math., 8 (2023), 13706–13724. http://dx.doi.org/10.3934/math.2023696 doi: 10.3934/math.2023696
    [21] J. B. E. Etoa, Solving quadratic convex bilevel programming problems using a smoothing method, Appl. Math. Comput., 217 (2011), 6680–6690. https://doi.org/10.1016/j.amc.2011.01.066 doi: 10.1016/j.amc.2011.01.066
    [22] J. E. Falk, J. M. Liu, On bilevel programming, Part Ⅰ: general nonlinear cases, Math. Program., 70 (1995), 47–72. https://doi.org/10.1007/BF01585928 doi: 10.1007/BF01585928
    [23] 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
    [24] Y. Ishizuka, E. Aiyoshi, Double penalty method for bilevel optimization problems, Ann. Oper. Res., 34 (1992), 73–88. https://doi.org/10.1007/BF02098173 doi: 10.1007/BF02098173
    [25] Y. Jiang, X. Li, C. Huang, X. Wu, Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bilevel programming problem, Appl. Math. Comput., 219 (2013), 4332–4339. https://doi.org/10.1016/j.amc.2012.10.010 doi: 10.1016/j.amc.2012.10.010
    [26] C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17 (1996), 851–868. https://doi.org/10.1137/S0895479894273134 doi: 10.1137/S0895479894273134
    [27] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671–680. https://doi.org/10.1126/science.220.4598.671 doi: 10.1126/science.220.4598.671
    [28] H. Li, Y. Jiao, L. Zhang, Orthogonal genetic algorithm for solving quadratic bilevel programming problems, J. Syst. Eng. Elect., 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
    [29] Y. B. Lv, T. S. Hu, G. M. Wang, Z. P. Wan, A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming, Appl. Math. Comput., 188 (2007) 808–813. https://doi.org/10.1016/j.amc.2006.10.045 doi: 10.1016/j.amc.2006.10.045
    [30] D. Muu, N. Quy, A global optimization method for solving convex quadratic bilevel programming problems, J. Global Optim., 26 (2003), 199–219. https://doi.org/10.1023/A:1023047900333 doi: 10.1023/A:1023047900333
    [31] J. Mo, C. Liu, S. Yan, A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function value, J. Comput. Appl. Math., 209 (2007), 97–108. https://doi.org/10.1016/j.cam.2006.10.070 doi: 10.1016/j.cam.2006.10.070
    [32] 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.
    [33] V. Oduguwa, R. Roy, Bi-level optimization using genetic algorithm, In: Proceedings 2002 IEEE International Conference on Artificial Intelligence Systems (ICAIS 2002), 2002,123–128. https://doi.org/10.1109/ICAIS.2002.1048121
    [34] T. Steihaug, The conjugate gradient method and trust-region in large scale optimization, SIAM J. Numer. Anal., 20 (1983), 0720042. https://doi.org/10.1137/0720042 doi: 10.1137/0720042
    [35] S. Smale, Algorithms for solving equations, In: Proceeding of International Congress of Mathematicians, American Mathematics Society, Rhode Island, 1987, 72–195.
    [36] 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
    [37] Z. J. Shi, J. H. Guo, A new trust region methods for unconstrained optimization, J. Comput. Appl. Math., 213 (2008), 509–520. https://doi.org/10.1016/j.cam.2007.01.027 doi: 10.1016/j.cam.2007.01.027
    [38] P. L. Toint, Non-monotone trust-region algorithm for nonlinear optimization subject to convex constraints, Math. Program., 77 (1997), 69–94. https://doi.org/10.1007/BF02614518 doi: 10.1007/BF02614518
    [39] Y. Yuan, On the convergence of a new trust region algorithm, Numer. Math., 70 (1995), 515–539. https://doi.org/10.1007/s002110050133 doi: 10.1007/s002110050133
    [40] 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
    [41] G. M. Wang, X. J. Wang, Z. P. Wan, Y. B. Lv, A globally convergent algorithm for a class of bilevel nonlinear programming problem, Appl. Math. Comput., 188 (2007), 166–172. https://doi.org/10.1016/j.amc.2006.09.130 doi: 10.1016/j.amc.2006.09.130
    [42] C. Y. Wu, Y. Z. Zhao, Watershed water trading decision-making model based on bilevel programming, Oper. Res. Manage. Sci., in Chinese, 20 (2011), 30–37.
    [43] X. S. Zhang, J. L. Zhang, L. Z. Liao, A nonmonotone adaptive trust region method and its convergence, Comput. Math. Appl., 45 (2003), 1469–1477. https://doi.org/10.1016/S0898-1221(03)00130-5 doi: 10.1016/S0898-1221(03)00130-5
    [44] H. C. Zhang, W. W. Hager, A nonmonotone line search technique for unconstrained optimization, SIAM J. Optim., 14 (2004), 1043–1056.
  • Reader Comments
  • © 2024 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(447) PDF downloads(47) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(3)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog