# Nonlinear least-squares solvers vs. generic minimization

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?

• Does $F$ map $R^{n}$ to $R^{m}$, or to $R$? If $F:R^{m} \rightarrow R^{n}$, then what do you mean by $F(x) \rightarrow \min_{x}$? – Brian Borchers Mar 29 '18 at 0:51
• As Brian Borchers wrote, there's a bit of confusion in your question: Your second minimization problem is exactly the "nonlinear least-squares problem" associated to the nonlinear equation $F(x)=0$, and the solution methods you mention are pretty much examples of "any old minimization method". I think what you're trying to ask is "are there specific minimization methods that use the specific structure of a least-squares problem" (yes) and "how do they work" (by exploiting the specific form of the derivatives). Could you edit your question to make this clearer? – Christian Clason Mar 29 '18 at 6:22
• Thanks everyone for the comments. I've edited the question accordingly. – Nico Schlömer Mar 29 '18 at 8:22

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.