Nonlinear least-squares solvers vs. generic minimization

Question

A nonlinear least-squares problem with $F:\mathbb{R}^m\to\mathbb{R}^n$, $$ F(x) \to \min_x \quad (\text{in the least-squares sense}) $$ really means minimizing $$ \frac{1}{2} \|F(x)\|^2 \to \min_x. $$ In principle, one could throw any old minimization method at it and get something. In turn, given any minimization problem $f(x)\to\min_x$, one could solve the gradient system $\nabla f(x)=0$ ($\nabla f: \mathbb{R}^m\to\mathbb{R}^m$) using least-squares methods. It almost appears that minimization and nonlinear least-squares algorithms are solving the same problem.

Still, there are specific nonlinear least-squares methods available in software: Trust-Region Reflective, Dogbox, Levenberg-Marquardt etc. How do they exploit the structure of the problem?

Answer 1

If we let

$\phi(x)=\sum_{i=1}^{m} F_{i}(x)^{2}$,

we could compute $\nabla \phi(x)$ by finite difference approximation. However, it is generally smart to make use of the special structure of $\phi(x)$ and derivatives of $F_{i}(x)$. Using the chain rule and exploiting the sum of squares structure of $\phi(x)$ we obtain that

$\nabla \phi(x)=2J(x)^{T}F(x)$

where $J(x)$ is the Jacobian of $F(x)$.

Furthermore, we can obtain the Hessian of $\phi(x)$ as

$\nabla^{2} \phi(x)=2J(x)^{T}J(x)+2\sum_{i=1}^{m} F_{i}(x)Q_{i}(x)$

where

$Q_{i}(x)=\nabla^{2}F_{i}(x)$.

These formulas for $\nabla \phi(x)$ and $\nabla^{2} \phi(x)$ can be used within whatever general purpose nonlinear optimization algorithm you want to use- you'll get a version specialized for least squares problems.

In the Gauss-Newton method, an approximation to the Hessian of $\phi(x)$,

$\nabla^{2} \phi(x) \approx 2J(x)^{T}J(x)$

is used. This approximation drops the second order terms $\sum_{i=1}^{m} F_{i}(x)Q(x)$ which tend to be small, particularly when $F_{i}(x)$ is close to 0. Only the Jacobian (first derivative) of $F(x)$ is used. This leads to a Newton's method step equation

$ J(x^{(k)})^{T}J(x^{(k)}) \Delta x = -J(x^{(k)})^{T}F(x^{(k)})$

The Levenberg-Marquadrt algorithm takes this one step further, by regularizing the Gauss-Newton methods to ensure improvement in $\phi(x)$ at each iteration.