Past exam of the continuous optimisation course of the University of Oxford / 2011 / 2 / iii

Use the exact line searches from part (i). After minimizing along one coordinate, the corresponding gradient component is zero. Unless the optimum has been reached, the whole nonzero gradient therefore lies along the other coordinate, which is selected next. The chosen signed coordinate direction then has $\cos {\theta }_k=1$. A selected zero gradient component can be skipped; it already minimizes that coordinate.

The Zoutendijk theorem therefore gives $\nabla f(x_k)\to 0$. The unique point with zero gradient isSince $\nabla f(x)=H(x-x^{\ast })$ and $H$ is invertible, gradient convergence implies $x_k\to x^{\ast }$. Positive definiteness makes this the unique global minimum.

Convergence also holds if “line search” is interpreted as any fixed-parameter Wolfe search. If coordinate $i$ is selected, its signed step $s$ satisfies $s=-\omega g_i/h$, where $h=c^{-2}+d^{-2}$ and $1-\eta \le \omega \le 2(1-\sigma )$. Sufficient decrease gives $f(x_k)-f(x_{k+1})\ge \sigma (1-\eta )g_i(x_k{)}^2/h$. Summation shows that selected gradient components tend to zero and step lengths tend to zero. The other component was selected in the preceding step; Lipschitz continuity then makes it tend to zero as well. Thus the full gradient converges to zero. The simple one-step angle argument and sharp Q-linear factor below use exact coordinate minimization; arbitrary Wolfe choices need not have that same Euclidean one-step factor.