I have a question on the convergence of optimization schemes for minimizing smooth, possibly non-convex functions. Can the popular schemes such as Newton, quasi-Newton, and conjugate gradient converge to a non-stationary point even when Strong Wolfe conditions are satisfied at every time step? In other words, are Strong Wolfe conditions (sufficient reduction in function and gradient values) sufficient for ensuring convergence to a stationary point? Are there any simple counter-examples?
For simplicity, throughout the answer I refer to the book "Numerical Optimization" by Nocedal and Wright for citing theorems and results.
All the methods you cite belong to the class of line search methods. Global convergence for these methods in the case of smooth functions requires two assumptions: (i) the step size has to satisfy the Wolfe conditions (either strong or weak) at any iteration; (ii) the angle between the chosen direction and the steepest descent direction has to be bounded away from 90°. This last result is a corollary of the Zoutendijk theorem (Theorem 3.2, page 43).
By this you obtain that the steepest descent method is always globally convergent (since the direction has always an angle of 0°). Newton and Quasi-Newton are globally convergent if the B matrices (either Hessian or its approximation) "have a bounded condition number and are positive definite" (page 45). For the conjugate gradients method, you can only prove a weaker result using a subsequence of the gradient norms (page 46).
To expand on these results you can also check sections 5.2 and 8.4.
Please note that your question "Can the popular schemes such as Newton, quasi-Newton, and conjugate gradient converge to a non-stationary point even when Strong Wolfe conditions are satisfied at every time step?" is not the negation of "In other words, are Strong Wolfe conditions (sufficient reduction in function and gradient values) sufficient for ensuring convergence to a stationary point?"!
And in this context that is very important!
The Strong Wolfe condition guarantees (see the cites by Simone Scardapane) that the norm of the gradient ||\grad f(x_k)|| tends to 0 for k to \infty. That means that the line search algorithm cannot converge to a non-stationary point.
However, that also does not mean that the method will converge to a stationary point. If you do not have additional information (like curvature information on the Hessian) it is possible to construct a function (even in 1D) with two (or more) global minima such that the line search algorithm constructs a non-converging sequence of points that has these global minima as cluster points.
- Badges
- Science topic
- Similar topics
- Mathematics
- Algebra
- Matrix