6
$\begingroup$

From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.

In addition to that, are the following statements also true?

  • the Gauss-Newton method always results in a direction of strict descent
  • the Gauss-Newton method only requires that the directional derivative of the objective function exist – but you do not need to compute it.
  • the Gauss-Newton method does not require the Hessian.
  • When you’re faced with an optimization problem of the form $\min ||F(x)||$, and $F(x)$ is non-linear, then Gauss-Newton is a good choice because it doesn’t require you to compute the directional derivative.

Any other help is appreciated. My colleagues are in disagreement about those statements.

$\endgroup$
12
+25
$\begingroup$

Just to clarify notation, I'll be discussing the Gauss-Newton method for the problem

$\min \phi(x)=(1/2) \| F(x) \|_{2}^{2}$

with the search direction $p$ computed as the solution to the linear system of equations

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

where $J(x)$ is the matrix of partial derivatives of components of $F(x)$ with respect to the components of $x$. In the following, I'll drop the superscript $(k)$ notation to save some typing.

Assuming that $\phi(x)$ and the individual components of $F(x)$ are continuously differentiable, then by some elementary vector calculus,

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

and assuming that $\phi(x)$ and the individual components of $F(x)$ are twice continuously differentiable,

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

From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.

In the simplest version of the Gauss-Newton method, there is no line search. The iteration is simply $x^{(k+1)}=x^{(k)}+p$. There is no guaranteed convergence result for this simple method, just as there is no guarantee of convergence for Newton's method with the full Hessian and unit step size. However, it does often work in practice.

Adding an approximate line search to the algorithm improves its convergence properties. If a safeguarded approximate line search is used, and if the individual $F_{i}(x)$ function have Lipschitz continuous gradients, and $J(x)^{T}J(x)$ is always nonsingular, then convergence to a stationary point can be guaranteed. See the Nocedal and Wright book cited at the end of this answer.

The Gauss-Newton method always results in a direction of strict descent.

This is basically true. If the matrix $J(x)^{T}J(x)$ in the Gauss-Newton method is non-singular, then it is symmetric and positive definite and $(J(x)^{T}J(x))^{-1}$ is also symmetric and positive definite. The GN direction is

$p=-(J(x)^{T}J(x))^{-1}J(x)^{T}F(x)$

and assuming that $J(x)^{T}F(x) \neq 0$, the directional derivative in the direction $p$ is

$\nabla \phi(x)^{T}p=-(J(x)^{T}F(x))^{T} \; (J(x)^{T}J(x))^{-1}\; (J(x)^{T}F(x)) < 0$.

If $J(x)^{T}F(x)=0$, then you're at a stationary point (and the GN method would stop.)

If $J(x)^{T}J(x)$ is singular, then the Gauss-Newton step is not well defined. Actually, because of the structure of the system of equations, there will be infinitely many directions $p$ that satisfy the equations. If $p$ is chosen arbitrarily from among these directions, the method can fail to converge.

the Gauss-Newton method only requires that the directional derivative of the objective function exist – but you do not need to compute it.

This question is unclear. Directional derivative of what function? In what direction? However, if what you mean by "directional derivative" is "the gradient of $\phi(x)$", then

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

and this is computed during each iteration of the Gauss-Newton method.

If you want the directional derivative of $\phi(x)$ in some particular direction, you can obtain it by taking the dot product of $\nabla \phi(x)$ and that direction.

the Gauss-Newton method does not require the Hessian.

Undoubtedly true. The matrix $J(x)^{T}J(x)$ used in the GN method is not the Hessian of $\phi(x)$.

When you’re faced with an optimization problem of the form min||F(x)||, and F(x) is non-linear, then Gauss-Newton is a good choice because it doesn’t require you to compute the directional derivative.

The Gauss-Newton method works well in practice on many problems, but it can fail when $J(x)^{T}J(x)$ is singular or nearly singular. Stabilization of the Gauss-Newton method is advisable for a more robust algorithm. The Levenberg-Marquardt algorithm is an example of a stabilized version of Gauss-Newton.

Again, it's not clear what you mean by "directional derivative" (of what function in what direction?) If you simply mean the gradient of $\phi(x)$, then you do compute $\nabla \phi(x)$ in the Gauss-Newton method as discussed above. In any case, this isn't a very good "because" reason.

This material is discussed in many textbooks on nonlinear optimization and nonlinear regression. An authoritative source is Nocedal and Wright, Numerical Optimization, 2nd ed. 2006.

$\endgroup$
  • 1
    $\begingroup$ At a very different level, you can consider implementations of the Gauss-Newton and Levenberg-Marquardt methods that avoid forming the matrix $J(x)^{T}J(x)$ by using an iterative method to solve the linear system of equations. This can be very important in practice for very large scale problems but doesn't really change the underlying mathematics of the method. $\endgroup$ – Brian Borchers May 2 '18 at 18:09
  • 1
    $\begingroup$ I believe the OP is asking about applying GN to a nondifferentiable $F:\mathbb{R}^n\to\mathbb{R}^m$. Such problems regularly arise in machine learning, e.g. training a neural net. But in that case, GN does not offer any substantial advantages over stochastic gradient descent, which is the default algorithm. $\endgroup$ – Richard Zhang May 5 '18 at 5:16
  • 1
    $\begingroup$ Perhaps the OP could clarify the question. $\endgroup$ – Brian Borchers May 5 '18 at 13:45
  • $\begingroup$ This is really good. I am asking about applying GN to nondifferentiable $F$, @RichardZhang thanks. But this is still a very good overview. $\endgroup$ – Hunle Jun 3 '18 at 8:35
  • 1
    $\begingroup$ The GN method uses $J(x)$, so the method will fail immediately if it encounters a point where the derivatives aren't defined. Furthermore, the theoretical convergence results require Lipschitz continuity of the derivatives. $\endgroup$ – Brian Borchers Jun 3 '18 at 14:23

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.