Two new limited-memory preconditioned conjugate gradient algorithms for nonlinear optimization problems

1 Introduction

Consider the following nonlinear unconstrained minimization problem

Min f ( x ) , x ∈ R n(1) where f : R ⁿ  → R is a twice continuously differentiable real-valued function. A nonlinear conjugate gradient algorithms to solve (1) have the form

x m + 1 = x m + α m d m ,(2) which is iterative technique and it is starting from an initial guess x₁ ∈ R ⁿ and the positive step length α _m is calculated to satisfy the strong Wolfe conditions and d _m is the search direction. For the preconditioned conjugate gradient techniques the search directions d _m are generated as:

d m + 1 = - H m + 1 g m + 1 + β m d m , d 1 = - H 1 g 1 ,(3) where g_m+1 = ∇ f (x_m+1) and H_m+1 is the inverse Hessian approximation and it is chosen to satisfy the following quasi-Newton equation

H m + 1 y m = v m .(4)

The quasi-Newton method is avoids the requirement to compute Hessian matrices by repeating from iteration to iteration.

We obtain the corresponding update formula for the inverse Hessian approximation [1]

H m + 1 = H m + ( v m - H m y m ) ( v m - H m y m ) T y m T ( v m - H m y m )(5) where y _m  = g_m+1 - g _m and v _m  = x_m+1 - x _m  .

Yang, Xu and Gao [2] made a little modification for self scaling symmetric rank one update wth Davidon’s optimal condition [3] (SHSR1) as follows H m + 1 = ρ m H m + ( v m - ρ m H m y ¯ m ) ( v m - ρ m H m y ¯ m ) T y ¯ m T ( v m - ρ m H m y ¯ m ) where ρ _m is the scaling factor, y ¯ m = ( 1 + ϑ m v m T y m ) y m , ϑ _m  = 6 (f _m  - f_m+1) + 3 (g _m  + g_m+1)  ^T v _m .

There are other methods to find the inverse Hessian approximation, like Davidon, Fletcher and Powell (DFP), which has the form [1]:

H m + 1 = H m + v m v m T v m T y m - ( H m y m ) ( H m y m ) T y m T H m y m(6) and Broyden, Fletcher, Gold Farb and Shanno Method (BFGS), which has the form [1]:

H m + 1 = H m + ( 1 + y m T H m y m y m T v m ) v m v m T v m T y m - ( H m y m v m T ) + ( H m y m v m ) T y m T y m .(7)

The parameter β _m in (3) is a conjugacy parameter. The most well-know formulas of β _m are called Hestenes-Stiefel (H/S) [4], Polak-Ribiere-Polyak (PRP) [5], Dai –Yuan (D/Y) [6] and Fletcher-Reeves(F/R) [7] which have the following forms:

β m HS = g m + 1 T y m d m T y m(8)

β m PRP = g m + 1 T y m ∥ g m ∥ 2(9)

β m DY = ∥ g m + 1 ∥ 2 d m T y m(10)

β m FR = ∥ g m + 1 ∥ 2 ∥ g m ∥ 2(11) where y _m  = g_m+1 - g _m and the symbol ∥ .∥ means the Euclidean norm.

The parameter β _m can be chosen in a variety of ways. For preconditioned conjugate gradient algorithm, we can choose from the choices below:

β m HS = g m + 1 T H m + 1 y m d m T y m(12)

β m FR = g m + 1 T H m + 1 g m + 1 g m T H m + 1 g m(13)

β m DY = g m + 1 T H m + 1 g m + 1 d m T y m(14)

Limited-memory quasi-Newton methods have previously been studied by various authors, for example, as memory-less quasi-Newton methods by Shanno [8], limited-memory BFGS (L-BFGS) by Nocedal [9], and also many of studies focused on limited memory quasi-Newton methods are concentrate on the limited memory BFGS (L-BFGS) method [10–13].

The methods are suitable for large scale problems because the amount of storage required by the algorithms can be controlled by the user. The aim of this paper is to propose two new limited-memory preconditioned conjugate gradient algorithms for solving nonlinear and unconstrained optimization problems because this class of methods is a good efficiency task to solve such problems.

The matrix of the symmetric rank one (SR1),

H m + 1 = H m + ( v m - H m y m ) ( v m - H m y m ) T y m T ( v m - H m y m ) ,(15) and the matrix of (DFP),

H m + 1 = H m + v m v m T v m T y m - ( H m y m ) ( H m y m ) T y m T H m y m(16) have the property that H_m+1y _j  = v _j , where m - M ⩽ m - 1 and it is symmetric, where m is the number of iteration and M is a memory index number.

At each iteration we can transform the two sequences of vectors {v _j  } _{m-M⩽j⩽m-1} and {y _j  } _{m-M⩽j⩽m-1} in to { v ¯ j } m - M ⩽ j ⩽ m - 1 and { y ¯ j } m - M ⩽ j ⩽ m - 1 , so that v ¯ i T y j = 0 for m - M ⩽ i ≠ j ⩽ m - 1,, in order to satisfy the quasi-Newton condition H _m y_m-1 = v_m-1, we let v ¯ j = v j and y ¯ j = y j .

This transformation is easily realized by the following Gram-Schmidt process.

For j = m - 1, m - 2, …, m - M,

v ¯ m j = v j - ∑ i = j + 1 m - 1 y ¯ m i v j v ¯ m iT y ¯ m i v ¯ m i(17) and

y ¯ m j = y j - ∑ i = j + 1 m - 1 v ¯ m i y j v ¯ m iT y ¯ m i y ¯ m i(18) see [14].

The paper is organized as follows: in section 3, we will suggest a new modified symmetric rank one (NMSR1) and a new modified Davidon, Fletcher, and Powell (NMDFP). Section 4 contains the outlines of the new limited memory preconditioned conjugate gradient methods (New1 and New2), these algorithms combine the methods NMSR1 and NMDFP with conjugate gradient methods, also using projection and limited memory, to solve nonlinear unconstrained minimization problems. Then, in section 5, we will study the fulfillment of the quasi-Newton condition and the positive definite condition for NMSR1, as well as the positive definite condition for NMDFP and the descent condition of this new technique. While section 6 includes some numerical results to show the efficiency of these new algorithms (New1 and New2).

In this section, we will suggest a new modified symmetric one (NMSR1) and a new modified Davidon, Fletcher, and Powell (NMDFP) for unconstrained minimization problems.

First we propose the following equation as a new quasi-Newton equation

H m + 1 y m = v m *(19) and we suppose that

v m * = δ 1 ( 2 ∥ g m + 1 ∥ ( f m + 1 - f m - g m T v m ) v m T y m v m + v m )(20)

Where y _m  = g_m+1 - g _m , v _m  = x_m+1 - x _m , g _m  = ∇ f (x _m ), g_m+1 = ∇ f (x_m+1) and δ₁ > 0.

Now, Let

H m + 1 = H m + α m w m w m T(21) where α _m  ∈ R and w _m  ∈ R ⁿ give H _m , y _m and v m * so that the required relationship H m + 1 y m = v m * is satisfied.

To find α _m  and w _m , multiply both sides of Equation(21) by y _m and by using (19), we have

H m + 1 y m = ( H m + α m w m w m T ) y m = v m *(22) note that w m T y m is a scalar, thus

v m * - H m y m = ( α m w m T y m ) w m(23) here,

w m = v m * - H m y m α m ( w m T y m )(24) hence,

α m w m w m T = ( v m * - H m y m ) ( v m * - H m y m ) T α m ( w m T y m ) 2(25) so, Equation (21) becomes

H m + 1 = H m + ( v m * - H m y m ) ( v m * - H m y m ) T α m ( w m T y m ) 2 .(26)

Multiply (23) by y m T to obtain

y m T v m * - y m T H m y m = y m T ( α m w m T y m ) w m(27) we know that α _m is scalar and y m T w m = w m T y m , then the above equation becomes,

y m T v m * - y m T H m y m = α k ( w k T y m ) 2(28) by substituting Equation (28) in Equation (26) we have, the NMSR1 as follows:

H m + 1 NMSR 1 = H m + ( v m * - H m y m ) ( v m * - H m y m ) T y m T ( v m * - H m y m ) .(29)

The correction term of the rank two has the form:

Δ H m = b 1 r 1 r 1 T + b 2 r 2 r 2 T(30) where the constants b₁, b₂ and the vectors r₁ and r₂ are to be determined.

Here,

H m + 1 = H m + Δ H m = H m + b 1 r 1 r 1 T + b 2 r 2 r 2 T(31) by forcing (31) to satisfy the new quasi-Newton condition (19) multiply both sides of Equation (31) by y _m we get, H m + 1 y m = H m y m + b 1 r 1 ( r 1 T y m ) + b 2 r 2 ( r 2 T y m ) and by Equation (19) we have,

v m * = H m y m + b 1 r 1 ( r 1 T y m ) + b 2 r 2 ( r 2 T y m ) ,(32) where r 1 T y m and r 2 T y m can be identified as scalar. Although the vectors r₁ and r₂ in (32) are not unique, so we chose r 1 = v m * , r₂ = H _m y _m , which make (32) to be satisfied, when b 1 = 1 r 1 T y m and b 2 = - 1 r 2 T y m .

Here, the rank two formula can be expressed as the NMDFP formula

H m + 1 NMDFP = H m + v m * v m * T y m T v m * - ( H m y m ) ( H m y m ) T y m T H m y m(33)

Let M ⩾ 0 be a memory index number, and assume that a positive definite symmetric matrix H₀ is given. During the first M iterative steps, we set v m + 1 = [ v 0 * , … , v m * ] and y_m+1 = [y₀, …, y _m ].

But for m ⩾ M, we only use the latest M steps information, which are v m + 1 = [ v m - M + 1 * , … , v m * ] and y_m+1 = [y_m-M+1, …, y _m ]

5 Quasi-Newton condition, positive definite and descent condition

In this section, we will prove the quasi-Newton condition, the positive definite condition, and the descent condition.

Theorem 1. If the new modified symmetric rank one ( H m + 1 NMSR 1 ) is applied to the quadratic with Hessian Q = Q ^T , we have H m + 1 NMSR 1 y m = v m * , m ⩾ 0 .

Proof. Multiply both sides of (29) by y _m to get,

H m + 1 NMSR 1 y m = H m y m + ( v m * - H m y m ) ( v m * - H m y m ) T y m T ( v m * - H m y m ) y m(34) since y m T ( v m * - H m y m ) and ( v m * - H k y m ) T y m are scalars, then ( v m * - H m y m ) T y m = y m T ( v m * - H m y m ) here we get, H m + 1 NMSR 1 y m = H m y m + v m * - H m y m finally, we have, H m + 1 NMSR 1 y m = v m * . ■

Theorem 2. Suppose that g _m  ≠ 0. If H _m is positive definite, then so is H m + 1 NMSR 1 .

Proof. Let X be any non-zero vector, Multiply both sides of Equation (29) by X ^T from left and by X from right, so, we get

X T H m + 1 NMSR 1 X = X T H m X + X T ( v m * - H m y m ) ( v m * - H m y m ) T y m T ( v m * - H m y m ) X(35) since, X T ( v m * - H m y m ) = ( v m * - H m y m ) T X

then, Equation (35) becomes,

X T H m + 1 NMSR 1 X = X T H m X + ( X T ( v m * - H m y m ) ) 2 ( y m T v m * - y m T H m y m ) )(36) since H _m is positive definite, then, y m T H m y m is positive.

Now, to complete the proof, we need to prove that y m T v m * > 0 consider, y m T v m * = δ 1 y m T ( S m ∥ g m + 1 ∥ v m + v m ) where δ₁ > 0 and S m = 2 ( f m + 1 - f m - g m T v m ) v m T y m , under the condition, if S _m  < 0, then take, S m = 2 ∥ g m ∥ 2 v m T y m and we know that y m T v m is positive, then, y m T v m * > 0 .

Or, by Goldstein rule [15]

k 3 ⩽ f m + 1 - f m α g m T d m ⩽ ( 1 - k 3 ) , where k 3 ɛ ( 0 , 1 2 )(37) for case m, we suppose that g m T d m < 0 , and assume that

α g m T d m = α g m T ( - H m g m ) = - α g m T H m g m(38) then, Equation (37) becomes,

k 3 ⩽ f m + 1 - f m - α g m T H m g m ⩽ ( 1 - k 3 ) .(39)

Multiply (39) by - α g m T H m g m , to get,

- k 3 α g m T H m g m ⩾ f m + 1 - f m ⩾ - ( 1 - k 3 ) α g m T H m g m ,(40) so, we have, f m + 1 - f m ⩾ - ( 1 - k 3 ) α g m T H m g m

or , f m + 1 - f m ⩾ - γ α g m T H m g m , γ ∈ [ 1 2 , 1 )(41) here, we have, v m * = δ 1 ( 2 ( f m + 1 - f m - g m T v m ) v m T y m ∥ g m + 1 ∥ v m + v m ) , where δ 1 > 0 multiply both sides by y m T from left, to get y m T v m * = δ 1 y m T ( 2 ( f m + 1 - f m - g m T v m ) v m T y m ∥ g m + 1 ∥ v m + v m ) , this implies that 1 δ 1 y m T v m * = ( 2 ( f m + 1 - f m - g m T v m ) ∥ g m + 1 ∥ + y m T v m ) , or,

1 2 δ 1 ∥ g m + 1 ∥ y m T v m * = ( ( f m + 1 - f m - g m T v m ) + 1 2 ∥ g m + 1 ∥ y m T v m ) ,(42) by Equations (38), (42) gives,

1 2 δ 1 ∥ g m + 1 ∥ y m T v m * = f m + 1 - f m + α g m T H m g m + 1 2 ∥ g m + 1 ∥ y m T v m ,(43) from (41) and (43), we have 1 2 δ 1 ∥ g m + 1 ∥ y m T v m * ⩾ - γ α g m T H m g m + α g m T H m g m + 1 2 ∥ g m + 1 ∥ y m T v m , or, 1 2 δ 1 ∥ g m + 1 ∥ y m T v m * ⩾ P m + 1 2 ∥ g m + 1 ∥ y m T v m where P m = - γ α g m T H m g m + α g m T H m g m

Since γ ∈ [ 1 2 , 1 ) , then P _m  > 0

here, we get 1 2 δ 1 ∥ g m + 1 ∥ y m T v m * ⩾ P m + 1 2 ∥ g m + 1 ∥ y m T v m > 0 implies that, y m T v m * ⩾ 2 δ 1 ∥ g m + 1 ∥ ( P m + 1 2 ∥ g m + 1 ∥ y m T v m ) > 0 then, y m T v m * > 0 so, we have, X T H m + 1 NMSR 1 X = X T H m X + ( X T ( v m * - H m y m ) ) 2 y m T v m * - y m T H m y m > X T H m X + ( X T ( v m * - H m y m ) ) 2 ( y m T v m * ) > 0 then H m + 1 NMSR 1 is positive definite. ■

Theorem 3. Suppose that g _m  ≠ 0. If H _m is positive definite, then so is H m + 1 NMDFP .

Proof. Let X be any non-zero vector, Multiply both sides of Equation (33) by X ^T from left and by X from right, so, we get

X T H m + 1 NMDFP X = X T H m X + X T v m * v m * T y m T v m * X - X T ( H m y m ) ( H m y m ) T y m T H m y m X(44) this implies that X T H m + 1 NMDFP X = X T H m X + ( v m * T X ) 2 y m T v m * - ( ( H m y m ) T X ) 2 y m T H m y m .

Define a 1 = H m 1 2 X and a 2 = H m 1 2 y m where, H m = H m 1 2 H m 1 2 using the definitions of a₁ and a₂, we obtain X T H m + 1 X = X T H m 1 2 H m 1 2 X = a 1 T a 1 X T H m + 1 y m = X T H m 1 2 H m 1 2 y m * = a 1 T a 2 and y m T H m y m = y m T H m 1 2 H m 1 2 y m = a 2 T a 2 hence,

X T H m + 1 NMDFP X = a 1 T a 1 + ( v m * T X ) 2 y m T v m * - ( a 1 T a 2 ) 2 a 2 T a 2(45) or

X T H m + 1 NMDFP X = ∥ a 1 ∥ 2 ∥ a 2 ∥ 2 - 〈 a 1 , a 2 〉 ∥ a 2 ∥ 2 + ( v m * T X ) 2 y m T v m *(46) so, Equation (46) gives

X T H m + 1 NMDFP X = ∥ a 1 ∥ 2 ∥ a 2 ∥ 2 - 〈 a 1 , a 2 〉 ∥ a 2 ∥ 2 + ( v m * T X ) 2 y m T v m * .(47)

By Cauchy Schwarz the first term in the right side of the Equation (47) is nonnegative and the second term is nonnegative also. To complete the proof, we need to show that at lest one of the terms is not equal to zero. Only when if a₁ and a₂ are proportional does the first term disappear, that is if a₁ = β₁a₂ for some scalar β₁ . Therefore, to complete the proof, it is only to prove that if a₁ = β₁a₂, then, ( v m * T X ) 2 y m T v m * > 0 .

Observe that, H m 1 2 X = a 1 = β 1 a 2 = β 1 H m 1 2 y m = H m 1 2 ( β 1 y m ) hence, X = β₁y _m

here, we obtain ( v m * T X ) 2 y m T v m * = ( β 1 v m * T y m ) 2 y m T v m * = β 1 2 ( y m T v m * ) 2 y m T v m * = β 1 2 y m T v m * and in the theorem 2 we proved that y m T v m * > 0 .

Thus, for all for X ≠ 0 X T H m + 1 NMDFP X > 0 .

■

Theorem 4. Suppose that the sequence {x_m} is generated by (2), then the search direction in (3) with conjugate gradient (14) and with (29) or (33) satisfy the descent condition, i.e. d m + 1 T g m + 1 ⩽ 0 with exact and inexact line search.

Proof. From Equations (14) we have,

d m + 1 T = - Hg m + 1 + g m + 1 T Hg m + 1 d m T y m d m(48) where, H = H m + 1 NMSR 1 or H = H m + 1 NMDFP

where they were proved in the Theorems 2 and 3 that they are positively defined.

Multiplying both sides of Equation (48) by g_m+1, to obtain

g m + 1 T d m + 1 = - g m + 1 T Hg m + 1 + g m + 1 T Hg m + 1 d m T y m g m + 1 T d m .(49)

Here, we will take two cases, the first case is exact line search, that is mean g m + 1 T d m = 0 , then, we get d m + 1 T g m + 1 = - g m + 1 T Hg m + 1 < 0 .

The second case is inexact line search, that is mean g m + 1 T d m ≠ 0 , here, we will prove by mathematical induction, d 0 T g 0 = - g 0 T Hg 0 ⩽ 0 , where d₀ = - Hg₀, and we assume that it is true for case m that means d m T g m ⩽ 0 . To prove case m + 1, by the inequality d m T g m + 1 < d m T y m

Equation (49) becomes, g m + 1 T d m + 1 < - g m + 1 T Hg m + 1 + g m + 1 T Hg m + 1 d m T y m d m T y m < 0 then,

g m + 1 T d m + 1 < 0 . ■

In this section, we focus on testing the implementation of the new algorithms. We compare New1, which is the new limited memory preconditioned conjugate gradient method (LMPCG), where it contains (NMSR1/DY) with the standard LMPCG (SR1/DY), and New2, which is the new LMPCG, where it contains (NMDFP/HS) with the standard LMPCG (DFP/HS). The comparative tests contain nonlinear unconstrained problems with different dimensions n = 50, 100 and 500. Different numbers were used M = 3, 4, 6, 7 and 9 as a memory index. We considered ɛ = 10^-5 and stopping criteria is set to ∥g_m+1 ∥ < 10^-5. Tables (1) and (2) of the findings provide specific references to the number of iterations NOI and the number of functions NOF. The results are in the two tables below confirm that the algorithms New1 and New2 are superior to standard L-PCG methods with respect to NOI and NOF. We adopt the performance profiles by Dolan and More [16] to compare the performance among different methods. Figures 1 and 2 shows the performance profiles of the New1 based on NOI and NOF respectively, and we see that the New1 is more performant than the standard LMPCG(SR1/DY). While the Figs. 3 and 4 shows the performance profiles of the New2 based on NOI and NOF respectively, and we see that the New2 is more performant than the standard LMPCG(DFP/HS).