Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Approximate norm descent methods for constrained nonlinear systems


Authors: Benedetta Morini, Margherita Porcelli and Philippe L. Toint
Journal: Math. Comp. 87 (2018), 1327-1351
MSC (2010): Primary 65H10, 90C06, 90C56
DOI: https://doi.org/10.1090/mcom/3251
Published electronically: May 11, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1007/s11075-012-9653-z
  • [2] Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141-148. MR 967848, https://doi.org/10.1093/imanum/8.1.141
  • [3] 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, https://doi.org/10.1016/S0168-9274(02)00170-8
  • [4] 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, https://doi.org/10.1080/10556788.2014.955496
  • [5] 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, https://doi.org/10.1023/A:1024013824524
  • [6] C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577-593. MR 0198670, https://doi.org/10.2307/2003941
  • [7] 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, https://doi.org/10.2307/2008615
  • [8] 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.
  • [9] 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
  • [10] 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 0343581, https://doi.org/10.2307/2005926
  • [11] 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.
  • [12] 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, https://doi.org/10.1016/j.amc.2012.09.056
  • [13] Stanley C. Eisenstat and Homer F. Walker, Globally convergent inexact Newton methods, SIAM J. Optim. 4 (1994), no. 2, 393-422. MR 1273766, https://doi.org/10.1137/0804022
  • [14] 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
  • [15] 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, https://doi.org/10.1017/S0334270000005208
  • [16] 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
  • [17] L. Grippo and M. Sciandrone, Nonmonotone derivative-free methods for nonlinear equations, Comput. Optim. Appl. 37 (2007), no. 3, 297-328. MR 2335098, https://doi.org/10.1007/s10589-007-9028-x
  • [18] 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, https://doi.org/10.1007/BF01580752
  • [19] 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, https://doi.org/10.1016/j.cam.2004.02.013
  • [20] 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, https://doi.org/10.1080/10556788.2012.721129
  • [21] 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, https://doi.org/10.1090/S0025-5718-06-01840-0
  • [22] 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, https://doi.org/10.1080/10556780310001610493
  • [23] 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, https://doi.org/10.1080/10556780008805782
  • [24] 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, https://doi.org/10.1080/10556789808805677
  • [25] 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.
  • [26] 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, https://doi.org/10.1016/j.apnum.2008.03.028
  • [27] 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, https://doi.org/10.1016/S0377-0427(00)00434-9
  • [28] 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, https://doi.org/10.1007/BF01585096
  • [29] 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, https://doi.org/10.1007/s11590-011-0430-z
  • [30] 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, https://doi.org/10.1016/j.amc.2016.01.063
  • [31] 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, https://doi.org/10.1016/j.cam.2005.01.013

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65H10, 90C06, 90C56

Retrieve articles in all journals with MSC (2010): 65H10, 90C06, 90C56


Additional Information

Benedetta Morini
Affiliation: Dipartimento di Ingegneria Industriale, Università degli Studi di Firenze, viale G.B. Morgagni 40, 50134 Firenze, Italy
Email: benedetta.morini@unifi.it

Margherita Porcelli
Affiliation: Dipartimento di Ingegneria Industriale, Università degli Studi di Firenze, viale G.B. Morgagni 40, 50134 Firenze, Italy
Email: margherita.porcelli@unifi.it

Philippe L. Toint
Affiliation: Namur Center for Complex Systems (naXys), University of Namur, 61, rue de Bruxelles, B-5000 Namur, Belgium
Email: philippe.toint@unamur.be

DOI: https://doi.org/10.1090/mcom/3251
Keywords: Nonlinear systems of equations, convex constraints, numerical algorithms, convergence theory
Received by editor(s): July 27, 2016
Received by editor(s) in revised form: December 16, 2016
Published electronically: May 11, 2017
Additional Notes: The work of the first two authors was supported by Gruppo Nazionale per il Calcolo Scientifico (GNCS-INdAM) of Italy
Part of this research was conducted during a visit supported by GNCS-INdAM of the third author to the Università degli Studi di Firenze
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society