A Modified Sufficient Descent Polak–Ribiére–Polyak Type Conjugate Gradient Method for Unconstrained Optimization Problems

Abstract

In this paper, a modification to the Polak–Ribiére–Polyak (PRP) nonlinear conjugate gradient method is presented. The proposed method always generates a sufficient descent direction independent of the accuracy of the line search and the convexity of the objective function. Under appropriate conditions, the modified method is proved to possess global convergence under the Wolfe or Armijo-type line search. Moreover, the proposed methodology is adopted in the Hestenes–Stiefel (HS) and Liu–Storey (LS) methods. Extensive preliminary numerical experiments are used to illustrate the efficiency of the proposed method.

1. Introduction

Conjugate gradient methods are among the most popular methods for solving optimization problem, especially for large-scale problems due to the simplicity and low storage of their iterative form [1].

Consider the following unconstrained optimization problem:

$$min\{f\left(x\right):x\in R^n\},$$

(1)

where $f:R^n\to R$ is continuously differentiable. Let $x_0$ be any initial point of the solution of the problem (1), then the conjugate gradient method generates an iteration sequence as follows:

$$x_{k+1}=x_k+{\alpha }_k{d}_k,k=0,1,2,...$$

(2)

where $x_k$ is the kth iterative point, ${\alpha }_k>0$ is a steplength which is obtained by carrying out some line search, and $d_k$ is a search direction defined by

$$d_k=\left\{\begin{array}{cc}-g_k,\hfill & \mathrm{if}k=0,\hfill \\ -g_k+{\beta }_k{d}_{k-1},\hfill & \mathrm{if}k\ge 1,\hfill \end{array}\right.$$

(3)

where $g_k=g\left(x_k\right)$ denotes the gradient of the function $f\left(x\right)$ at $x_k$ and ${\beta }_k$ is a scalar that determines different conjugate gradient methods [2,3,4,5,6]. In this paper, we focus our attention on well-known methods such as Polak–Ribière–Polyak (PRP) [4,5], Hestenes–Stiefel (HS) [3] and Liu–Storey (LS) [6] methods which share the same numerator $g_k^T{y}_{k-1}$ in ${\beta }_k$. The update parameters of these methods are, respectively, given by

$${\beta }_k^{PRP}=\frac{g_k^T{y}_{k-1}}{\parallel g_{k-1}{\parallel }^2},{\beta }_k^{HS}=\frac{g_k^T{y}_{k-1}}{d_{k-1}^T{y}_{k-1}},{\beta }_k^{LS}=-\frac{g_k^T{y}_{k-1}}{d_{k-1}^T{g}_{k-1}},$$

(4)

where $y_{k-1}=g_k-g_{k-1},\parallel ·\parallel$ denotes the Euclidean norm of vectors. Other nonlinear conjugate gradient methods and their global convergence can be found in [1,7].

It is well-known that the PRP, HS and LS methods are generally regarded to be the most efficient methods in practical computation. This can be attributed to the property (*), which was derived in Gilbert and Nocedal [8]. Polak–Ribière [4] obtained the global convergence of the PRP method for the strongly convex functions with exact line search. Yuan [9] also obtained the global convergence of the PRP method under the assumption that the search direction satisfies a descent condition:

$$g_k^T{d}_k<0,\forall k\ge 0.$$

(5)

and the following standard Wolfe line search

$$\left\{\begin{array}{c}f(x_k+{\alpha }_k{d}_k)-f\left(x_k\right)\le \delta {\alpha }_k{g}_k^T{d}_k,\hfill \\ g{(x_k+{\alpha }_k{d}_k)}^T{d}_k\ge \sigma g_k^T{d}_k,\hfill \end{array}\right.$$

(6)

where $0<\delta \le \sigma <1$.

Their convergence properties are not so good in many situations. Powell [10] gave a counter example which showed that there exist nonconvex functions on which the PRP method does not converge globally even if the exact line search is used. Inspired by Powell’s work, Gilbert and Nocedal [8] proved that the modified PRP method is globally convergent in which ${\beta }_k$ is given by ${\beta }_k^{PRP+}=max\{{\beta }_k^{PRP},0\}$. The search direction prevents effectively jamming phenomena from occurring and satisfies the descent property (5) or the following sufficient descent condition:

$$g_k^T{d}_k\le -c{\parallel g_k\parallel }^2,\forall k\ge 0,c>0,$$

(7)

which is very important for establishing the global convergence of the proposed method. In [11], Hager and Zhang proposed a modified HS formula for ${\beta }_k$ defined by

$${\beta }_k^{HZ}={\beta }_k^{HS}-2\frac{\parallel y_k{\parallel }^2{g}_k^T{d}_{k-1}}{{\left(d_{k-1}^T{y}_{k-1}\right)}^2}.$$

More specifically, in their proposed method, called CG-DESCENT. They showed that the method possesses the sufficient descent property with c = 7/8. Afterwards, they also presented the following extension of ${\beta }_k^{HZ}$:

$${\beta }_k^{HZ}={\beta }_k^{HS}-{\theta }_k\frac{\parallel y_k{\parallel }^2{g}_k^T{d}_{k-1}}{{\left(d_{k-1}^T{y}_{k-1}\right)}^2},$$

where ${\theta }_k$ is a nonnegative parameter. If ${\theta }_k\ge \theta >1/4$, then the method possesses the sufficient descent property with $c=1-1/\left(4\theta \right)$. Cheng [12] developed a two term PRP-based descent method satisfying (7) by use of the projection technique for unconstrained optimization problem. Yu et al. [13] proposed a modified form of ${\beta }_k^{PRP}$ as follows:

$${\beta }_k^{DPRP}={\beta }_k^{PRP}-\mu \frac{\parallel y_k{\parallel }^2}{\parallel g_k{\parallel }^4}{g}_{k+1}^T{d}_k.$$

It is important that if $\mu >\frac{1}{4}$, then the condition (7) is achieved with $c=1-\frac{1}{4\mu }$. Yuan [14] present a new PRP formula defined by

$${\beta }_k^{MPRP}={\beta }_k^{PRP}-min\{{\beta }_k^{PRP},\mu \frac{\parallel y_k{\parallel }^2}{\parallel g_k{\parallel }^4}{g}_{k+1}^T{d}_k\},$$

where $\mu >\frac{1}{4}$ guaranteeing the descent property (7) and ${\beta }_k^{MPRP}\ge 0$. Livieris and Pintelas [15] proposed a new class of spectral conjugate gradient methods which ensures sufficient descent independent of the accuracy of the line search.

Wei et al. [16] gave a variant of the PRP method called the VPRP method. The parameter ${\beta }_k$ in the VPRP method is given by

$${\beta }_k^{VPRP}=\frac{\parallel g_k{\parallel }^2-\frac{\parallel g_k\parallel }{\parallel g_{k-1}\parallel }{g}_k^T{g}_{k-1}}{\parallel g_{k-1}{\parallel }^2}.$$

Based on the VPRP method, Zhang [17] made a little modification and obtained the NPRP method as follows,

$${\beta }_k^{NPRP}=\frac{\parallel g_k{\parallel }^2-\frac{\parallel g_k\parallel }{\parallel g_{k-1}\parallel }|g_k^T{g}_{k-1}|}{\parallel g_{k-1}{\parallel }^2},$$

and established the sufficient descent property (7) of the NPRP method. Recently, Zhang [18] proposed a three-term conjugate gradient method called MPRP method in which the direction $d_k$ takes the following form:

$$d_k=-g_k+{\beta }_k^{PRP}{d}_{k-1}-\frac{g_k^T{d}_{k-1}}{\parallel g_{k-1}{\parallel }^2}{y}_{k-1},$$

(8)

leading to the MPRP method with the sufficient descent property. This property always holds independent of any line search and the convexity of the objective function. Under the following line search

$$f(x_k+{\alpha }_k{d}_k)\le f\left(x_k\right)-\delta {\alpha }_k^2{\parallel d_k\parallel }^2,$$

(9)

where ${\alpha }_k=\max \{{\rho }^i,i=1,2,...\}$ with $0<\rho ,\delta <1$, the global convergence of the MPRP method is established. Note that the MPRP method in [18] will reduce to the standard PRP method if exact line search is used and converges globally under the line search (9). However, it fails to converge under the weak Wolfe line search (6). The main reason lies in the trust region property (Lemma 1 in Section 2) that is not satisfied by the MPRP method. Based on the method in [12,18], Dong et al. [19] propose a three-term PRP-type conjugate gradient method which always satisfies the sufficient descent condition independently of line searches employed.

Motivated by the above observations, we propose a modified three-term PRP formula based on (8), which possesses not only the sufficient descent property but also the trust region feature. In the following, we first reformulate the search direction (8) into a new form, which can be written as follows:

$$d_k=-g_k+{\beta }_k^{PRP}{d}_{k-1}-{\beta }_k^{PRP}\frac{g_k^T{d}_{k-1}}{g_k^T{y}_{k-1}}{y}_{k-1}.$$

(10)

Then, we can consider the following general iteration form:

$$d_k=-g_k+{\beta }_k{d}_{k-1}-{\beta }_k\frac{g_k^T{d}_{k-1}}{g_k^T{y}_{k-1}}{y}_{k-1}.$$

(11)

with any ${\beta }_k$, it is not difficult to deduce that the direction defined by (11) satisfies

$$d_k^T{g}_k=-{\parallel g_k\parallel }^2,$$

(12)

which is independent of any line search and the convexity of the objective function.

In this paper, we further study the PRP method and suggest a new three term PRP method to improve the numerical performance and obtain better property of the PRP method. The remaining of this paper is organized as follows. In Section 2, we present a modified PRP method by using a new technique and establish its global convergence. In Section 3, the new technique is extended to the HS and LS method. In the last section, some numerical results are reported to show the modified methods are efficient.

2. The Modified PRP Method and Its Properties

In order to have the sufficient descent condition and keep simple structure and good properties, we take a modification to the denominator of the PRP formula, namely,

$${\beta }_k^{ZPRP}=\frac{g_k^T{y}_{k-1}}{max\{\mu \parallel d_{k-1}\parallel \parallel y_{k-1}\parallel ,\parallel g_{k-1}{\parallel }^2\}},$$

(13)

where $\mu >0$. For convenience, we call the iterative form by (2), (11) and (13) a ZPRP method. It is obvious that the ZPRP method reduces to the PRP method if $\mu \parallel d_{k-1}\parallel \parallel y_{k-1}\parallel \le \parallel g_{k-1}{\parallel }^2$.

Then, we give the modified PRP type conjugate gradient method below (Algorithm 1).

Algorithm 1 Modified PRP-type Conjugate Gradient Method

Step 0: Given an initial point $x_0\in R^n$, $ϵ>0$, $d_0=-g_0$, set $k:=0$. Step 1: If $\parallel g_k\parallel \le ϵ$, then stop. Otherwise, go to Step 2. Step 2: Find the step size ${\alpha }_k$ satisfying a suitable line search. Step 3: Let $x_{k+1}=x_k+{\alpha }_k{d}_k$. Step 4: Compute the search direction $d_{k+1}$ by (11) where ${\beta }_{k+1}={\beta }_{k+1}^{ZPRP}$ is given by (13). Step 5: Set $k:=k+1$ and go to Step 1.

The following lemma shows that the direction $d_k$ determined by (11) satisfies a trust region property.

Lemma 1.

Let $d_k$ be defined by (11) with ${\beta }_k^{ZPRP}$, then we have

$$\parallel d_k\parallel \le (1+\frac{2}{\mu })\parallel g_k\parallel .$$

(14)

Proof of Lemma 1.

By (13), for all $k\ge 1$, we have

$$\begin{array}{ccc}\hfill |{\beta }_k^{ZPRP}|& \le & \frac{\parallel g_k\parallel \parallel y_{k-1}\parallel }{max\{\mu \parallel d_{k-1}\parallel \parallel y_{k-1}\parallel ,\parallel g_{k-1}{\parallel }^2\}}\hfill \\ & \le & \frac{\parallel g_k\parallel }{\mu \parallel d_{k-1}\parallel }\hfill \end{array}$$

(15)

From (11), (13) and (15), we obtain

$$\begin{array}{ccc}\hfill \parallel d_k\parallel & \le & \parallel g_k\parallel +|{\beta }_k^{ZPRP}|\parallel d_{k-1}\parallel +|{\beta }_k^{ZPRP}|\frac{\parallel g_k\parallel \parallel d_{k-1}\parallel }{|g_k^T{y}_{k-1}|}\parallel y_{k-1}\parallel \hfill \\ & \le & \parallel g_k\parallel +\frac{1}{\mu }\parallel g_k\parallel +\frac{|g_k^T{y}_{k-1}|}{\mu \parallel d_{k-1}\parallel \parallel y_{k-1}\parallel }\frac{\parallel g_k\parallel \parallel d_{k-1}\parallel }{|g_k^T{y}_{k-1}|}\parallel y_{k-1}\parallel \hfill \\ & =& (1+\frac{2}{\mu })\parallel g_k\parallel .\hfill \end{array}$$

(16)

The proof is completed. ☐

3. Global Convergence of the ZPRP Method

In this section, we come to show the global convergence of our proposed method. The following assumptions are often used in the literature to analyze the global convergence of conjugate gradient methods with inexact line searches.

Assumption 1

(i)

The level set $\Omega =\{x\in R^n|f\left(x\right)\le f\left(x_0\right)\}$ is bounded.

(ii)

In some neighborhood N of $\Omega$, f is continuously differentiable and its gradient is Lipschitz continuous, that is, there exists a constant $L>0$ such that $\parallel g\left(x\right)-g\left(y\right)\parallel \le L\parallel x-y\parallel ,\forall x,y\in N$.

We first prove the ZPRP method is globally convergent with Wolfe line search (6). Under Assumption 1, we give a useful Zoutendijk condition [20].

Lemma 2.

Suppose that Assumption 1 holds. Consider the method in the form of (2) and (3) where $d_k$ is a descent direction and ${\alpha }_k$ satisfies the Wolfe line search conditions (6). Then we have

$$\sum _{k\ge 0}\frac{{\left(g_k^T{d}_k\right)}^2}{\parallel d_k{\parallel }^2}<+\infty .$$

(17)

Obviously, the Zoutendijk condition (17) and (12) imply that

$$\sum _{k\ge 0}\frac{\parallel g_k{\parallel }^4}{\parallel d_k{\parallel }^2}<+\infty .$$

(18)

Theorem 1.

Suppose that Assumption 1 holds. Consider the ZPRP method, and ${\alpha }_k$ is obtained by the Wolfe conditions (6). Then we have

$$\underset{k\to \infty }{lim}\parallel g_k\parallel =0.$$

(19)

Proof of Theorem 1.

By Lemma 1, we have $\parallel d_k\parallel \le (1+\frac{2}{\mu })\parallel g_k\parallel$. Let $C=1+\frac{2}{\mu }$, then we get

$$\begin{array}{c}\hfill \parallel d_k{\parallel }^2\le C^2{\parallel g_k\parallel }^2,\end{array}$$

(20)

which implies

$$\sum _{k=0}^{\infty }{\parallel g_k\parallel }^2\le C^2\sum _{k=0}^{\infty }\frac{\parallel g_k{\parallel }^4}{\parallel d_k{\parallel }^2}<+\infty .$$

(21)

Hence, (19) holds. The proof is completed. ☐

Next, we prove the global convergence of the ZPRP method under the condition (9).

Theorem 2.

Suppose that Assumption 1 holds. Consider the ZPRP method and ${\alpha }_k$ satisfies the Armijo line search (9). Then we have

$$\underset{k\to \infty }{lim\; inf}\parallel g_k\parallel =0.$$

(22)

Proof of Theorem 2.

Suppose that the conclusion is not true. Then there exists a constant $ϵ>0$ such that $\forall k\ge 0$,

$$\parallel g_k\parallel \ge ϵ.$$

(23)

From (9) and Assumption 1 (i), we have

$$\underset{k\to \infty }{lim}{\alpha }_k^2{\parallel d_k\parallel }^2=0.$$

(24)

If ${lim\; inf}_{k\to \infty }{\alpha }_k>0$, we get from (24) that ${lim\; inf}_{k\to \infty }\parallel d_k\parallel =0$. From (12), we get ${lim\; inf}_{k\to \infty }\parallel g_k\parallel =0$, which contradicts (23).

Suppose ${lim\; inf}_{k\to \infty }{\alpha }_k=0$, then there is an infinite index set K such that

$$\underset{k\in K,k\to \infty }{lim}{\alpha }_k=0.$$

(25)

From (9), it follows that when $k\in K$ is sufficiently large, ${\rho }^{-1}{\alpha }_k$ satisfies the following inequality,

$$f(x_k+{\rho }^{-1}{\alpha }_k{d}_k)-f\left(x_k\right)>-\delta {\rho }^{-2}{\alpha }_k^2{\parallel d_k\parallel }^2.$$

(26)

By Assumption 1 (ii) and the mean value theorem, there is a ${\eta }_k\in (0,1)$ such that

$$\begin{array}{ccc}f(x_k+{\rho }^{-1}{\alpha }_k{d}_k)-f\left(x_k\right)\hfill & =\hfill & {\rho }^{-1}{\alpha }_{k}g{(x_k+{\eta }_k{\rho }^{-1}{\alpha }_k{d}_k)}^T{d}_k\hfill \\ & =\hfill & {\rho }^{-1}{\alpha }_k{(g(x_k+{\eta }_k{\rho }^{-1}{\alpha }_k{d}_k)-g\left(x_k\right))}^T{d}_k+{\rho }^{-1}{\alpha }_{k}g{\left(x_k\right)}^T{d}_k\hfill \\ & \le \hfill & L{\rho }^{-2}{\alpha }_k^2{\parallel d_k\parallel }^2-{\rho }^{-1}{\alpha }_k{g}_k^T{d}_k\hfill \\ & =\hfill & L{\rho }^{-2}{\alpha }_k^2\parallel d_k{\parallel }^2-{\rho }^{-1}{\alpha }_k{\parallel g_k\parallel }^2\hfill \end{array}$$

(27)

By (20), (26) and (27), we can get that

$$\parallel g_k{\parallel }^2\le {\rho }^{-1}(\delta +L){\alpha }_k{C}^2.$$

(28)

Together with (25), (28) implies ${lim}_{k\in K,k\to \infty }\parallel g_k\parallel =0$. This also yields a contradiction. The proof is completed. ☐

4. Extension to the HS and LS Method

In this section, we extend the idea above to the HS and LS method. The corresponding method is called the ZHS method and the ZLS method in which ${\beta }_k$ is respectively defined by

$${\beta }_k^{ZHS}=\frac{g_k^T{y}_{k-1}}{max\{\mu \parallel d_{k-1}\parallel \parallel y_{k-1}\parallel ,d_{k-1}^T{y}_{k-1}\}},{\beta }_k^{ZLS}=\frac{g_k^T{y}_{k-1}}{max\{\mu \parallel d_{k-1}\parallel \parallel y_{k-1}\parallel ,-g_{k-1}^T{d}_{k-1}\}}$$

(29)

where $\mu >0$. It is obvious that ${\beta }_k^{ZLS}={\beta }_k^{ZPRP}$ since $g_k^T{d}_k=-{\parallel g_k\parallel }^2$. Hence, we now only need to discuss the global convergence of the ZHS method.

The following theorem shows that the ZHS method converges globally with the Wolfe line search (6).

Theorem 3.

Let Assumption 1 hold. Consider the ZHS method and ${\alpha }_k$ is obtained by the Wolfe line search (6), then

$$\underset{k\to \infty }{lim}\parallel g_k\parallel =0.$$

(30)

Proof of Theorem 3.

Suppose by contradiction that the conclusion is not true. Then there exists a constant $ϵ>0$ such that $\parallel g_k\parallel >ϵ,\forall k\ge 1$. From (29), it follows that

$$|{\beta }_k^{ZHS}|\le \frac{\parallel g_k\parallel \parallel y_{k-1}\parallel }{\mu \parallel d_{k-1}\parallel \parallel y_{k-1}\parallel }=\frac{\parallel g_k\parallel }{\mu \parallel d_{k-1}\parallel }.$$

(31)

By (11) with ${\beta }_k={\beta }_k^{ZHS}$, we can get that

$$\begin{array}{ccc}\parallel d_k\parallel \hfill & \le \hfill & \parallel g_k\parallel +|{\beta }_k^{ZHS}|\parallel d_{k-1}\parallel +|{\beta }_k^{ZHS}|\frac{\parallel g_k\parallel \parallel d_{k-1}\parallel }{|g_k^T{y}_{k-1}|}\parallel y_{k-1}\parallel \hfill \\ & \le \hfill & \parallel g_k\parallel +\frac{\parallel g_k\parallel }{\mu }+\frac{\parallel g_k\parallel }{\mu }\hfill \\ & =\hfill & (1+\frac{2}{\mu })\parallel g_k\parallel .\hfill \end{array}$$

(32)

Hence, combing with (17),

$$\sum _{k=0}^{\infty }{\parallel g_k\parallel }^2\le {(1+\frac{2}{\mu })}^2\sum _{k=0}^{\infty }\frac{\parallel g_k{\parallel }^4}{\parallel d_k{\parallel }^2}<\infty .$$

(33)

which leads to a contradiction. The proof is completed. ☐

The following result shows that the ZHS method with the Armijo line search (9) possesses global convergence.

Theorem 4.

Let Assumption 1 hold. Consider the ZHS method and ${\alpha }_k$ is obtained by the line search (9), then

$$\underset{k\to \infty }{lim\; inf}\parallel g_k\parallel =0.$$

(34)

Proof of Theorem 4.

The proof is similar to the proof of the global convergent property of the ZPRP method given in Theorem 2 in this paper. We omit it here. ☐

5. Numerical Experiments

In this section, we report some numerical results on some of the unconstrained optimization problems in the CUTE [21] test problem libraty. We test the ZPRP method and ZHS method, and compare the performance of the these two methods with the MPRP method in [18]. The parameters $\delta ={10}^{-4},\rho =0.3$ and $\mu =0.001$. All codes were written in MATLAB R2012a and run on PC with 3.00 GHz CPU processor and Win 7 operation system. We use the stopping iteration $\parallel g_k{\parallel }_{\infty }\le {10}^{-6}$. The detailed numerical results are listed on the web site: http://mathxiuxiu.blog.sohu.com/326066259.html.

We first evaluate the performance of the ZPRP method with that of CG-DESCENT proposed by Hager and Zhang (2005) and all methods with the Wolfe line search (6). Figure 1, Figure 2 and Figure 3 show the numerical performance of the above methods related to the total number of iterations, the number of function and gradient evaluations, CPU time, respectively, which are evaluated using the profiles of Dolan and Moré [22]. For each method, we plot the fraction P of problems for which the method is within a factor t of the smallest number of iterations, or the smallest number of function evaluations or least CPU time, respectively. The left side of the figure gives the percentage of the test problems for which a method is the fastest; the right side gives the percentage of the test problems that are successfully solved by each of the methods. The top curve is the method that solved the most problems in a time that was within a factor t of the best time. Clearly, the ZPRP method has the better performance since it illustrates the best probability of being the optimal solver, outperforming CG-DESCENT. From Figure 1, we can obtain the ZPRP method solves about 59.5% of the test problems with the least number of function evaluations while CG-DESCENT solve about 56.5% of the test problems. For the total number of function and gradient evaluations, in Figure 2 illustrates that the ZPRP method solves 55.2% of the test problems with the least number of function and gradient evaluations while CG-DESCENT solve about 52.2% of the test problems. Therefore, the ZPRP method outperforms CG-DESCENT.

In the sequel, we compare the performance of the ZPRP method with that of the ZHS method and the MPRP method in [18] and all methods with the line search (9). Figure 4, Figure 5 and Figure 6 list the performance of the above methods relative to CPU time, the number of function evaluations and the number of gradient evaluations, respectively. From Figure 4, we can observe that the ZPRP method outperforms the MPRP and ZHS method. More analytically, the performance profile for the number of iteration shows that ZPRP can solve 61% of the test problems with the least number while MPRP and ZHS solve about 47.5% and 45.2% of the test problems, respectively. As regards the number of function and gradient evaluations, Figure 5 shows that the ZPRP solves 80% of the test problems with the least number. Hence, the performance of the ZPRP method slightly better than that of the MPRP and ZHS methods.

6. Conclusions

In this paper, we first proposed a modified PRP formula which provides sufficient descent directions for the objective function independent of any line search. Then we applied the technique to HS and LS conjugate gradient methods which also ensure the sufficient descent property. The global convergence of modified methods are established under the standard Wolfe line search or Armijo line search. Moveover, numerical experiments show that the proposed methods are promising. Our future work is concentrated on applying our coefficient ${\beta }_k$ with spectral conjugate gradient method [15] which ensures sufficient descent independent of the accuracy of the line search and studying the convergence properties of a spectral conjugate gradient method.