Regularized nonlinear Levenberg–Marquardt with discrepancy stopping

Assume Countable Choice. Let $X,Y$ be real Hilbert spaces, let $U\subseteq X$ be open, and let $F:U\to Y$ be continuously Fréchet differentiable, meaning that $F$ is Fréchet differentiable at each point of $U$ and $x\mapsto F^{\mathrm{\prime }}(x)$ is continuous in operator norm. The input consists of an initial point $x_0\in U$, a datum $y^{\delta }\in Y$, a positive noise bound $\delta >0$, a discrepancy factor $\tau >1$, a forcing fraction $\sigma \in (0,1)$, a range-approximation margin $\gamma >1$, and a finite update budget $N_{\max }\in {\mathbb{N}}_0:=\{0,1,2,\dots \}$. Assume an exact solution $x^{†}\in U$ exists with $F(x^{†})=y$ and $\mathrm{\parallel }{y}^{\delta }-y{\mathrm{\parallel }}_Y\le \delta$. At every state $x_n^{\delta }$ before the discrepancy stop, the admissible local range condition is $\mathrm{\parallel }{F}^{\mathrm{\prime }}(x_n^{\delta })(x^{†}-x_n^{\delta })+F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y\le \frac{\sigma }{\gamma }\mathrm{\parallel }F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y\mathrm{.}$

For $x_n^{\delta }\in U$ and $\alpha >0$, define $h_{n,\alpha }$ to be the unique global minimizer over $h\in X$ of the regularized linearized least-squares objective $J_{n,\alpha }(h):=\frac{1}{2}\mathrm{\parallel }{F}^{\mathrm{\prime }}(x_n^{\delta })h+F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y^2+\frac{\alpha }{2}\mathrm{\parallel }h{\mathrm{\parallel }}_X^2\mathrm{.}$ Equivalently, it is the unique solution of $(F^{\mathrm{\prime }}(x_n^{\delta }{)}^{\ast }{F}^{\mathrm{\prime }}(x_n^{\delta })+\alpha I_X)h_{n,\alpha }=F^{\mathrm{\prime }}(x_n^{\delta }{)}^{\ast }(y^{\delta }-F(x_n^{\delta }))\mathrm{.}$ Here $I_X$ is the identity operator on $X$. The forcing rule selects any ${\alpha }_n>0$ for which $\mathrm{\parallel }{F}^{\mathrm{\prime }}(x_n^{\delta })h_{n,{\alpha }_n}+F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y=\sigma \mathrm{\parallel }F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y,$ and sets $x_{n+1}^{\delta }=x_n^{\delta }+h_{n,{\alpha }_n}$. The displayed range condition is a sufficient condition for the forcing rule to have such a parameter; it is not an input to either linearized minimization problem.

For a finite run, inspect $n=0,1,\dots ,N_{\max }$ in order. If $x_n^{\delta }\mathrm{\notin }U$, return $(x_n^{\delta },n,\mathtt{\text{domain-failure}})$. If $\mathrm{\parallel }F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y\le \tau \delta$, return $(x_n^{\delta },n,\mathtt{\text{discrepancy}})$. If $n=N_{\max }$, return $(x_n^{\delta },n,\mathtt{\text{budget-exhausted}})$. Otherwise request the exact regularized minimizer and a positive parameter satisfying the forcing rule. If the exact minimizer cannot be certified, return $(x_n^{\delta },n,\mathtt{\text{solve-unverified}})$; if the parameter selector cannot return a positive parameter satisfying the displayed equality, return $(x_n^{\delta },n,\mathtt{\text{forcing-unavailable}})$. After both exact calls succeed, set $x_{n+1}^{\delta }=x_n^{\delta }+h_{n,{\alpha }_n}$ and continue. Each return is a triple of state, index, and status. No convergence claim is attached to the failure statuses or to a budget-exhausted state.

Nonlinear forward maps between real Hilbert spaces

Fréchet differentiability on an open real Banach domain

Product-type tangential cone condition

Axiom of Countable Choice

Hilbert-space adjoint under Countable Choice

Invertibility of the shifted normal operator

Christian Clason, Regularization of Inverse Problems, §11.2, equations (11.14)–(11.16)

Barbara Kaltenbacher, Inverse Problems – Applications and Solution Strategies, PDF p. 63

The iteration is unanchored: its increment minimizes the linearized residual plus a positive penalty on the increment. It has no ${\alpha }_n(x_0-x_n^{\delta })$ term, and the anchored IRGNM theorem is not used for it. The theorem on this page uses exact regularized minimizers and exact residual-forcing parameters; it gives no guarantee for arbitrary inexact linear solves.