Nonlinear conjugate gradient methods

Work in finite-dimensional real Euclidean space ${\mathbb{R}}^n$, $n\ge 1$, with its standard inner product and norm (The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$). Let $D\subseteq {\mathbb{R}}^n$ be open, let $f:D\to \mathbb{R}$ be $C^1$ (Continuously differentiable maps, local inverses, and local diffeomorphisms), and write $g(x)=\mathrm{\nabla }f(x)$ using the gradient convention of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case.

The inputs are $x_0\in D$, a method choice $\mathrm{F}\mathrm{R}$ or $\mathrm{P}\mathrm{R}+$, constants $0<c_1<c_2<1\mathrm{/}2$, an outer iteration limit $K\in \mathbb{N}$, and a line-search mode. In bounded-strong-Wolfe mode, also supply finite expansion and zoom limits $E,Z\in \mathbb{N}$. In exact-SPD-quadratic mode, supply a real symmetric positive-definite matrix $A$ and vector $b$ such that $D={\mathbb{R}}^n$ and $f(x)=\frac{1}{2}{x}^{T}Ax-b^{T}x$. The $\mathrm{P}\mathrm{R}+$ choice also takes $\sigma ,C>0$. Evaluations and arithmetic are exact real operations; this definition makes no finite-precision error claim.

1. Evaluate $g_0=g(x_0)$. If $g_0=0$, return status stationary with $x_0$. Otherwise set $d_0=-g_0$.

2. For $k=0,\dots ,K-1$, if $g_k=0$, return stationary with $x_k$. For $k\ge 1$, set ${\beta }_{k-1}^{\mathrm{F}\mathrm{R}}=\frac{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2}{\mathrm{\parallel }{g}_{k-1}{\mathrm{\parallel }}_2^2},{\beta }_{k-1}^{\mathrm{P}\mathrm{R}+}=\max \text{\hspace{0.17em}⁣}\{0,\frac{g_k^T(g_k-g_{k-1})}{\mathrm{\parallel }{g}_{k-1}{\mathrm{\parallel }}_2^2}\}\mathrm{.}$ Choose the selected coefficient and form $d_k^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}=-g_k+{\beta }_{k-1}{d}_{k-1}$. For $k=0$, set $d_0^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}=d_0=-g_0$. Denominators are nonzero because the procedure has already returned at any zero gradient.

3. In the $\mathrm{P}\mathrm{R}+$ method, test the candidate at the current point. If $g_k^T{d}_k^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}>-\sigma \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2$ or $\mathrm{\parallel }{d}_k^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}{\mathrm{\parallel }}_2>C\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$, restart by setting $d_k=-g_k$ and, only when $k\ge 1$, ${\beta }_{k-1}=0$, and record that a restart occurred. Otherwise set $d_k=d_k^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}$. In the $\mathrm{F}\mathrm{R}$ method set $d_k=d_k^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}$ without this safeguard. If $g_k^T{d}_k\ge 0$, return search-failure with cause invalid-direction.

4. In bounded-strong-Wolfe mode, call Finite-budget bracketing and zoom for a strong Wolfe step at $(f,x_k,d_k,c_1,c_2)$ with budgets $E,Z$. That procedure returns a step only after checking both strong Wolfe inequalities. If it instead returns invalid-direction, domain-exit, or evaluation-budget-exhausted, return search-failure with that cause.

5. In exact-SPD-quadratic mode, when $g_k^T{d}_k<0$, compute $t_k=-\frac{g_k^T{d}_k}{d_k^{T}A{d}_k}\mathrm{.}$ If the denominator is nonpositive or the computed step is not positive, return search-failure with cause invalid-exact-model. Otherwise verify the strong Wolfe inequalities and return search-failure if either fails. This mode records the exact-line-search specialization; it does not replace the finite-budget search mode.

6. For an accepted step, set $x_{k+1}=x_k+t_k{d}_k$ and evaluate $g_{k+1}$. If $g_{k+1}=0$, return stationary with $x_{k+1}$. After the loop, return iteration-limit with the last iterate, the accepted trace, and all restart flags. A failure or stationary status returns immediately with the trace so far.

The FR and safeguarded PR+ convergence statements concern infinite sequences following the respective recurrences and direction rules above, with a successful strong Wolfe update at every index; they do not concern an infinite execution of this finite-$K$ procedure. Each finite execution can realize only a prefix of such a sequence. A finite search budget can return search-failure; it does not certify convergence.

Let $g_k=\mathrm{\nabla }f(x_k)\mathrm{\ne }0$ and let the Fletcher–Reeves directions be $d_0=-g_0,d_k=-g_k+{\beta }_{k-1}{d}_{k-1},{\beta }_{k-1}=\frac{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2}{\mathrm{\parallel }{g}_{k-1}{\mathrm{\parallel }}_2^2}(k\ge 1)\mathrm{.}$ Suppose every accepted step along $d_{k-1}$ satisfies the strong Wolfe curvature inequality with constant $0<c_2<1\mathrm{/}2$. Define $q_k=-\frac{g_k^T{d}_k}{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2},\delta =\frac{1-2c_2}{1-c_2},C_3=\frac{1+c_2}{1-c_2},S_k={\sum }_{j=0}^k\frac{1}{\mathrm{\parallel }{g}_j{\mathrm{\parallel }}_2^2}\mathrm{.}$ Then, for every $k$, $\delta \le q_k\le \frac{1}{1-c_2},\mathrm{\parallel }{d}_k{\mathrm{\parallel }}_2^2\le C_3\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^4{S}_k\mathrm{.}$ In particular every direction is strictly descending, and its normalized directional derivative has a uniform positive lower bound.

The first bound is on $-g_k^T{d}_k\mathrm{/}\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2$, not on the cosine of the angle. It does not by itself give a uniform angle bound.

Let $g\mathrm{\ne }0$ and let $d^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}$ be the PR+ candidate direction from Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients. The safeguarded procedure either keeps $d^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}$ when $g^T{d}^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}\le -\sigma \mathrm{\parallel }g{\mathrm{\parallel }}_2^2,\mathrm{\parallel }{d}^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}{\mathrm{\parallel }}_2\le C\mathrm{\parallel }g{\mathrm{\parallel }}_2,$ or restarts to $d=-g$, where $\sigma ,C>0$. The resulting direction is strictly descending and its angle $\theta$ with $-g$ satisfies $\cos \theta \ge {\delta }_{\mathrm{P}\mathrm{R}}:=\min \{1,\sigma \mathrm{/}C\}>0,$ using the angle convention of Wolfe and strong Wolfe line-search conditions.

Assume function and gradient evaluations at requested in-domain points return real values. For finite outer limit $K$ and finite expansion and zoom limits $E,Z$, the procedure of Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients terminates with one of stationary, search-failure, or iteration-limit. In bounded-strong-Wolfe mode it makes at most $K$ line-search calls and at most $K(E+Z)$ line-search trial evaluations, each of which evaluates the objective and directional derivative at one trial point. Separately, the outer iteration evaluates the gradient at most $K+1$ times: once initially and once after each accepted update. The theorem does not claim a total gradient-evaluation count, because the line search also evaluates directional derivatives. It gives no arithmetic-work or finite-precision error bound.

Let $A\in {\mathbb{R}}^{n\times n}$ be symmetric positive definite, $b\in {\mathbb{R}}^n$, and $f(x)=\frac{1}{2}{x}^{T}Ax-b^{T}x,x\in {\mathbb{R}}^n\mathrm{.}$ In exact arithmetic, run the FR recurrence of Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients with exact line minimization. Its iterates, residuals $r_k=b-A{x}_k$, and directions coincide with the linear conjugate-gradient recurrence of The conjugate-gradient recurrence until the common zero-residual exit. The unrestarted raw PR+ recurrence has the same exact-line-search sequence; the safeguarded PR+ implementation has this equivalence only on runs where its safeguard does not restart. No such equivalence is asserted for non-SPD quadratics, inexact line searches, or finite-precision arithmetic.

Let $D\subseteq {\mathbb{R}}^n$ be open, $f:D\to \mathbb{R}$ be $C^1$, and $x_0\in D$. Let $L_0=\{x\in D:f(x)\le f(x_0)\}$, and suppose $f$ is bounded below on $L_0$. Suppose an open set $N\subseteq D$ contains every trial segment $x_k+[0,t_k]d_k$ and, for one $L>0$, $\mathrm{\parallel }\mathrm{\nabla }f(u)-\mathrm{\nabla }f(v){\mathrm{\parallel }}_2\le L\mathrm{\parallel }u-v{\mathrm{\parallel }}_2(u,v\in N)\mathrm{.}$ Consider an infinite sequence following the FR recurrence $d_0=-g_0$, $d_k=-g_k+(\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }{g}_{k-1}{\mathrm{\parallel }}_2^2)d_{k-1}$ from Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients, with $g_k=\mathrm{\nabla }f(x_k)\mathrm{\ne }0$, feasible updates $x_{k+1}=x_k+t_k{d}_k$, and every $t_k$ a strong Wolfe step for constants $0<c_1<c_2<1\mathrm{/}2$. Then ${\mathrm{lim\hspace{0.17em}inf}}_{k\to \mathrm{\infty }}\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2=0.$ This is a theorem about the infinite recurrence and successful updates, not an infinite execution of the finite-$K$ algorithm. The conclusion is a liminf statement; it does not assert $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\to 0$.

The source proofs use bounded initial level sets to obtain bounded gradients. The argument here does not: the local direction-growth estimate in [F1] is normalized by the current gradient and leads directly to the harmonic contradiction under the hypotheses stated above.

Let $D,f,x_0,L_0,N,L$ satisfy the hypotheses of A uniform descent angle makes the Wolfe gradient norms vanish. Consider an infinite sequence following the PR+ coefficient recurrence and candidate-or-restart direction selection of Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients, with its fixed $\sigma ,C>0$, $d_0=-g_0$, every gradient nonzero, feasible updates $x_{k+1}=x_k+t_k{d}_k$, and every $t_k$ a strong Wolfe step with $0<c_1<c_2<1\mathrm{/}2$. Then $\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}_2⟶0.$ This claim concerns the infinite recurrence with successful updates at every index, not an infinite execution of the finite-$K$ algorithm. Raw PR+ without the stated safeguard is not covered.