4
$\begingroup$

Notation for Gauss-Newton method

Non-linear least squares problems are often solved by the Levenberg-Marquardt algorithm, which can be viewed as a Gauss–Newton method using a trust region approach.

In a non-linear least squares problem, we want to find the minimum of a function $F(x)$ that is a sum of squares of nonlinear functions $$F(x)=\sum_{i=1}^m[f_i(x)]^2$$ The Gauss-Newton method computes a sequence of approximate solutions $x_k$ by linearizing the functions $f_i$ around $x_k$ and determine $x_{k+1}$ as the solution of the corresponding linear least squares problem. However, convergence is not guaranteed, for general non-linear functions $f_i$.

Context

I recently tried to answer a question for which it is possible to formulate the problem in such a way that the non-linear functions are of the form $f_i(x)=\max(0,y_i-b_i^{T}x)$. It's clear to me that this can be reformulated as a convex quadratic programming problem, and hence can be solved exactly by a quadratic programing solver. However, I asked myself whether the much simpler Gauss-Newton method wouldn't also be able to solve this problem with a "finite number of iterations". I tried to find a counter example, but didn't succeed so far.

Question

Is it possible to prove that the Gauss-Newton method finds the solution after a "finite number of iterations" when the non-linear functions are of the form $f_i(x)=\max(0,y_i-b_i^{T}x)$ in case there is a unique solution? (I assume here that degenerate linear least squares problems are handled appropriately, for example by using a singular value decomposition). Is it even possible to give an explicit bound for the number of iterations?

EDIT / Update (I decided to add a bounty. Explaining my current status hopefully increases the chances of getting answers that bring me nearer to a solution.)

Considering the counter example from the comment, it's a good idea to use $$F_k(x)=\sum_{i \;:\; y_i-b_i^{T}x_k \geq 0}[y_i-b_i^{T}x]^2$$ as the linear least squares problem to be solved in the $k$-th iteration. (Because we will probably use an existing Levenberg-Marquardt implementation instead of the Gauss-Newton method in practice, having a uniquely defined linearization independent of the optimization "history" is extremely desirable).

My current idea how to "prove" that the algorithm "finds" the unique solution (assuming an unique solution exists) goes as follows: Let $x_*$ be the unique solution and define $$F_*(x)=\sum_{i \;:\; y_i-b_i^{T}x_* \geq 0}[y_i-b_i^{T}x]^2$$ For $x_k=x_*$ we have $x_{k+1}=x_*$. My current hope is that for $k>1$ and $x_k\neq x_*$ we have $F_*(x_{k+1}) < F_*(x_k)$. If this is really true, it's hopefully possible to prove it. If it's not true, it's hopefully possible to find an explicit counter example.

$\endgroup$
  • $\begingroup$ I found a counter example, in case $0$ is used as linearization around $x_k$ for any $f_i$ with $f_i(x_k)=0$: For $m=2$, $f_1(x)=\max(0,1+x)$, $f_2(x)=\max(0,1-x)$ and $x_0 = 1$ the Gauss-Newton method will give $x_k=(-1)^k$. The unique solution would have been $x_*=0$. So we have to at least add an additional rule like that the used linearization of $f_i$ around $x_{k-1}$ may only be changed if it doesn't qualify as a linearization of $f_i$ around $x_k$. $\endgroup$ – Thomas Klimpel Aug 16 '11 at 17:38
  • $\begingroup$ Isn't what you propose basically equivalent to an active-set method on the problem of minimizing $\sum t_i^2$ under the constraints $t_i \geq 0$ and $t_i \geq y_i - b_i^T x$ for all $i$? At each iteration, you have an index set $I$ such that $t_i = y_i - b_i^T x$ for $i \in I$ and simply substitute those $t_i$'s in the objective? $\endgroup$ – Dominique Oct 30 '11 at 4:35
  • $\begingroup$ @Dominique You are right, it is an active set method with an especially simple rule how to select the next active set. For a general quadratic programming problem, this rule would be too simple. However, while it is easy to write down a (strictly convex) quadratic programming problem where this rule fails to converge in a finite number of steps, this rule might actually work for problems of the type given above. $\endgroup$ – Thomas Klimpel Oct 31 '11 at 0:25
  • $\begingroup$ You might try asking this on scicomp.stackexchange.com $\endgroup$ – David Ketcheson Jan 12 '12 at 14:50
  • $\begingroup$ @ThomasKlimpel If we agree that the active-set approach is equivalent to Gauss-Newton, then convergence is guaranteed in a finite number of steps since there are only a finite number of possible active sets ($2^m$ where $m$ is the number of inequality constraints, including bounds). $\endgroup$ – Dominique May 25 '12 at 21:31

Your Answer

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

Browse other questions tagged or ask your own question.