Abstract
The minimization of linear functionals defined on the solutions of discrete ill-posed problems arises, e.g., in the computation of confidence intervals for these solutions. In 1990, Eldén proposed an algorithm for this minimization problem based on a parametric programming reformulation involving the solution of a sequence of trust-region problems, and using matrix factorizations. In this paper, we describe MLFIP, a large-scale version of this algorithm where a limited-memory trust-region solver is used on the subproblems. We illustrate the use of our algorithm in connection with an inverse heat conduction problem.
Similar content being viewed by others
References
D. Calvetti and L. Reichel, Tikhonov regularization with a solution constraint, SIAM J. Sci. Comput., 26 (2004), pp. 224–239.
A. S. Carasso, Determining surface temperatures from interior observations, SIAM J. Appl. Math., 42 (1982), pp. 558–574.
L. Eldén, The numerical solution of a non-characteristic Cauchy problem for a parabolic equation, in P. Deuflhard and E. Hairer (eds), Numerical Treatment of Inverse Problems in Differential and Integral Equations, Proceedings of an International Workshop, Heidelberg, 1982, Birkhäuser, Boston, 1983, pp. 246–268.
L. Eldén, Algorithms for the computation of functionals defined on the solution of discrete ill-posed problems, BIT, 30 (1990), pp. 466–483.
L. Eldén, F. Berntsson, and T. Reginska, Wavelet and Fourier methods for solving the sideways heat equation, SIAM J. Sci. Comput., 21 (2001), pp. 2187–2205.
G. H. Golub and U. von Matt, Quadratically constrained least squares and quadratic problems, Numer. Math., 59 (1991), pp. 561–580.
N. Gould, S. Lucidi, M. Roma, and Ph. L. Toint, Solving the trust–region subproblem using the Lanczos method, SIAM J. Optim., 9 (1999), pp. 504–525.
W. W. Hager, Minimizing a quadratic over a sphere, SIAM J. Optim., 12 (2001), pp. 188–208.
P. C. Hansen, Regularization Tools: A Matlab package for analysis and solution of discrete ill-posed problems, Numer. Algo., 6 (1994), pp. 1–35.
P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion, SIAM, Philadelphia, 1998.
R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK User’s Guide: Solution of Large Scale Eigenvalue Problems by Implicitly Restarted Arnoldi Methods, SIAM, Philadelphia, 1998.
D. P. O’Leary and B. W. Rust, Confidence intervals for inequality-constrained least squares problems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 473–489.
P. Paateri, Extreme value estimation, a method for regularizing ill-posed inversion problems, in A. N. Tikhonov (ed.), Ill-Posed Problems in Natural Sciences, VSP, Utrecht, 1992, pp. 118–133.
F. Rendl and H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Prog., 77 (1997), pp. 273–299.
M. Rojas, S. A. Santos, and D. C. Sorensen, A new matrix-free algorithm for the largescale trust-region subproblem, SIAM J. Optim., 11 (2000), pp. 611–646.
M. Rojas, S. A. Santos, and D. C. Sorensen, LSTRS: Matlab software for largescale trust-region subproblems and regularization, Technical Report 2003-4, Department of Mathematics, Wake Forest University, October 2003, revised October 2004. http://web.math.wfu.edu/∼mrojas/software.html
M. Rojas and D. C. Sorensen, A trust-region approach to the regularization of large-scale discrete forms of ill-posed problems, SIAM J. Sci. Comp., 26 (2002), pp. 1843–1861.
D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357–385.
T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20 (1983), pp. 626–637.
Author information
Authors and Affiliations
Corresponding authors
Additional information
AMS subject classification (2000)
65F22
Rights and permissions
About this article
Cite this article
Eldén, L., Hansen, P. & Rojas, M. Minimization of Linear Functionals Defined on Solutions of Large-Scale Discrete Ill-Posed Problems. Bit Numer Math 45, 329–340 (2005). https://doi.org/10.1007/s10543-005-7122-y
Issue Date:
DOI: https://doi.org/10.1007/s10543-005-7122-y