Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  Thomas Klimpel Aug 16 '11 at 17:38
    
Please condense your question down a bit to the univariate case (like your example). And i think it is useful to consider subgradient methods just to see where the difference between them and gauss-newton is. For example in the univariate gauss-newton we say that the next approximation to the root comes from the root of the tangent at the function of the current approximation. So for a piecewise linear function there should only be a finite number of possible approximations (like in your example where there are two possibilites). –  Peter Sheldrick Sep 9 '11 at 4:37
    
But if you look at this method "look for the root of the tangent" what you are really doing is looking for a direction to optimize - for the univariate case the direction can only be left or right - and then you look for a steplenght. For gauss-newton this steplength gets determined by where the tangant has its root. So the possible steplengths you can get are determined by the shape of the function (and $x_0$). However, for subgradient methods they look at all sorts of possible ways to get the steplength - for example you can also look at constant step length. Things you should consider. –  Peter Sheldrick Sep 9 '11 at 4:41
    
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? –  Dominique Oct 30 '11 at 4:35
    
@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. –  Thomas Klimpel Oct 31 '11 at 0:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.