# A New Hybrid Algorithm for Convex Nonlinear Unconstrained Optimization

Authors: Eman T. Hamed; Huda I. Ahmed; Abbas Y. Al-Bayati
Journal: Journal of Applied Mathematics
 (2019)

---

## Abstract

In this study, we tend to propose a replacement hybrid algorithmic rule which mixes the search directions like Steepest Descent (SD) and Quasi-Newton (QN). First, we tend to develop a replacement search direction for combined conjugate gradient (CG) and QN strategies. Second, we tend to depict a replacement positive CG methodology that possesses the adequate descent property with sturdy Wolfe line search. We tend to conjointly prove a replacement theorem to make sure global convergence property is underneath some given conditions. Our numerical results show that the new algorithmic rule is powerful as compared to different standard high scale CG strategies.


---

## Body

## 1. Introduction

The nonlinear CG technique could be a helpful procedure to search out the minimum value of any nonlinear function through exploitation unconstrained nonlinear optimization strategies.Let us contemplate the subsequent unconstrained minimization problem:(1)minimizex∈Rnfx where f:Rn→R is a real-valued smooth function. The repetitious formula is given as(2)xk+1=xk+αkdkwhere αk is associate optimum step-size computed by any line search procedure [1]. The search direction dk is defined as(3)dk+1=-gk+1fork=0-gk+1+βkdkfork≥1and gk=g(xk) denotes ∇f(xk), while βk is a positive scalar.Well-known established instances ofβk square measure are from Hestenes-Stiefel, Fletcher-Reeves, Polak-Ribière, Liu-Storey, Dai-Yuan, and Dai-Liao (see [2, 3, 3, 4, 4–7], respectively), within the already-existing convergence analysis and implementation of the CG methodology, the weak Wolfe conditions square measure [8]:(4)＇＇fxk+αkdk-fxk≤δαk∇fxkTd＇＇(5)＇＇∇fxk+αkdkTdk≥σ∇fxkTdk＇＇If we choose 0<δ<σ<1, also the strong Wolfe conditions [8] consist of (4) and (6)＇＇gxk+αkdkTdk≤-σgkTdk＇＇Now, this allows us to review Ibrahim et al. work [9] that could be a work that considers unconstrained minimization problems. Ibrahim et al. recommend a search direction that is outlined as(7)dk=-Bk-1gk+λk+1dk-1and Bk is the BFGS updating matrix if step-size is(8)λk=ηgkTgkgkTdk-1The scalar η∈[0,1] is chosen to ensure conjugacy.Also, another addition is regarded as an equivalent unconstrained minimization problem. Ibrahim et al. [10] recommend another search direction outlined as(9)dk=-Bk-1gk+ρgk,Bk-ρIdk=-gkMatrix I is the identity and ρ<0.In addition, Ibrahim et al. [11] propose another search direction that is outlined as(10)dk=-Bk-1gkk=0-Bk-1gk+η-gk+βkdk-1k≥1The positive scalar η and βk are the Hestenes-Stiefel parameters.


## 2. A New Proposed Search Direction

In this section, we advise a replacement search direction as deduced from Ibrahim et al. [9–11]. The new search direction is outlined as(11)dk+1=-λkgk+1+Hk+1gk+1whereas Hk+1 (the approximation matrix of BFGS updating matrix) denotes approximations of Hessian matrix G, and λk could be a positive constant. In order to drive the value of λk, we have a tendency to multiply either side of (11) by ykT to induce(12)ykTdk+1=-λkykTgk+1+ykTHk+1gk+1Since ykTHk+1=skT and ykTdk+1=-tskTgk+1 (Perry condition [12]), then(13)-tskTgk+1=-λkykTgk+1+skTgk+1λk=1+tskTgk+1ykTgk+1In order to see value of ρk, we tend to additionally multiply either side of (11) to induce(14)dk+1=-λkgk+1+ρkHk+1gk+1(15)ykTdk+1=-λkykTgk+1+ykTHk+1gk+1(16)ρk=λkykTgk+1-tskTgk+1skTgk+1As a result of processes of multiplication shown in (13) and (16), we tend to reach the following search directions in (17a), (17b), and (17c). The subsequent new search directions are our new projected algorithmic program:(17a)dk+1=-λkgk+1+ρkHk+1gk+1(17b)λk=1+tskTgk+1ykTgk+1(17c)ρk=λkykTgk+1-tskTgk+1skTgk+1In the following step, we have a tendency to assume that each search direction got to satisfy the subsequent descent condition (gkTdk<0, for all k). Also, there should exist a constant c>0 in order to get (18)＇＇dkTgk≤-c1gk2＇＇For all k≥0, the new direction that is outlined in (18) ought to satisfy the sufficient descent condition. The enough descent conditions are going to be used later to prove our new theorem (see Section 2.2). So to prove our new theorem, we have a tendency to necessarily use the subsequent given assumptions (see Section 2.1).


### 2.1. Assumptions in [9, 11, 13]

(A1)
f : R n → R is twice continuously differentiable. (A2)
f is uniformly convex; that is, m and M are positive constants, such that(19a)＇＇mz2≤zTGxz≤Mz2＇＇ for allx,z∈Rn, and G is the Hessian matrix of f. (A3)
The matrix G is Lipschitz continuous at the pointx∗; that is, there exists the positive constant L satisfying(19b)＇＇gx-gx∗≤Lx-x∗＇＇ for all x in a neighborhood ofx∗.


### 2.2. A New Theorem for Proving Sufficient Descent Property

To prove that our new projected algorithm defined in (17a), (17b), and (17c) satisfies sufficiently descent condition, we tend to suppose that assumptions in (Section 2.1) square measure are true. Additionally, the sequence Hk is bounded. Then, sufficient descent condition (18) is true for all k≥0.Proof.
When taking (17a), (17b), and (17c) and achieving the descent condition, we can see the following:(20)gk+1Tdk+1=-λkgk+1Tgk+1+ρkgk+1THk+1gk+1≤-λkgk+12+δkgk+12≤cgk+12We get value c=-(λk-δk), which is bounded away from zero. Therefore (18) is true.


### 2.3. Lemma in [10, 14]

Suppose that assumptions in Section2.1 are true. Then, the step-size αk which is determined by (2) satisfies (21)＇＇fk+1-fk≤-c3gkTdk2dk2＇＇when c3 is a positive constant.


### 2.4. New Theorem for Proving Global Convergence Property

Having demonstrated the important and necessary properties of regression algorithms, we now come to the proof of the necessary property to be present in all numerical optimization algorithms. Let us demonstrate the new algorithm defined in (17a), (17b), and (17c). To achieve a global convergence property, assume that the theory in Section 2.2 and the assumptions in Section 2.1 are correct. Then(22)＇＇limk→∞gk2=0＇＇Proof.
By linking the theory in Section2.2 and lemma in Section 2.3 we give the following result:(23)∑k=0∞gk4dk2<∞Hence, from our new theorem in Section 2.2, we can define that dk≤-cgk, and we can therefore simplify (23) as ∑k=0∞gk2<∞. Thus, the proof is established.


## 2.1. Assumptions in [9, 11, 13]

(A1)
f : R n → R is twice continuously differentiable. (A2)
f is uniformly convex; that is, m and M are positive constants, such that(19a)＇＇mz2≤zTGxz≤Mz2＇＇ for allx,z∈Rn, and G is the Hessian matrix of f. (A3)
The matrix G is Lipschitz continuous at the pointx∗; that is, there exists the positive constant L satisfying(19b)＇＇gx-gx∗≤Lx-x∗＇＇ for all x in a neighborhood ofx∗.


## 2.2. A New Theorem for Proving Sufficient Descent Property

To prove that our new projected algorithm defined in (17a), (17b), and (17c) satisfies sufficiently descent condition, we tend to suppose that assumptions in (Section 2.1) square measure are true. Additionally, the sequence Hk is bounded. Then, sufficient descent condition (18) is true for all k≥0.Proof.
When taking (17a), (17b), and (17c) and achieving the descent condition, we can see the following:(20)gk+1Tdk+1=-λkgk+1Tgk+1+ρkgk+1THk+1gk+1≤-λkgk+12+δkgk+12≤cgk+12We get value c=-(λk-δk), which is bounded away from zero. Therefore (18) is true.


## 2.3. Lemma in [10, 14]

Suppose that assumptions in Section2.1 are true. Then, the step-size αk which is determined by (2) satisfies (21)＇＇fk+1-fk≤-c3gkTdk2dk2＇＇when c3 is a positive constant.


## 2.4. New Theorem for Proving Global Convergence Property

Having demonstrated the important and necessary properties of regression algorithms, we now come to the proof of the necessary property to be present in all numerical optimization algorithms. Let us demonstrate the new algorithm defined in (17a), (17b), and (17c). To achieve a global convergence property, assume that the theory in Section 2.2 and the assumptions in Section 2.1 are correct. Then(22)＇＇limk→∞gk2=0＇＇Proof.
By linking the theory in Section2.2 and lemma in Section 2.3 we give the following result:(23)∑k=0∞gk4dk2<∞Hence, from our new theorem in Section 2.2, we can define that dk≤-cgk, and we can therefore simplify (23) as ∑k=0∞gk2<∞. Thus, the proof is established.


## 3. A New Form for the Parameterβk in Conjugate Gradient Method

To obtain an updated version of the conjugate gradient method associated with a new parameterβk, we compare the standard CG-method specified in (3) with the proposed new algorithm specified in (17a), (17b), and (17c):(24)-λkgk+1+ρkHk+1gk+1=-gk+1+βkskMultiplying both sides of (24) by ykT we get(25)-λkykTgk+1+ρkykTHk+1gk+1=-ykTgk+1+βkykTskOr(26)Hk+1=-ykgk+1T+βkykskT+λkykgk+1TρkykTgk+1·Iknowing that I is the identity matrix. Moreover, (27)skTHk+1sk=-skTykgk+1Tsk+βkskTykskTsk+λkskTykgk+1TskρkykTgk+1Then, the new βk is (28)βkhh=skTHk+1skρkykTgk+1+skTykgk+1Tsk-λkskTykgk+1Tsksk2skTykand yk=gk+1-gk,sk=xk+1-xk. It should be noted that when using exact line searches assuming that ρk=1 and the matrix Hk+1 is the identity matrix, the new standard will be reduced to HS. This condition must also be met, with skTHk+1sk>0 (positive constant), and since(29a)skTHk+1sk=ψk>0after these conditions we know the new parameter βkhh is(29b)βkhh=ψkρkykTgk+1+skTykgk+1Tsk-λkskTykgk+1Tsksk2skTykIn conjunction with both parameters(29c)λk=1+tskTgk+1ykTgk+1(29d)ρk=λkykTgk+1-tskTgk+1skTgk+1and the search direction is defined as(29e)dk+1=-gk+1+ψkρkykTgk+1+skTykgk+1Tsk-λkskTykgk+1Tsksk2skTyksk


### 3.1. Outlines of the New Proposed CG-Algorithm in (29a), (29b), (29c), (29d), and (29e)

By assumingx∈Rn,∈≥0, and by setting the iteration k=1, we get the following steps.Step 1.
Setdk=-gk, if gk<∈, then stop.Step 2.
Computeαk by strong Wolfe line search conditions in (4) and in (6).Step 3.
Generatedk+1 by implementing (29a), (29b), (29c), (29d), and (29e).Step 4.
Ifgk+1Tgk≥0.2gk+12 [15] is satisfied, then go to Step 1; if not, then continue.


### 3.2. Assumptions for Proving the Convergence Analysis Property of the New Algorithm in (29a), (29b), (29c), (29d), and (29e)

Let us suppose the following.(i)
The level set(30)＇＇S=x∈Rn:fx≤fx0＇＇isbonded.
(ii)
The condition∇f(x)≤γ is satisfied where γ>0; also since f is a uniformly convex function on S, then there exists a constant μ>0, such that(31)＇＇∇fx-∇fyTx-y≥μx-y2,∀x,y∈S＇＇From both (19a), (19b), and (31), we can get the following: (32)＇＇μsk2≤ykTsk≤Lsk2＇＇


### 3.3. New Theorem for Proving Sufficiently Descent Directions of the New Algorithm in (29a), (29b), (29c), (29d), and (29e)

If we have a tendency to assume that (A3) in Section2.1 is true and if we assume that conditions (i) and (ii), outlined in (30) and in (31), respectively, are true, then the new proposed search direction dk+1 defined in (29e) satisfies the sufficient descent condition.Proof.
By using the mathematical induction we demonstrate this new theorem; for initial direction (k=1) we have(33)d1=-g1→d1Tg1=-g12≤0which satisfies (18).
We suppose thatdiTgi≤-cgi2≤0,∀i=1,2,…,k.
And if we multiply both sides of (29a) by gk+1/gk+12, then we can get(34)dk+1Tgk+1+gk+12gk+12=ψkρkykTgk+1+skTykgk+1Tsk-λkskTykgk+1Tsksk2skTykskTgk+1gk+12since skTgk+1≤skTyk+1, since ykTgk+1≤yk·gk+1:(35)dk+1Tgk+1+gk+12gk+12≤ψkρkyk·gk+1+skTykskTyk-λkskTykskTyksk2skTykskTykgk+12≤ψkρkyk·gk+1+skTyk2-λkskTyk2sk2skTykskTykgk+12≤ψkρkyk·gk+1+1-λkskTyk2sk2gk+12and since 0<λ<1→(1-λ)>0(36)letc1=ψkρkyk·gk+1+1-λkskTyk2sk2gk+12>0dk+1Tgk+1≤-1-c1gk+12.The above equations ensure that condition (18) is satisfied. Hence, the proof is complete.


### 3.4. Lemma in [1, 16]

By assuming that assumptions in Section2.1 are true, by supposing that any CG-method with search direction dk+1 could be a descent direction provided that the step-size αk is obtained by the strong Wolfe line search conditions, and if(37)＇＇∑k≥11dk+12=∞＇＇then(38)＇＇limk→∞infgk=0＇＇


### 3.5. A New Theorem for Proving the Global Convergence Property of the New Algorithm in (29a), (29b), (29c), (29d), and (29e)

If we suppose that assumptions (i) and (ii) in (30) and in (31), respectively, are true and if we have a tendency to assume that (A3) in Section 2.1 is additionally true, then the search directions dk+1 outlined in (29e) are descent provided that the step-size αk is computed using (4) and (6), and then(39)limk→∞gk=0.Proof.
since(40)βkhh=ψkρkykTgk+1+skTykgk+1Tsk-λkskTykgk+1Tsksk2skTykβkhh≤ψkρkykTgk+1sk2skTyk+skTykgk+1Tsksk2skTyk+λkskTykgk+1Tsksk2skTykand since skTgk+1≤skTyk+1 and ykTgk+1≤yk·gk+1,(41)βkhh≤ψkρkykgk+1sk2skTyk+skTyk2sk2skTyk+λkskTyk2sk2skTyk≤ψkρkykgk+1sk2skTyk+skTyksk2+λkskTyksk2then from (A3) in part (Section 2.1), from condition (ii) in (31), and from (28) we get(42)βkhh≤ψkρkLskγsk2μsk2+Lsk2sk2+λkLsk2sk2≤ψkρkLγskμsk2+L+Lλk=c2>0dk+1≤gk+1+c2sk=D∑k≥11dk+12≥1D∑k≥11=∞.i.e.limk→∞gk=0


## 3.1. Outlines of the New Proposed CG-Algorithm in (29a), (29b), (29c), (29d), and (29e)

By assumingx∈Rn,∈≥0, and by setting the iteration k=1, we get the following steps.Step 1.
Setdk=-gk, if gk<∈, then stop.Step 2.
Computeαk by strong Wolfe line search conditions in (4) and in (6).Step 3.
Generatedk+1 by implementing (29a), (29b), (29c), (29d), and (29e).Step 4.
Ifgk+1Tgk≥0.2gk+12 [15] is satisfied, then go to Step 1; if not, then continue.


## 3.2. Assumptions for Proving the Convergence Analysis Property of the New Algorithm in (29a), (29b), (29c), (29d), and (29e)

Let us suppose the following.(i)
The level set(30)＇＇S=x∈Rn:fx≤fx0＇＇isbonded.
(ii)
The condition∇f(x)≤γ is satisfied where γ>0; also since f is a uniformly convex function on S, then there exists a constant μ>0, such that(31)＇＇∇fx-∇fyTx-y≥μx-y2,∀x,y∈S＇＇From both (19a), (19b), and (31), we can get the following: (32)＇＇μsk2≤ykTsk≤Lsk2＇＇


## 3.3. New Theorem for Proving Sufficiently Descent Directions of the New Algorithm in (29a), (29b), (29c), (29d), and (29e)

If we have a tendency to assume that (A3) in Section2.1 is true and if we assume that conditions (i) and (ii), outlined in (30) and in (31), respectively, are true, then the new proposed search direction dk+1 defined in (29e) satisfies the sufficient descent condition.Proof.
By using the mathematical induction we demonstrate this new theorem; for initial direction (k=1) we have(33)d1=-g1→d1Tg1=-g12≤0which satisfies (18).
We suppose thatdiTgi≤-cgi2≤0,∀i=1,2,…,k.
And if we multiply both sides of (29a) by gk+1/gk+12, then we can get(34)dk+1Tgk+1+gk+12gk+12=ψkρkykTgk+1+skTykgk+1Tsk-λkskTykgk+1Tsksk2skTykskTgk+1gk+12since skTgk+1≤skTyk+1, since ykTgk+1≤yk·gk+1:(35)dk+1Tgk+1+gk+12gk+12≤ψkρkyk·gk+1+skTykskTyk-λkskTykskTyksk2skTykskTykgk+12≤ψkρkyk·gk+1+skTyk2-λkskTyk2sk2skTykskTykgk+12≤ψkρkyk·gk+1+1-λkskTyk2sk2gk+12and since 0<λ<1→(1-λ)>0(36)letc1=ψkρkyk·gk+1+1-λkskTyk2sk2gk+12>0dk+1Tgk+1≤-1-c1gk+12.The above equations ensure that condition (18) is satisfied. Hence, the proof is complete.


## 3.4. Lemma in [1, 16]

By assuming that assumptions in Section2.1 are true, by supposing that any CG-method with search direction dk+1 could be a descent direction provided that the step-size αk is obtained by the strong Wolfe line search conditions, and if(37)＇＇∑k≥11dk+12=∞＇＇then(38)＇＇limk→∞infgk=0＇＇


## 3.5. A New Theorem for Proving the Global Convergence Property of the New Algorithm in (29a), (29b), (29c), (29d), and (29e)

If we suppose that assumptions (i) and (ii) in (30) and in (31), respectively, are true and if we have a tendency to assume that (A3) in Section 2.1 is additionally true, then the search directions dk+1 outlined in (29e) are descent provided that the step-size αk is computed using (4) and (6), and then(39)limk→∞gk=0.Proof.
since(40)βkhh=ψkρkykTgk+1+skTykgk+1Tsk-λkskTykgk+1Tsksk2skTykβkhh≤ψkρkykTgk+1sk2skTyk+skTykgk+1Tsksk2skTyk+λkskTykgk+1Tsksk2skTykand since skTgk+1≤skTyk+1 and ykTgk+1≤yk·gk+1,(41)βkhh≤ψkρkykgk+1sk2skTyk+skTyk2sk2skTyk+λkskTyk2sk2skTyk≤ψkρkykgk+1sk2skTyk+skTyksk2+λkskTyksk2then from (A3) in part (Section 2.1), from condition (ii) in (31), and from (28) we get(42)βkhh≤ψkρkLskγsk2μsk2+Lsk2sk2+λkLsk2sk2≤ψkρkLγskμsk2+L+Lλk=c2>0dk+1≤gk+1+c2sk=D∑k≥11dk+12≥1D∑k≥11=∞.i.e.limk→∞gk=0


## 4. Numerical Results and Comparisons

In this work, we have a tendency to compare our new proposed CG-method with some normal classical CG strategies like Hestenes-Stiefel [HS] and Dai-Yuan [DY] by exploitation of fifty unconstrained nonlinear cases; take a look at functions obtained from Andrei [17, 18]. As for the computer program, it was stopped when gk≤10-6. In addition, the term skTHk+1sk, which is defined in (29a), can be computed as skTHk+1sk=2(fk-fk+1)+2skTgk+1. Numerical results for new algorithm in (29a), (29b), (29c), (29d), and (29e) with λ=1 and ρ=0.1 are for the total of 50 test problems from the CUTE library. The Sigma plotting software was used to graph the data. We adopt the performance profiles given by Dolan and Moré [19]. Thus, new, HS, and DY strategies are compared in terms of NOI, CPU, and NOF in Figures 1–3. For each method, we plotted the fraction of problems that were solved correctly within a factor of the best time. In the figures, the uppermost curve is the method that solves the most problems within a factor t of the best time. In Figures 1–3, the new method outperforms the HS algorithm and DY method in terms of NOI, CPU, and NOF. If the solution had not converged after 800 seconds, the program was terminated. Generally, convergence was achieved within this time limit; functions for which the time limit was exceeded are denoted by “F” for fail-in.Figure 1
Performance profiles based on number of iterations.Figure 2
Performance profiles based on CPU time.Figure 3
Performance profiles based on function evaluation.


## 5. Conclusions

At the end of this work we were able to obtain a new direction of research defined in (29a), (29b), (29c), (29d), and (29e). This new trend is a hybrid trend that combines pedigree techniques with Quasi-Newton ones. Through the theories presented in the research, the new trend in (29a), (29b), (29c), (29d), and (29e) proved that it satisfies the requirement of sufficient proportions and ensures the property of global convergence. In addition, we have presented a new scalar (βk) which ensures the sufficient descent directions. Moreover, under some conditions, we have established that the new proposed algorithm is a globally convergent algorithm for uniformly convex functions under the strong Wolfe line search conditions. The numerical results show that when we choose the value of parameters λ in (13) and ρ in (16), we obtain best numerical results as compared to other similar numerical results.



---

*Source: 8728196-2019-04-01.xml*