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
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. |
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
DownLoad: