zbMATH — the first resource for mathematics

Approximate norm descent methods for constrained nonlinear systems. (English) Zbl 1383.65051
Summary: We address the solution of convex-constrained nonlinear systems of equations where the Jacobian matrix is unavailable or its computation/storage is burdensome. In order to efficiently solve such problems, we propose a new class of algorithms which are “derivative-free” both in the computation of the search direction and in the selection of the steplength. Search directions comprise the residuals and quasi-Newton directions while the steplength is determined by using a new linesearch strategy based on a nonmonotone approximate norm descent property of the merit function. We provide a theoretical analysis of the proposed algorithm and we discuss several conditions ensuring convergence to a solution of the constrained nonlinear system. Finally, we illustrate its numerical behaviour also in comparison with existing approaches.

65H10 Numerical computation of solutions to systems of equations
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C53 Methods of quasi-Newton type
90C56 Derivative-free methods and methods using generalized derivatives
levmar; STRSCNE
Full Text: DOI
[1] Ahookhosh, Masoud; Amini, Keyvan; Bahrami, Somayeh, Two derivative-free projection approaches for systems of large-scale nonlinear monotone equations, Numer. Algorithms, 64, 1, 21-42, (2013) · Zbl 1290.65046
[2] Barzilai, Jonathan; Borwein, Jonathan M., Two-point step size gradient methods, IMA J. Numer. Anal., 8, 1, 141-148, (1988) · Zbl 0638.65055
[3] Bellavia, Stefania; Macconi, Maria; Morini, Benedetta, An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math., 44, 3, 257-280, (2003) · Zbl 1018.65067
[4] Bellavia, Stefania; Pieraccini, Sandra, On affine-scaling inexact dogleg methods for bound-constrained nonlinear systems, Optim. Methods Softw., 30, 2, 276-300, (2015) · Zbl 1325.90100
[5] Birgin, Ernesto G.; Kreji\'c, Nata\v sa; Mart\'\i nez, Jos\'e Mario, Globally convergent inexact quasi-Newton methods for solving nonlinear systems, Numer. Algorithms, 32, 2-4, 249-260, (2003) · Zbl 1034.65032
[6] Broyden, C. G., A class of methods for solving nonlinear simultaneous equations, Math. Comp., 19, 577-593, (1965) · Zbl 0131.13905
[7] Conn, Andrew R.; Gould, Nicholas I. M.; Toint, Philippe L., Testing a class of methods for solving minimization problems with simple bounds on the variables, Math. Comp., 50, 182, 399-430, (1988) · Zbl 0645.65033
[8] cpr A. R. Curtis, M. J. D. Powell, J. K. Reid, \em On the estimation of sparse Jacobian matrices, J. Inst. Math. Appl. <span class=”textbf”>1</span>3 (1974), 117–119. · Zbl 0273.65036
[9] Dennis, John E., Jr.; Schnabel, Robert B., Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, xiii+378 pp., (1983), Prentice Hall, Inc., Englewood Cliffs, NJ
[10] Dennis, J. E., Jr.; Mor\'e, Jorge J., A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28, 549-560, (1974) · Zbl 0282.65042
[11] mcplib S.P. Dirkse, M.C. Ferris, \em MCPLIB: A Collection of Nonlinear Mixed Complementary Problems, Technical Report, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1994.
[12] Echebest, N.; Schuverdt, M. L.; Vignau, R. P., A derivative-free method for solving box-constrained underdetermined nonlinear systems of equations, Appl. Math. Comput., 219, 6, 3198-3208, (2012) · Zbl 1309.65055
[13] Eisenstat, Stanley C.; Walker, Homer F., Globally convergent inexact Newton methods, SIAM J. Optim., 4, 2, 393-422, (1994) · Zbl 0814.65049
[14] Floudas, Christodoulos A.; Pardalos, P\~anos M.; Adjiman, Claire S.; Esposito, William R.; G\`‘um\'’u\c s, Zeynep H.; Harding, Stephen T.; Klepeis, John L.; Meyer, Clifford A.; Schweiger, Carl A., Handbook of Test Problems in Local and Global Optimization, Nonconvex Optimization and its Applications 33, xvi+441 pp., (1999), Kluwer Academic Publishers, Dordrecht · Zbl 0943.90001
[15] Griewank, Andreas, The “global” convergence of Broyden-like methods with a suitable line search, J. Austral. Math. Soc. Ser. B, 28, 1, 75-92, (1986) · Zbl 0596.65034
[16] Golub, Gene H.; Van Loan, Charles F., Matrix computations, Johns Hopkins Series in the Mathematical Sciences 3, xvi+476 pp., (1983), Johns Hopkins University Press, Baltimore, MD · Zbl 0559.65011
[17] Grippo, L.; Sciandrone, M., Nonmonotone derivative-free methods for nonlinear equations, Comput. Optim. Appl., 37, 3, 297-328, (2007) · Zbl 1180.90310
[18] Harker, Patrick T., Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities, Math. Programming, 41, 1, (Ser. A), 29-59, (1988) · Zbl 0825.49019
[19] Kanzow, Christian; Yamashita, Nobuo; Fukushima, Masao, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 172, 2, 375-397, (2004) · Zbl 1064.65037
[20] La Cruz, William, A projected derivative-free algorithm for nonlinear equations with convex constraints, Optim. Methods Softw., 29, 1, 24-41, (2014) · Zbl 1285.65028
[21] La Cruz, William; Mart\'\i nez, Jos\'e Mario; Raydan, Marcos, Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comp., 75, 255, 1429-1448, (2006) · Zbl 1122.65049
[22] La Cruz, William; Raydan, Marcos, Nonmonotone spectral methods for large-scale nonlinear systems, Optim. Methods Softw., 18, 5, 583-599, (2003) · Zbl 1069.65056
[23] Li, Dong-Hui; Fukushima, Masao, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Softw., 13, 3, 181-201, (2000) · Zbl 0960.65076
[24] Luk\v san, L.; Vl\v cek, J., Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations, Optim. Methods Softw., 8, 3-4, 201-223, (1998) · Zbl 0927.65068
[25] lv_test L. Luk\(\check \mbox s\)an, J. Vl\(\check \mbox c\)ek, \em Test Problems for Unconstrained Optimization, Tech. Rep. V-897, ICS AS CR, November 2003.
[26] Macconi, Maria; Morini, Benedetta; Porcelli, Margherita, Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities, Appl. Numer. Math., 59, 5, 859-876, (2009) · Zbl 1165.65030
[27] Mart\'\i nez, Jos\'e Mario, Practical quasi-Newton methods for solving nonlinear systems, J. Comput. Appl. Math., 124, 1-2, 97-121, (2000) · Zbl 0967.65065
[28] Murphy, Frederic H.; Sherali, Hanif D.; Soyster, Allen L., A mathematical programming approach for determining oligopolistic market equilibrium, Math. Programming, 24, 1, 92-106, (1982) · Zbl 0486.90015
[29] Porcelli, Margherita, On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds, Optim. Lett., 7, 3, 447-465, (2013) · Zbl 1268.90091
[30] Wang, Peng; Zhu, Detong, An inexact derivative-free Levenberg-Marquardt method for linear inequality constrained nonlinear systems under local error bound conditions, Appl. Math. Comput., 282, 32-52, (2016) · Zbl 1410.49037
[31] Zhu, Detong, An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems, J. Comput. Appl. Math., 184, 2, 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.