A more direct and better variant of New Q-Newton's method Backtracking for m equations in m variables.
2021
In this paper we propose a variant of New Q-Newton's method Backtracking (which is relevant to Levenberg-Marquardt algorithm, but with the argumentation chosen by New Q-Newton's method idea for good theoretical guarantee, and with Backtracking line search added) for to use specifically with systems of m equations in m variables.
We fix $\delta _0=0 $ and $\delta _1=2$, and a number $0<\tau <1$. If $A$ is a square matrix, we denote by $minsp(A)=\min \{|\lambda |: $ $\lambda$ is an eigenvalue of $A\}$. Also, we denote by $A^{\intercal}$ the transpose of $A$.
Given $F:\mathbb{R}^m\rightarrow \mathbb{R}^m$ a $C^1$ function, we denote by $H(x)=JF(x)$ the Jacobian of $F$, and $f(x)=||F(x)||^2$. If $x\in \mathbb{R}^m$ is such that $F(x)\not= 0$, we define various :
$\delta (x)$ be the first element $\delta _j$ in $\{\delta _0,\delta _1\}$ so that $minsp(H(x)+\delta _j||F(x)||^{\tau } )\geq \min \{ ||F(x)||^{\tau},1\}$;
$A(x)=H(x)^{\intercal}H(x)+\delta (x)||F(x)||^{\tau }Id$;
$w(x)=A(x)^{-1}H(x)^{\intercal}F(x)$; (if $x$ is close to a non-degenerate zero of $F$, then $w(x)=H(x)^{-1}F(x)$ the usual Newton's direction) Note: we can normalise $w(x)/\max \{||w(x)|| ,1\}$ if needed
$\gamma (x)$ is chosen from Armijo's Backtracking line search: it is the largest number $\gamma$ among $\{1,1/2,(1/2)^2,\ldots \}$ so that: $f(x-\gamma w(x))-f(x)\leq -\gamma $;
The update rule of our method is $x\mapsto x-\gamma (x)w(x)$.
Good theoretical guarantees are proven, in particular for systems of polynomial equations. In "generic situations", we will also discuss a way to avoid that the limit of the constructed sequence is a solution of $H(x)^{\intercal}F(x)=0$ but not of $F(x)=0$.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
0
Citations
NaN
KQI