Fast line searches for the robust solution of

详细信息 p://geophysics.geoscienceworld.org/content/72/2/A13.full">在线全文 p://geophysics.geoscienceworld.org/content/72/2/A13.full.pdf">PDF全文下载

journal_title：Geophysics
Contributor：Kenneth P. Bube ; Tamas Nemeth
Publisher：Society of Exploration Geophysicists
Date：2007-
Format：text/html
Language：en
Identifier：10.1190/1.2431639
journal_abbrev：Geophysics
issn：0016-8033
volume：72
issue：2
firstpage：A13
section：GEOPHYSICS LETTERS

摘要

<p id="p-1">Linear systems of equations arise in traveltime tomography, deconvolution, and many other geophysical applications. Nonlinear problems are often solved by successive linearization, leading to a sequence of linear systems. Overdetermined linear systems are solved by minimizing some measure of the size of the misfit or residual. The most commonly used measure is the pan class="inline-formula" id="inline-formula-2"> $\text{[math]}$ pan> norm (squared), leading to least squares problems. The advantage of least squares problems for linear systems is that they can be solved by methods (for example, pan class="inline-formula" id="inline-formula-3"> $\text{[math]}$ pan> factorization) that retain the linear behavior of the problem. The disadvantage of least squares solutions is that the solution is sensitive to outliers. More robust norms, approximating the pan class="inline-formula" id="inline-formula-4"> $\text{[math]}$ pan> norm, can be used to reduce the sensitivity to outliers. Unfortunately, these more robustnorms lead to nonlinear minimization problems, even for linear systems, and many efficient algorithms for nonlinear minimization problems require line searches. One iterative method for solving linear problems in these more robust norms is iteratively reweighted least squares (IRLS). Recently, the limited-memory Broyden, Fletcher, Goldfarb, and Shanno (BFGS) algorithm (LBFGS) has been applied efficiently to these problems. A variety of nonlinear conjugate gradient algorithms (NLCG) can also be applied. LBFGS and NLCG methods require a line search in each iteration. We show that exact line searches for these methods can be performed very efficiently for computing solutions to linear systems in these robust norms, thereby promoting fast convergence of these methods. We also compare LBFGS and NLCG (with and without exact line searches) to IRLS for a small number of iterations. p>