An active set quasi-Newton method with projection step for monotone nonlinear equations

Zhensheng Yu; Peixin Li; Zhensheng Yu; Peixin Li

doi:10.3934/math.2021215

AIMS Mathematics

2021, Volume 6, Issue 4: 3606-3623. doi: 10.3934/math.2021215

Previous Article Next Article

Research article

An active set quasi-Newton method with projection step for monotone nonlinear equations

Zhensheng Yu ^,,
Peixin Li

College of Science, University of Shanghai for Science and Technology, Shanghai, 200093, China

Received: 08 November 2020 Accepted: 15 January 2021 Published: 22 January 2021
MSC : 65K05, 90C30

In this paper, an active set quasi-Newton method for bound constrained nonlinear equation is proposed. By using this active set technique, we only need to solve a reduced dimension linear equation at each iteration to generate the search direction. The algorithm is a combination of the quasi-Newton method and projection method. Firstly we use the quasi-Newton step as the trial step and then use a projection technique to generate the next iteration point. Our key observation is that the algorithm generates a bounded iteration sequence automatically even if the bounds are equal to infinity and the global convergence is obtained in the sense that the whole sequence converges to the stationary point. The numerical tests show the efficiency of the algorithm.
- constrained nonlinear equations,
- active set,
- quasi-Newton,
- global convergence,
- projection
Citation: Zhensheng Yu, Peixin Li. An active set quasi-Newton method with projection step for monotone nonlinear equations[J]. AIMS Mathematics, 2021, 6(4): 3606-3623. doi: 10.3934/math.2021215

Related Papers:

Abstract

In this paper, an active set quasi-Newton method for bound constrained nonlinear equation is proposed. By using this active set technique, we only need to solve a reduced dimension linear equation at each iteration to generate the search direction. The algorithm is a combination of the quasi-Newton method and projection method. Firstly we use the quasi-Newton step as the trial step and then use a projection technique to generate the next iteration point. Our key observation is that the algorithm generates a bounded iteration sequence automatically even if the bounds are equal to infinity and the global convergence is obtained in the sense that the whole sequence converges to the stationary point. The numerical tests show the efficiency of the algorithm.

References

[1]	R. Andreani, A. Friedlander, Bound constrained smooth optimization for solving variational inequalities and related problems, Ann. Oper. Res., 116 (2002), 179–198. doi: 10.1023/A:1021336531779
[2]	D. P. Bertsekas, Projected Newton methods for optimization problems with simple constraints, SIAM J. Control. Optim., 20 (1982), 221–246. doi: 10.1137/0320018
[3]	S. Bellavia, M. Macconi, B. Morini, An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math., 44 (2003), 257–280. doi: 10.1016/S0168-9274(02)00170-8
[4]	S. Bellavia, M. Macconi, B. Morini, STRSCNE: A scaled trust-region solver for constrained nonlinear equations, Comput. Optim. Appl., 28 (2004), 31–50. doi: 10.1023/B:COAP.0000018878.95983.4e
[5]	S. Bellavia, B. Morini, S. Pieraccini, Constrained dogleg methods for nonlinear systems with simple bounds, Comput. Optim. Appl., 53 (2012), 771–794. doi: 10.1007/s10589-012-9469-8
[6]	F. Facchinei, A. Fischer, C. Kanzow, J. M. Peng, A simply constrained optimization reformulation of KKT systems arising from variational inequalities, Appl. Math. Optim., 40 (1999), 19–37. doi: 10.1007/s002459900114
[7]	C. Kanzow, H. D. Qi, A QP-free constrained Newton-type method for variational inequality problems, Math. Program., 85 (1997), 81–106.
[8]	C. Kanzow, Some equation-based methods for the nonlinear complementarity problem, Optim. Methods Softw., 3 (2007), 327–340.
[9]	M. Ulbrich, Nonmonotone trust-region methods for bound-constrained semismooth equations with applications to nonlinear mixed complementarity problems, SIAM J. Optim., 11 (2001), 889–917. doi: 10.1137/S1052623499356344
[10]	E. G. Birgina, N. Krejić, J. M. Martínez, Globally convergent inexact quasi-Newton methods for solving nonlinear systems, Numer. Algorithms, 32 (2003), 249–260. doi: 10.1023/A:1024013824524
[11]	A. Fischer, A. F. Izmailov, M. V. Solodov, Local attractors of Newton-type methods for constrained equations and complementarity problems with nonisolated solutions, J. Optim. Theory. Appl., 180 (2019), 140–169. doi: 10.1007/s10957-018-1297-2
[12]	F. Facchinei, J. Júdice, J. Soares, An active set Newton algorithm for large-scale nonlinear programs with box constraints, SIAM J. Optim., 8 (1998), 158–186. doi: 10.1137/S1052623493253991
[13]	C. Kanzow, An active set-type Newton method for constrained nonlinear systems, M.C. Ferris, O.L. Mangasarian, (Eds.), Boston: Springer, 2001.
[14]	L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp., 24 (1970), 27–30. doi: 10.1090/S0025-5718-1970-0258276-9
[15]	C. Kanzow, N. Yamashita, M. Fukushima, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 172 (2004), 375–397. doi: 10.1016/j.cam.2004.02.013
[16]	J. L. Zhang, On the convergence properties of the Levenberg-Marquardt method, Optimization, 52 (2003), 739–756. doi: 10.1080/0233193031000163993
[17]	J. M. Martińez, Practical quasi-Newton methods for solving nonlinear systems, J. Comput. Appl. Math., 124 (2000), 97–122. doi: 10.1016/S0377-0427(00)00434-9
[18]	S. Bellavia, S. Pieraccini, On affine-scaling inexact dogleg methods for bound-constrained nonlinear systems, Optim. Methods Softw., 30 (2015), 276–300. doi: 10.1080/10556788.2014.955496
[19]	C. J. Lin, J. Moré, Newton's method for large bound-constrained optimization problems, SIAM J. Optim., 9 (1999), 1100–1127. doi: 10.1137/S1052623498345075
[20]	R. H. Byrd, J. Nocedal, R. B. Schnabel, Representation of quasi-Newton matrices and their use in limited memory methods, Math. Program., 63 (1994), 129–156. doi: 10.1007/BF01582063
[21]	L. Marini, B. Morini, M. Porcelli, Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications, Comput. Optim. Appl., 71 (2018), 147–170. doi: 10.1007/s10589-018-9980-7
[22]	H. D. Qi, L. Q. Qi, D. F. Sun, Solving KKT systems via the trust region and the conjugate gradient methods, SIAM J. Optim., 14 (2004), 439–463.
[23]	M. V. Solodov, B. F. Svaiter, A globally convergent inexact Newton method for systems of monotone equations, M. Fukushima, L. Qi (Eds.), Boston: Springer, 1998.
[24]	Z. S. Yu, J. Lin, J. Sun, et.al. Spectral gradient projection method for mononote nonlinear equations with convex constraints, Appl. Numer. Math., 59 (2009), 2416–2423. doi: 10.1016/j.apnum.2009.04.004
[25]	A. M. Awwal, L. Wang, P. Kumam, H. Mohammad, W. Watthayu, A projection Hestenes-Stiefel method with spectral parameter for nonlinear monotone equations and signal processing, Math. Comput. Appl., 25 (2020), 27.
[26]	A. H. Ibrahim, P. Kumam, A. B. Abubakar, W. Jirakitpuwapat, J. Abubakar, A hybrid conjugate gradient algorithm for constrained monotone equations with application in compressive sensing, Heliyon, 6 (2020), e03466. doi: 10.1016/j.heliyon.2020.e03466
[27]	E. D. Dolan, J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201–213. doi: 10.1007/s101070100263

Reader Comments

Your name:*

Email:*
© 2021 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)