4
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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}$? $\endgroup$ – Brian Borchers Mar 29 '18 at 0:51
  • 1
    $\begingroup$ 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? $\endgroup$ – Christian Clason Mar 29 '18 at 6:22
  • $\begingroup$ Thanks everyone for the comments. I've edited the question accordingly. $\endgroup$ – Nico Schlömer Mar 29 '18 at 8:22
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.