Regularized nonlinear Levenberg–Marquardt

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. For a subset $V\subseteq U$ and a constant $c>0$, the product-type tangential cone condition on $V$ with constant $c$ is the requirement that, for every $x,\tilde{x}\in V$,

$\mathrm{\parallel }F(x)-F(\tilde{x})-F^{\mathrm{\prime }}(x)(x-\tilde{x}){\mathrm{\parallel }}_Y\le c\mathrm{\parallel }x-\tilde{x}{\mathrm{\parallel }}_X\mathrm{\parallel }F(x)-F(\tilde{x}){\mathrm{\parallel }}_Y\mathrm{.}$

Nonlinear forward map between real Hilbert spaces

Fréchet derivative on an open real Banach domain

One-basepoint local tangential cone condition

Christian Clason, Regularization of Inverse Problems, Assumption 11.10 and equation (11.23)

This is an explicit two-point product-remainder hypothesis. The LM stopping proof below assumes this inequality directly; it does not derive it from differentiability or from the one-basepoint local tangential cone condition.

Let $X,Y$ be real Hilbert spaces, let $U\subseteq X$ be open, and let $F:U\to Y$ be Fréchet differentiable at every point of $U$ with $x\mapsto F^{\mathrm{\prime }}(x)$ continuous in operator norm. Let $V\subseteq U$ and let $c>0$ be such that, for every $u,\tilde{u}\in V$, $\mathrm{\parallel }F(u)-F(\tilde{u})-F^{\mathrm{\prime }}(u)(u-\tilde{u}){\mathrm{\parallel }}_Y\le c\mathrm{\parallel }u-\tilde{u}{\mathrm{\parallel }}_X\mathrm{\parallel }F(u)-F(\tilde{u}){\mathrm{\parallel }}_Y\mathrm{.}$ Suppose $x^{†},x\in V$, $F(x^{†})=y$, $\mathrm{\parallel }{y}^{\delta }-y{\mathrm{\parallel }}_Y\le \delta$ with $\delta \ge 0$, $\tau >0$, and $\mathrm{\parallel }x-x^{†}{\mathrm{\parallel }}_X\le e$. If $R:=\mathrm{\parallel }F(x)-y^{\delta }{\mathrm{\parallel }}_Y>\tau \delta$, then

$\mathrm{\parallel }{F}^{\mathrm{\prime }}(x)(x^{†}-x)+F(x)-y^{\delta }{\mathrm{\parallel }}_Y\le \frac{1+ce(1+\tau )}{\tau }R\mathrm{.}$

In particular, if $\sigma \in (0,1)$, $e\le e_0$, and $\gamma :=\frac{\sigma \tau }{1+c{e}_0(1+\tau )}>1,$ then $\mathrm{\parallel }{F}^{\mathrm{\prime }}(x)(x^{†}-x)+F(x)-y^{\delta }{\mathrm{\parallel }}_Y\le \frac{\sigma }{\gamma }R\mathrm{.}$

Product-type tangential cone condition

Nonlinear forward map and exact-data convention

Real Hilbert spaces and their induced norms

Fréchet differentiability and operator-norm derivative

Christian Clason, Regularization of Inverse Problems, Assumption 11.10 and proof of Theorem 11.11

No choice principle is used: the proof applies the product condition to the two fixed points in the hypotheses and then uses norm inequalities.

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.

Assume Countable Choice. Let $X,Y$ be real Hilbert spaces, let $T:X\to Y$ be a bounded linear operator, let $r\in Y$ be nonzero, and let $\sigma \in (0,1)$ and $\gamma >1$. Suppose that a fixed $v\in X$ satisfies $\mathrm{\parallel }Tv-r{\mathrm{\parallel }}_Y\le \frac{\sigma }{\gamma }\mathrm{\parallel }r{\mathrm{\parallel }}_Y\mathrm{.}$ For each $\alpha >0$, the functional ${\mathrm{\Phi }}_{\alpha }(h):=\frac{1}{2}\mathrm{\parallel }Th-r{\mathrm{\parallel }}_Y^2+\frac{\alpha }{2}\mathrm{\parallel }h{\mathrm{\parallel }}_X^2(h\in X)$ has the unique global minimizer $h_{\alpha }=(T^{\ast }T+\alpha I_X{)}^{-1}{T}^{\ast }r,$ where $T^{\ast }$ is the Hilbert adjoint and $I_X$ is the identity on $X$. Moreover, there exists at least one $\alpha >0$ for which $\mathrm{\parallel }T{h}_{\alpha }-r{\mathrm{\parallel }}_Y=\sigma \mathrm{\parallel }r{\mathrm{\parallel }}_Y\mathrm{.}$

The regularized linearized LM subproblem and forcing rule

Local range-approximation bound

Real Hilbert spaces

Bounded linear operators

Operator norm

Real inner-product identities

Triangle inequality for the Hilbert norm

Hilbert adjoint under Countable Choice

Real Hilbert spaces

Axiom of Countable Choice

Shifted normal operator is invertible

Intermediate value theorem

Christian Clason, Regularization of Inverse Problems, Theorem 11.8 and its proof

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

The proof uses Countable Choice through the stated Hilbert-adjoint and normal-operator interfaces; it does not use full AC, DC, or HB. The scalar bisection or root-finding cost of a numerical parameter selector is not covered by this existence lemma.

Assume Countable Choice. Let $X,Y$ be real Hilbert spaces, let $T:X\to Y$ be bounded linear with Hilbert adjoint $T^{\ast }$, and let $e\in X$ and $r\in Y\setminus \{0\}$. Suppose $0<\sigma <1$, $\gamma >1$, $\alpha >0$, and $h$ is the unique minimizer of $h⟼\frac{1}{2}\mathrm{\parallel }Th-r{\mathrm{\parallel }}_Y^2+\frac{\alpha }{2}\mathrm{\parallel }h{\mathrm{\parallel }}_X^2\mathrm{.}$ Assume its residual forcing and the range-approximation condition are $\mathrm{\parallel }Th-r{\mathrm{\parallel }}_Y=\sigma \mathrm{\parallel }r{\mathrm{\parallel }}_Y,$ $\mathrm{\parallel }Te+r{\mathrm{\parallel }}_Y\le \frac{\sigma }{\gamma }\mathrm{\parallel }r{\mathrm{\parallel }}_Y\mathrm{.}$ Then $\mathrm{\parallel }e{\mathrm{\parallel }}_X^2-\mathrm{\parallel }e+h{\mathrm{\parallel }}_X^2\ge \mathrm{\parallel }h{\mathrm{\parallel }}_X^2+\frac{2(\gamma -1){\sigma }^2}{\gamma \alpha }\mathrm{\parallel }r{\mathrm{\parallel }}_Y^2\mathrm{.}$ If also $\mathrm{\parallel }T\mathrm{\parallel }\le M$ for some $M>0$, then $\alpha \le \frac{\sigma M^2}{1-\sigma }\mathrm{.}$

Regularized LM step and forcing rule

Range-approximation condition

Unique linearized minimizer and forcing parameter

Axiom of Countable Choice

Hilbert adjoint

Real Hilbert inner-product convention

Adjoint norm and product identities

Triangle inequality for the Hilbert norm

Christian Clason, Regularization of Inverse Problems, Lemma 11.9 and proof of Theorem 11.11

Apply the lemma in the iteration with $T=F^{\mathrm{\prime }}(x)$, $e=x-x^{†}$, and $r=y^{\delta }-F(x)$. By [F1], the algorithm's exact increment is the required minimizer. Then $Te+r$ is the negative of the linearized residual at $x^{†}$, so their norms agree. The proof uses Countable Choice through the Hilbert-adjoint and normal-operator interfaces; it does not use full AC, DC, or HB. The first estimate is conditional on the exact residual-forcing step and the stated range-approximation inequality. It is not a claim about arbitrary inexact solutions of the normal equation.

Assume Countable Choice. Let $X,Y$ be real Hilbert spaces, let $U\subseteq X$ be open, and let $F:U\to Y$ be Fréchet differentiable everywhere with $x\mapsto F^{\mathrm{\prime }}(x)$ continuous in operator norm. For $s>0$, write $B_s(x_0):=\{x\in X:\mathrm{\parallel }x-x_0{\mathrm{\parallel }}_X<s\}\mathrm{.}$ Suppose $B_{2r}(x_0)\subseteq U$ for some $r>0$, $x^{†}\in B_r(x_0)$, and $F(x^{†})=y$. Assume there are constants $M,c>0$ such that, for every $x,\tilde{x}\in B_{2r}(x_0)$, $\mathrm{\parallel }{F}^{\mathrm{\prime }}(x)\mathrm{\parallel }\le M,$ $\mathrm{\parallel }F(x)-F(\tilde{x})-F^{\mathrm{\prime }}(x)(x-\tilde{x}){\mathrm{\parallel }}_Y\le c\mathrm{\parallel }x-\tilde{x}{\mathrm{\parallel }}_X\mathrm{\parallel }F(x)-F(\tilde{x}){\mathrm{\parallel }}_Y\mathrm{.}$ Fix $\sigma \in (0,1)$ and $\tau >1\mathrm{/}\sigma$. Put $e_0:=\mathrm{\parallel }{x}_0-x^{†}{\mathrm{\parallel }}_X$ and assume $e_0<\min \{r,\frac{\sigma \tau -1}{c(1+\tau )},\frac{1-\sigma }{2c}\}\mathrm{.}$ Set $\gamma :=\frac{\sigma \tau }{1+c{e}_0(1+\tau )};$ the hypotheses give $\gamma >1$. For each exact iteration, use this $\gamma$ in the range-approximation margin of the regularized LM procedure and select any positive parameter satisfying its residual-forcing equality. For every $\delta >0$ and $y^{\delta }\in Y$ satisfying $\mathrm{\parallel }{y}^{\delta }-y{\mathrm{\parallel }}_Y\le \delta$, start at $x_0^{\delta }=x_0$ and, at each state before stopping, let $h_n$ minimize $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 }_n}{2}\mathrm{\parallel }h{\mathrm{\parallel }}_X^2$ for a selected ${\alpha }_n>0$ satisfying $\mathrm{\parallel }{F}^{\mathrm{\prime }}(x_n^{\delta })h_n+F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y=\sigma \mathrm{\parallel }F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y,$ and set $x_{n+1}^{\delta }=x_n^{\delta }+h_n$. Let $N_{\delta }$ be the first $n\in {\mathbb{N}}_0:=\{0,1,2,\dots \}$ such that $\mathrm{\parallel }F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y\le \tau \delta \mathrm{.}$ Then this exact iteration is well-defined up to a finite first discrepancy index $N_{\delta }$. Set $q:=\frac{\sigma +c{e}_0}{1-c{e}_0},K:=1+\mathrm{\parallel }F(x_0)-y{\mathrm{\parallel }}_Y,{\delta }_0:=\min \{1,\frac{K}{\tau }\}\mathrm{.}$ Here $q\in (0,1)$ and $\log$ denotes the natural logarithm. For $0<\delta \le {\delta }_0$, $N_{\delta }\le 1+\frac{\log (K\mathrm{/}(\tau \delta ))}{-\log q}\mathrm{.}$ Consequently $N_{\delta }=O(1+\mathrm{\mid }\log \delta \mathrm{\mid })$ as $\delta \downarrow 0$, with constants depending only on the fixed problem and displayed parameters. A finite run with update budget at least $N_{\delta }$ and successful exact calls returns this first crossing; a shorter budget may return budget-exhausted. No convergence rate for $x_{N_{\delta }}^{\delta }$ is asserted.

Exact residual-forcing regularized LM iteration and finite statuses

Nonlinear forward map and exact-solution convention

Real Hilbert spaces

Fréchet derivative and derivative operator norm

Operator norm

Product-type tangential cone condition

Range approximation from the product condition

Fejér decrease and upper bound for the regularization parameter

Axiom of Countable Choice

Triangle inequality for the real Hilbert norm

Natural logarithm

Order and quotient laws for the logarithm

Natural numbers are unbounded in the real field

Christian Clason, Regularization of Inverse Problems, Assumption 11.10 and Theorem 11.11 with complete proof

The source's logarithmic count uses the product-type remainder condition and a sufficiently small start. Positive noise is essential for finite discrepancy stopping; the B-page zero-noise counterexample verifies this boundary. This theorem proves an index bound only, not convergence of the stopped solution or an error rate.