Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients

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.