×

zbMATH — the first resource for mathematics

Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications. (English) Zbl 1405.90143
Summary: We address the solution of constrained nonlinear systems by new linesearch quasi-Newton methods. These methods are based on a proper use of the projection map onto the convex constraint set and on a derivative-free and nonmonotone linesearch strategy. The convergence properties of the proposed methods are presented along with a worst-case iteration complexity bound. Several implementations of the proposed scheme are discussed and validated on bound-constrained problems including gas distribution network models. The results reported show that the new methods are very efficient and competitive with an existing affine-scaling procedure.
Reviewer: Reviewer (Berlin)

MSC:
90C53 Methods of quasi-Newton type
90C30 Nonlinear programming
Software:
BFO; levmar; STRSCNE; TRESNEI
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bellavia, S; Macconi, M; Morini, B, An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math., 44, 257-280, (2003) · Zbl 1018.65067
[2] Bellavia, S; Morini, B, Subspace trust-region methods for large bound-constrained nonlinear equations, SIAM J. Numer. Anal., 44, 1535-1555, (2006) · Zbl 1128.65033
[3] Bellavia, S; Pieraccini, S, On affine-scaling inexact dogleg methods for bound-constrained nonlinear systems, Optim. Methods Softw., 30, 276-300, (2015) · Zbl 1325.90100
[4] Birgin, EG; Krejić, N; Martínez, JM, Globally convergent inexact quasi-Newton methods for solving nonlinear equations, Numer. Algorithms, 32, 249-260, (2003) · Zbl 1034.65032
[5] Bogle, IDL; Perkins, JD, A new sparsity preserving quasi-Newton update for solving nonlinear equations, SIAM J. Sci. Stat. Comput., 11, 621-630, (1990) · Zbl 0749.65033
[6] Broyden, CG, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comput., 25, 285-294, (1971) · Zbl 0227.65038
[7] Carcasci, C; Marini, L; Morini, B; Porcelli, M, A new modular procedure for industrial plant simulations and its reliable implementation, Energy, 94, 380-390, (2016)
[8] Coleman, TF; Li, Y, An interior trust region approach for nonlinear minimization subject to bounds, SIAM J. Optim., 6, 418-445, (1996) · Zbl 0855.65063
[9] Curtis, AR; Powell, MJD; Reid, JK, On the estimation of sparse Jacobian matrices, IMA J. Appl. Math., 13, 117-119, (1974) · Zbl 0273.65036
[10] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall, Englewood Cliffs (1983) · Zbl 0579.65058
[11] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[12] Gonçalves, MLN; Melo, JG, A Newton conditional gradient method for constrained nonlinear systems, J. Comput. Appl. Math., 311, 473-483, (2017) · Zbl 1382.65141
[13] Gonçalves, M.L.N., Oliveira, F.R.: An inexact Newton-like conditional gradient method for constrained nonlinear systems. arXiv:1705.07684 (2017)
[14] Griewank, A, The global convergence of Broyden-like methods with a suitable line search, J. Aust. Math. Soc. Ser. B, 28, 75-92, (1986) · Zbl 0596.65034
[15] Kanzow, C; Ferris, MC (ed.); Mangasarian, OL (ed.); Pang, J-S (ed.), An active set-type Newton method for constrained nonlinear systems, 179-200, (2001), Dordrecht
[16] Kanzow, C; Yamashita, N; Fukushima, M, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 172, 375-397, (2004) · Zbl 1064.65037
[17] Cruz, W, A projected derivative-free algorithm for nonlinear equations with convex constraints, Optim. Methods Softw., 29, 24-41, (2014) · Zbl 1285.65028
[18] Cruz, W; Martínez, JM; Raydan, M, Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comput., 18, 1429-1448, (2006) · Zbl 1122.65049
[19] Cruz, W; Raydan, M, Nonmonotone spectral methods for large-scale nonlinear systems, Optim. Methods Softw., 18, 583-599, (2003) · Zbl 1069.65056
[20] Li, DH; Fukushima, M, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Softw., 13, 181-201, (2000) · Zbl 0960.65076
[21] Lukšan, L., Vlček, J.: Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations. Optim. Methods Softw. 8, 201-223 (1998) · Zbl 0927.65068
[22] Lukšan, L., Vlček, J.: Test problems for unconstrained optimization. Tech. Rep. V-897, ICS AS CR, November (2003)
[23] Macconi, M; Morini, B; Porcelli, M, Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities, Appl. Numer. Math., 59, 859-876, (2009) · Zbl 1165.65030
[24] Martínez, JM, Practical quasi-Newton methods for solving nonlinear systems, J. Comput. Appl. Math., 124, 97-121, (2000) · Zbl 0967.65065
[25] Martínez, JM; Zambaldi, M, An inverse column-updating method for solving large-scale nonlinear systems of equations, Optim. Methods Softw., 1, 129-140, (1992)
[26] Morini, B; Porcelli, M, TRESNEI, a Matlab trust-region solver for systems of nonlinear equalities and inequalities, Comput. Optim. Appl., 51, 27-49, (2012) · Zbl 1244.90224
[27] Morini, B., Porcelli, M., Toint, P.L.: Approximate norm descent methods for constrained nonlinear systems. Math. Comput. electronically published on May 11 (2017). https://doi.org/10.1090/mcom/3251 (to appear in print) · Zbl 1383.65051
[28] Munson, B.R., Young, D.F., Okiishi, T.H.: Fundamentals of Fluid Mechanics. Wiley, New York (2006) · Zbl 0834.76001
[29] Porcelli, M, On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds, Optim. Lett., 7, 447-465, (2013) · Zbl 1268.90091
[30] Porcelli, M., Toint, P.L.: BFO, a trainable derivative-free brute force optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables. ACM Trans. Math. Softw. 44(1), Article 6, 25 pages (2017) · Zbl 06920068
[31] Schubert, LK, Modifications of a quasi-Newton for nonlinear equations with sparse Jacobian, Math. Comput., 24, 27-30, (1970) · Zbl 0198.49402
[32] Zhao, L; Sun, W, A conic affine scaling dogleg method for nonlinear optimization with bound constraints, Asia Pac. J. Oper. Res., 30, 1340011-1-1340011-30, (2013) · Zbl 1273.90209
[33] Zhu, D, An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems, J. Comput. Appl. Math., 184, 343-361, (2005) · Zbl 1087.65047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.