Approximate norm descent methods for constrained nonlinear systems

Morini, Benedetta; Porcelli, Margherita; Toint, Philippe L.

doi:10.1090/mcom/3251

Approximate norm descent methods for constrained nonlinear systems
HTML articles powered by AMS MathViewer

by Benedetta Morini, Margherita Porcelli and Philippe L. Toint PDF

Math. Comp. 87 (2018), 1327-1351 Request permission

Abstract:

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.

References

Masoud Ahookhosh, Keyvan Amini, and Somayeh Bahrami, Two derivative-free projection approaches for systems of large-scale nonlinear monotone equations, Numer. Algorithms 64 (2013), no. 1, 21–42. MR 3090835, DOI 10.1007/s11075-012-9653-z
Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141–148. MR 967848, DOI 10.1093/imanum/8.1.141
Stefania Bellavia, Maria Macconi, and Benedetta Morini, An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math. 44 (2003), no. 3, 257–280. MR 1954953, DOI 10.1016/S0168-9274(02)00170-8
Stefania Bellavia and Sandra Pieraccini, On affine-scaling inexact dogleg methods for bound-constrained nonlinear systems, Optim. Methods Softw. 30 (2015), no. 2, 276–300. MR 3298091, DOI 10.1080/10556788.2014.955496
Ernesto G. Birgin, Nataša Krejić, and José Mario Martínez, Globally convergent inexact quasi-Newton methods for solving nonlinear systems, Numer. Algorithms 32 (2003), no. 2-4, 249–260. MR 1989368, DOI 10.1023/A:1024013824524
C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577–593. MR 198670, DOI 10.1090/S0025-5718-1965-0198670-6
Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint, Testing a class of methods for solving minimization problems with simple bounds on the variables, Math. Comp. 50 (1988), no. 182, 399–430. MR 929544, DOI 10.1090/S0025-5718-1988-0929544-3
A. R. Curtis, M. J. D. Powell, J. K. Reid, On the estimation of sparse Jacobian matrices, J. Inst. Math. Appl. 13 (1974), 117–119.
John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
J. E. Dennis Jr. and Jorge J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549–560. MR 343581, DOI 10.1090/S0025-5718-1974-0343581-1
S.P. Dirkse, M.C. Ferris, MCPLIB: A Collection of Nonlinear Mixed Complementary Problems, Technical Report, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1994.
N. Echebest, M. L. Schuverdt, and R. P. Vignau, A derivative-free method for solving box-constrained underdetermined nonlinear systems of equations, Appl. Math. Comput. 219 (2012), no. 6, 3198–3208. MR 2992017, DOI 10.1016/j.amc.2012.09.056
Stanley C. Eisenstat and Homer F. Walker, Globally convergent inexact Newton methods, SIAM J. Optim. 4 (1994), no. 2, 393–422. MR 1273766, DOI 10.1137/0804022
Christodoulos A. Floudas, Pãnos M. Pardalos, Claire S. Adjiman, William R. Esposito, Zeynep H. Gümüş, Stephen T. Harding, John L. Klepeis, Clifford A. Meyer, and Carl A. Schweiger, Handbook of test problems in local and global optimization, Nonconvex Optimization and its Applications, vol. 33, Kluwer Academic Publishers, Dordrecht, 1999. MR 1718483, DOI 10.1007/978-1-4757-3040-1
Andreas Griewank, The “global” convergence of Broyden-like methods with a suitable line search, J. Austral. Math. Soc. Ser. B 28 (1986), no. 1, 75–92. MR 846784, DOI 10.1017/S0334270000005208
Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
L. Grippo and M. Sciandrone, Nonmonotone derivative-free methods for nonlinear equations, Comput. Optim. Appl. 37 (2007), no. 3, 297–328. MR 2335098, DOI 10.1007/s10589-007-9028-x
Patrick T. Harker, Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities, Math. Programming 41 (1988), no. 1, (Ser. A), 29–59. MR 941316, DOI 10.1007/BF01580752
Christian Kanzow, Nobuo Yamashita, and Masao Fukushima, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math. 172 (2004), no. 2, 375–397. MR 2095326, DOI 10.1016/j.cam.2004.02.013
William La Cruz, A projected derivative-free algorithm for nonlinear equations with convex constraints, Optim. Methods Softw. 29 (2014), no. 1, 24–41. MR 3175472, DOI 10.1080/10556788.2012.721129
William La Cruz, José Mario Martínez, and Marcos Raydan, Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comp. 75 (2006), no. 255, 1429–1448. MR 2219036, DOI 10.1090/S0025-5718-06-01840-0
William La Cruz and Marcos Raydan, Nonmonotone spectral methods for large-scale nonlinear systems, Optim. Methods Softw. 18 (2003), no. 5, 583–599. MR 2015399, DOI 10.1080/10556780310001610493
Dong-Hui Li and Masao Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Softw. 13 (2000), no. 3, 181–201. MR 1785195, DOI 10.1080/10556780008805782
L. Lukšan and J. Vlček, Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations, Optim. Methods Softw. 8 (1998), no. 3-4, 201–223. MR 1623249, DOI 10.1080/10556789808805677
L. Luk$\check {\mbox {s}}$an, J. Vl$\check {\mbox {c}}$ek, Test Problems for Unconstrained Optimization, Tech. Rep. V-897, ICS AS CR, November 2003.
Maria Macconi, Benedetta Morini, and Margherita Porcelli, Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities, Appl. Numer. Math. 59 (2009), no. 5, 859–876. MR 2495126, DOI 10.1016/j.apnum.2008.03.028
José Mario Martínez, Practical quasi-Newton methods for solving nonlinear systems, J. Comput. Appl. Math. 124 (2000), no. 1-2, 97–121. Numerical analysis 2000, Vol. IV, Optimization and nonlinear equations. MR 1803295, DOI 10.1016/S0377-0427(00)00434-9
Frederic H. Murphy, Hanif D. Sherali, and Allen L. Soyster, A mathematical programming approach for determining oligopolistic market equilibrium, Math. Programming 24 (1982), no. 1, 92–106. MR 667941, DOI 10.1007/BF01585096
Margherita Porcelli, On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds, Optim. Lett. 7 (2013), no. 3, 447–465. MR 3022783, DOI 10.1007/s11590-011-0430-z
Peng Wang and Detong Zhu, An inexact derivative-free Levenberg-Marquardt method for linear inequality constrained nonlinear systems under local error bound conditions, Appl. Math. Comput. 282 (2016), 32–52. MR 3472588, DOI 10.1016/j.amc.2016.01.063
Detong Zhu, An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems, J. Comput. Appl. Math. 184 (2005), no. 2, 343–361. MR 2157333, DOI 10.1016/j.cam.2005.01.013