×

zbMATH — the first resource for mathematics

Preconditioning Newton-Krylov methods in nonconvex large scale optimization. (English) Zbl 1314.90063
Summary: We consider an iterative preconditioning technique for non-convex large scale optimization. First, we refer to the solution of large scale indefinite linear systems by using a Krylov subspace method, and describe the iterative construction of a preconditioner which does not involve matrices products or matrices storage. The set of directions generated by the Krylov subspace method is used, as by product, to provide an approximate inverse preconditioner. Then, we experience our preconditioner within Truncated Newton schemes for large scale unconstrained optimization, where we generalize the truncation rule by S. G. Nash and A. Sofer [Oper. Res. Lett. 9, No. 4, 219–221 (1990; Zbl 0706.90073)] to the indefinite case, too. We use a Krylov subspace method to both approximately solve the Newton equation and to construct the preconditioner to be used at the current outer iteration. An extensive numerical experience shows that the proposed preconditioning strategy, compared with the unpreconditioned strategy and PREQN [J. L. Morales and J. Nocedal, SIAM J. Optim. 10, No. 4, 1079–1096 (2000; Zbl 1020.65019)], may lead to a reduction of the overall inner iterations. Finally, we show that our proposal has some similarities with the Limited Memory Preconditioners [S. Gratton et al., SIAM J. Optim. 21, No. 3, 912–935 (2011; Zbl 1273.65044)].

MSC:
90C26 Nonconvex programming, global optimization
90C06 Large-scale problems in mathematical programming
65K05 Numerical mathematical programming methods
Software:
PREQN; tn; CUTEr; SifDec; KELLEY
PDF BibTeX Cite
Full Text: DOI
References:
[1] Baglama, J.; Calvetti, D.; Golub, G.H.; Reichel, L., Adaptively preconditioned GMRES algorithms, SIAM J. Sci. Comput., 20, 243-269, (1998) · Zbl 0954.65026
[2] Bernstein, D.S.: Matrix Mathematics, 2nd edn. Princeton University Press, Princeton (2009) · Zbl 1183.15001
[3] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS—SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071
[4] Dembo, R.S.; Steihaug, T., Truncated-Newton algorithms for large-scale unconstrained optimization, Math. Program., 26, 190-212, (1983) · Zbl 0523.90078
[5] Dolan, E.D.; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[6] Erhel, J.; Burrage, K.; Pohl, B., Restarted GMRES preconditioned by deflation, J. Comput. Appl. Math., 69, 303-318, (1996) · Zbl 0854.65025
[7] Fasano, G., Planar-conjugate gradient algorithm for large-scale unconstrained optimization, part 1: theory, J. Optim. Theory Appl., 125, 523-541, (2005) · Zbl 1079.90162
[8] Fasano, G., Planar-conjugate gradient algorithm for large-scale unconstrained optimization, part 2: application, J. Optim. Theory Appl., 125, 543-558, (2005) · Zbl 1079.90163
[9] Fasano, G., Lanczos-conjugate gradient method and pseudoinverse computation, in unconstrained optimization, J. Optim. Theory Appl., 132, 267-285, (2006) · Zbl 1151.65023
[10] Fasano, G.; Roma, M., Iterative computation of negative curvature directions in large scale optimization, Comput. Optim. Appl., 38, 81-104, (2007) · Zbl 1171.90549
[11] Gill, P.E.; Murray, W.; Ponceleon, D.B.; Saunders, M.A., Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13, 292-311, (1992) · Zbl 0749.65037
[12] Giraud, L.; Gratton, S., On the sensitivity of some spectral preconditioners, SIAM J. Matrix Anal. Appl., 27, 1089-1105, (2006) · Zbl 1104.65040
[13] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins Press, Baltimore (1996) · Zbl 0865.65009
[14] Gould, N.I.M.; Lucidi, S.; Roma, M.; Toint, Ph.L., Exploiting negative curvature directions in linesearch methods for unconstrained optimization, Optim. Methods Softw., 14, 75-98, (2000) · Zbl 0988.90039
[15] Gould, N.I.M.; Orban, D.; Toint, Ph.L., Cuter (and sifdec), a constrained and unconstrained testing environment, revised, ACM Trans. Math. Softw., 29, 373-394, (2003) · Zbl 1068.90526
[16] Gratton, S.; Sartenaer, A.; Tshimanga, J., On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides, SIAM J. Optim., 21, 912-935, (2011) · Zbl 1273.65044
[17] Grippo, L.; Lampariello, F.; Lucidi, S., A truncated Newton method with nonmonotone linesearch for unconstrained optimization, J. Optim. Theory Appl., 60, 401-419, (1989) · Zbl 0632.90059
[18] Kelley, C.T.: Iterative Methods for Optimization. SIAM Frontiers in Applied Mathematics. SIAM, Philadelphia (1999) · Zbl 0934.90082
[19] Loghin, L.; Ruiz, D.; Touhami, A., Adaptive preconditioners for nonlinear systems of equations, J. Comput. Appl. Math., 189, 362-374, (2006) · Zbl 1088.65048
[20] Morales, J.L.; Nocedal, J., Algorithm PREQN: Fortran 77 subroutine for preconditioning the conjugate gradient method, ACM Trans. Math. Softw., 27, 83-91, (2001) · Zbl 1070.65538
[21] Morales, J.L.; Nocedal, J., Automatic preconditioning by limited memory quasi-Newton updating, SIAM J. Optim., 10, 1079-1096, (2000) · Zbl 1020.65019
[22] Nash, S.G., Preconditioning of truncated-Newton methods, SIAM J. Sci. Stat. Comput., 6, 599-616, (1985) · Zbl 0592.65038
[23] Nash, S.G., A survey of truncated-Newton methods, J. Comput. Appl. Math., 124, 45-59, (2000) · Zbl 0969.65054
[24] Nash, S.G.; Sofer, A., Assessing a search direction within a truncated-Newton method, Oper. Res. Lett., 9, 219-221, (1990) · Zbl 0706.90073
[25] Nocedal, J.; Watson, A. (ed.); Duff, I. (ed.), Large scale unconstrained optimization, 311-338, (1997), Oxford · Zbl 0881.65055
[26] Roma, M., A dynamic scaling based preconditioning for truncated Newton methods in large scale unconstrained optimization, Optim. Methods Softw., 20, 693-713, (2005) · Zbl 1127.90408
[27] Stoer, J.; Bachem, A. (ed.); Grötschel, M. (ed.); Korte, B. (ed.), Solution of large linear systems of equations by conjugate gradient type methods, 540-565, (1983), Berlin
[28] Tshimanga, J.; Gratton, S.; Weaver, A.T.; Sartenaer, A., Limited-memory preconditioners with applications to incremental four-dimensional variational data assimilation, Q. J. R. Meteorol. Soc., 134, 751-769, (2008)
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.