×

Preconditioning and globalizing conjugate gradients in dual space for quadratically penalized nonlinear-least squares problems. (English) Zbl 1267.90093

Summary: When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each iteration of the method is rewritten as a quadratic minimization subject to linear equality constraints. This allows the exploitation of duality properties of the associated linearized problems. This paper considers a recent conjugate-gradient-like method which performs the quadratic minimization in the dual space and produces, in exact arithmetic, the same iterates as those produced by a standard conjugate-gradient method in the primal space. This dual algorithm is computationally interesting whenever the dimension of the dual space is significantly smaller than that of the primal space, yielding gains in terms of both memory usage and computational cost. The relation between this dual space solver and PSAS (Physical-space Statistical Analysis System), another well-known dual space technique used in data assimilation problems, is explained. The use of an effective preconditioning technique is proposed and refined convergence bounds derived, which results in a practical solution method. Finally, stopping rules adequate for a trust-region solver are proposed in the dual space, providing iterates that are equivalent to those obtained with a Steihaug-Toint truncated conjugate-gradient method in the primal space.

MSC:

90C20 Quadratic programming
90C52 Methods of reduced gradient type

Software:

KELLEY; LSTRS; TAMC; TAF
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akkraoui, A.E., Gauthier, P., Pellerin, S., Buis, S.: Intercomparison of the primal and dual formulations of variational data assimilation. Q. J. R. Meteorol. Soc. 134, 1015–1025 (2008) · doi:10.1002/qj.257
[2] Arioli, M.: A stopping criterion for the conjugate gradient algorithm in a finite element framework. Numer. Math. 97, 1–24 (2004) · Zbl 1048.65029 · doi:10.1007/s00211-003-0500-y
[3] Ashby, S.F., Holst, M.J., Manteuffel, T.A., Saylor, P.E.: The role of the inner product in stopping criteria for conjugate gradient iterations. BIT 41(1), 026–052 (2001) · Zbl 0984.65025 · doi:10.1023/A:1021961616621
[4] Axelsson, O.: Iterative Solution Methods. Cambridge University Press, Cambridge (1996) · Zbl 0845.65011
[5] Björck, Å.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996) · Zbl 0847.65023
[6] Bouttier, F., Courtier, P.: Data assimilation concepts and methods. Technical report, ECMWF, Reading, England, 1999
[7] Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic overestimation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results. Math. Program., Ser. A (2009). doi: 10.1007/s10107-009-0286-5 , 51 pp. · Zbl 1229.90192
[8] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS-SIAM Series on Optimization, vol. 01. SIAM, Philadelphia (2000) · Zbl 0958.65071
[9] Courtier, P.: Dual formulation of four-dimensional variational assimilation. Q. J. R. Meteorol. Soc. 123, 2449–2461 (1997) · doi:10.1002/qj.49712354414
[10] Courtier, P., Thépaut, J.-N., Hollingsworth, A.: A strategy for operational implementation of 4D-Var using an incremental approach. Q. J. R. Meteorol. Soc. 120, 1367–1388 (1994) · doi:10.1002/qj.49712051912
[11] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs (1983). Reprinted as Classics in Applied Mathematics, vol. 16. SIAM, Philadelphia (1996) · Zbl 0579.65058
[12] Fisher, M., Nocedal, J., Tremolet, Y., Wright, S.J.: Data assimilation in weather forecasting: a case study in PDE-constrained optimization. Optim. Eng. 10, 409–426 (2009) · Zbl 1400.90325 · doi:10.1007/s11081-008-9051-5
[13] Giering, R., Kaminski, T.: Recipes for adjoint code construction. ACM Trans. Math. Softw. 24(4), 437–474 (1998) · Zbl 0934.65027 · doi:10.1145/293686.293695
[14] Golub, G.H., Van Loan, C.F.: Matrix Computations, 2nd edn. Johns Hopkins University Press, Baltimore (1989) · Zbl 0733.65016
[15] Gratton, S., Tshimanga, J.: An observation-space formulation of variational assimilation using a restricted preconditioned conjugate-gradient algorithm. Q. J. R. Meteorol. Soc. 135, 1573–1585 (2009) · doi:10.1002/qj.477
[16] Gratton, S., Lawless, A., Nichols, N.K.: Approximate Gauss-Newton methods for nonlinear least-squares problems. SIAM J. Optim. 18, 106–132 (2007) · Zbl 1138.65046 · doi:10.1137/050624935
[17] Kelley, C.T.: Iterative Methods for Optimization. Frontiers in Applied Mathematics. SIAM, Philadelphia (1999) · Zbl 0934.90082
[18] Lampe, J., Rojas, M., Sorensen, D.C., Voss, H.: Accelerating the LSTRS algorithm. SIAM J. Sci. Comput. 33(1), 175–194 (2011) · Zbl 1368.65096 · doi:10.1137/090764426
[19] Morales, J.L., Nocedal, J.: Automatic preconditioning by limited-memory quasi-Newton updating. SIAM J. Optim. 10, 1079–1096 (2000) · Zbl 1020.65019 · doi:10.1137/S1052623497327854
[20] Nocedal, J., Wright, S.J.: Numerical Optimization. Series in Operations Research. Springer, Heidelberg (1999) · Zbl 0930.65067
[21] Rojas, M., Santos, S.A., Sorensen, D.C.: Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization. ACM Trans. Math. Softw. 34(2), 11 (2008) · Zbl 1291.65177
[22] Roux, F.X.: Acceleration of the outer conjugate gradient by reorthogonalization for a domain decomposition method for structural analysis problems. In: Proceedings of the 3rd International Conference on Supercomputing’, ICS’89, pp. 471–476. ACM, New York (1989)
[23] Stoll, M., Wathen, A.: Combination preconditioning and the Bramble-Pasciak+ preconditioner. SIAM J. Matrix Anal. Appl. 30(2), 582–608 (2008) · Zbl 1167.65358 · doi:10.1137/070688961
[24] Tarantola, A.: Inverse Problem Theory. Methods for Data Fitting and Model Parameter Estimation. Elsevier, Amsterdam (1987) · Zbl 0875.65001
[25] Tschimanga, Jean: On a class of limited memory preconditioners for large-scale nonlinear least-squares problems (with application to variational ocean data assimilation). PhD thesis, Department of Mathematics, FUNDP, University of Namur, Namur, Belgium (2007)
[26] Tshimanga, J., Gratton, S., Weaver, A., Sartenaer, A.: Limited-memory preconditioners with application to incremental four-dimensional variational data assimilation. Q. J. R. Meteorol. Soc. 134, 751–769 (2008) · doi:10.1002/qj.228
[27] van der Vorst, H.A.: Iterative Krylov Methods for Large Linear Systems. Cambridge University Press, Cambridge (2003) · Zbl 1023.65027
[28] Weaver, A.T., Vialard, J., Anderson, D.L.T.: Three- and four-dimensional variational assimilation with a general circulation model of the tropical Pacific ocean, Part 1: Formulation, internal diagnostics and consistency checks. Mon. Weather Rev. 131, 1360–1378 (2003) · doi:10.1175/1520-0493(2003)131<1360:TAFVAW>2.0.CO;2
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.