Research article

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

  • 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搜索

Metrics

Article views(733) PDF downloads(56) Cited by(1)

Article outline

Figures and Tables

Tables(3)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog