# Hybrid Modification of Accelerated Double Direction Method

Authors: Milena J. Petrović; Predrag S. Stanimirović; Nataša Kontrec; Julija Mladenović
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We present a hybridization of the accelerated gradient method with two vector directions. This hybridization is based on the usage of a chosen three-term hybrid model. Derived hybrid accelerated double direction model keeps preferable properties of both included methods. Convergence analysis demonstrates at least linear convergence of the proposed iterative scheme on the set of uniformly convex and strictly convex quadratic functions. The results of numerical experiments confirm better performance profile in favor of derived hybrid accelerated double direction model when compared to its forerunners.


---

## Body

## 1. Introduction

The main goal herein is to derive an efficient optimization method for minimization of an objective functionf
:
R
n
→
R. Therewith, we assume the function f is uniformly convex and twice continuously differentiable. Furthermore, for the gradient and the Hessian of the function f at the k-th iterative point we use the next notation:(1)
g
k
x
=
▽
f
x
k
,
G
k
x
=
▽
2
f
x
k
. The general form of the iterations for finding the extreme values of the objective function f is given by the next expression:(2)
x
k
+
1
=
x
k
+
t
k
d
k
,where x
k is the current, x
k
+
1 is the next iterative point, t
k is iterative step length value, and d
k is an iterative vector direction which leads us to the solution of the problem. Certainly, t
k and d
k are the most important issues of an optimization model (2) and they generate the efficiency of a relevant method. For that reason, the way of defining these two crucial elements is of great importance for each minimization scheme.In one of the first algorithms for solving unconstrained optimization problems, denoted as the steepest descent gradient method which is exposed by Cauchy, the iteration is defined as(3)
x
k
+
1
=
x
k
-
t
k
g
k
,and here, the descent direction is simply presented as the negative gradient vector, while iterative step size value is calculated by the exact line search formula:(4)
t
k
=
arg
⁡
min
t
>
0
⁡
f
x
k
+
t
d
k
.Furthermore, in the general Newton method(5)
x
k
+
1
=
x
k
-
G
k
-
1
g
k
t
k
,the vector direction is calculated as the product of the inverse Hessian and the gradient of the objective function. Defining the vector direction in this way guarantees fast convergence properties, but still, practical computing of the function Hessian and its inverse can be difficult. And so, many modified Newton, Newton-conjugate, and quasi Newton schemes were developed in which the calculation of the Hessian and its inverse is, somehow, avoided.In the quasi-Newton methods the Hessian of the goal function or its inverse is approximated by the adequately defined matrix. Using this type of methods we generally reduce the time of computations since we avoid the complicated calculations in deriving the Hessian of the objective function. Nevertheless, the methods of quasi Newton type preserve good properties of the Newton method. For these reasons, in this paper, we propose the method of quasi Newton type where the value of the iterative step size parametert
k is obtained by the inexact Backtracking line search procedure.In the second section we give an overview of some accelerated gradient methods and hybrid iterations. We elaborate the deriving of the hybrid accelerated double direction method and restate the algorithm in the third section of this paper. In the fourth section we give a convergence analysis regarding the proposed iteration. Numerical experiments and comparison are presented in the last section of this paper.


## 2. Preliminaries: Accelerated Gradient Methods and Hybrid Iterations

The authors in [1] rightfully detected a class of accelerated gradient descent methods, defined by the general iterative scheme(6)
x
k
+
1
=
x
k
-
γ
k
-
1
t
k
g
k
.In the previous expression, γ
k presents an iterative acceleration parameter which improves performance of the relevant method. A common way to determine this parameter is through the features of the second-order Taylor’s series taken on appropriate scheme (6). Acceleration parameters that were computed in such way are applied in the methods described in [1–5]. According to the iteration form (6), we can conclude that the accelerated gradient methods are of the quasi-Newton type in which the approximation of the Hessian, i.e., its inverse, is obtained by the scalar matrix γ
k
I, where I is appropriate identity matrix and γ
k
=
γ
(
x
k
,
x
k
-
1
) is the matching acceleration parameter. Here are several expressions for defining the acceleration parameters of some accelerated gradient schemes: (7)
γ
k
+
1
S
M
=
2
γ
k
γ
k
f
x
k
+
1
-
f
x
k
+
t
k
g
k
2
t
k
2
g
k
2
.(SM method [1])(8)
γ
k
+
1
A
D
D
=
2
f
x
k
+
1
-
f
x
k
-
α
k
g
k
T
α
k
d
k
-
γ
k
-
1
g
k
α
k
d
k
-
γ
k
-
1
g
k
T
α
k
d
k
-
γ
k
-
1
g
k
, (ADD method [4])(9)
γ
k
+
1
A
D
S
S
=
2
f
x
k
+
1
-
f
x
k
+
α
k
γ
k
-
1
+
β
k
g
k
2
α
k
γ
k
-
1
+
β
k
2
g
k
2
,(ADSS method [2])(10)
γ
k
+
1
T
A
D
S
S
=
2
f
x
k
+
1
-
f
x
k
+
ψ
k
g
k
2
ψ
k
2
g
k
2
,(TADSS method [5])(11)
γ
k
+
1
H
S
M
=
2
γ
k
γ
k
f
x
k
+
1
-
f
x
k
+
α
k
+
1
t
k
g
k
2
α
k
+
1
2
t
k
2
g
k
2
,(HSM method [3]).An interesting concept of merging iterations through the hybrid expression was suggested in some research articles (see [6–8]). Some of representations are given by the next set of iterations:(12)
u
1
=
u
∈
C
,
u
k
+
1
=
T
u
k
,
k
∈
N
,
(13)
v
1
=
v
∈
C
,
v
k
+
1
=
1
-
α
k
v
k
+
α
k
T
v
k
,
k
∈
N
,
(14)
z
1
=
z
∈
C
,
z
k
+
1
=
1
-
α
k
z
k
+
α
k
T
y
k
,
y
k
=
1
-
β
k
z
k
+
β
k
T
z
k
,
k
∈
N
,where T
:
C
→
C is a mapping defined on nonempty convex subset C of a normed space E, v
k
,
z
k, and y
k present the sequences defined by proposed iterations, and {
α
k
}
,
{
β
k
}
∈
(
0,1
).In [9] it was proved that the hybrid method(15)
x
1
=
x
∈
R
,
x
k
+
1
=
T
y
k
,
y
k
=
1
-
α
k
x
k
+
α
k
T
x
k
,
k
∈
N
,proposed by Picard, Mann, and Ishikawa, upgrades the hybrid models mentioned above. The authors of [3] used the advantages of the hybrid model (15) and derived a hybrid version of the accelerated gradient SM method from [1], termed the HSM method and defined by(16)
x
k
+
1
=
x
k
-
α
k
+
1
t
k
γ
k
-
1
g
k
.Numerical tests from [3] confirmed that the hybrid model (16) upgrades its forerunner SM iterative rule.


## 3. HADD Algorithm

We are motivated by the confirmed advantages which were approved in [3] when the scheme (15) was applied on the SM method. As a result, the hybrid SM model (called HSM) was defined and tested in [3]. Herein, we apply the same hybridization strategy to the accelerated double direction method (ADD method, shortly), introduced in [4]. Derived scheme will be based on the hybrid scheme (15) and with that it keeps the accelerated features of the ADD iterations.In order to complete the presentation, we start from the ADD iteration:(17)
x
k
+
1
=
x
k
-
t
k
γ
k
-
1
g
k
+
t
k
2
d
k
,where t
k is appropriately defined step size, the first direction vector is given by -
γ
k
-
1
g
k
=
-
γ
k
A
D
D
-
1
g
k, and the second one, d
k, is determined based on the next procedureSecond direction. That procedure was introduced in [4], which was derived as a practical appearance of the more general procedure considered in [10]. The procedureSecond direction is restated in Algorithm 1.Algorithm 1:Procedure Second direction
(calculation of the second direction vector
d
k
).
Require: Objective function f
(
x
), gradient g
k and stepsize t
k.
1: Compute
d
k
(
t
)
=
d
k
∗
i
f
k
≤
m
-
1
∑
i
=
2
m
‍
t
i
-
1
d
k
-
i
+
1
∗
i
f
k
≥
m
,
wheret
=
t
k is the step size, d
k
∗ is the solution of the problem m
i
n
x
∈
R
Φ
k
(
d
), and
Φ
k
(
d
)
=
∇
f
x
k
T
d
+
1
2
γ
k
+
1
I
=
g
k
T
d
+
1
2
γ
k
+
1
I
.
2: Returnd
k
=
d
k
∗.Remark 1.
For further investigation within this topic, the second directiond
k in the ADD iteration can be defined differently. For example, in [11] the authors proposed directional k-step Newton methods for solving a single nonlinear equation in n-variables. Accordingly, they established the semi-local convergence analysis for these models, based on two different approaches. The first one is based on recurrent relations, while the other, more preferable, is established using recurrent functions. Using one (or both) approaches from [11] in determining the second direction d
k in the ADD method as well as in its hybrid version can be an interesting topic in further research.Applying the hybrid scheme (15) on the iterative rule (17), we get the hybrid iterative scheme(18)
x
1
=
x
∈
R
,
x
k
+
1
=
T
y
k
=
y
k
-
t
k
γ
k
-
1
g
k
+
t
k
2
d
k
,
y
k
=
1
-
α
k
x
k
+
α
k
T
x
k
=
1
-
α
k
x
k
+
α
k
x
k
-
t
k
γ
k
-
1
g
k
+
t
k
2
d
k
=
x
k
-
α
k
t
k
γ
k
-
1
g
k
+
α
k
t
k
2
d
k
,
k
∈
N
.After replacing the third expression from the set of equations (18) into the second one, the next iterative rule follows:(19)
x
k
+
1
=
x
k
-
α
k
+
1
t
k
γ
k
-
1
g
k
+
α
k
+
1
t
k
2
d
k
.To simplify further calculation, we will use a constant value for the parameterα
k
∈
(
0,1
) in (19), just like the authors did in [1, 9]. So, in (19), instead of α
k
+
1
∈
(
1,2
) we simply take α
∈
(
1,2
). Now we can restate a hybrid ADD method, or the HADD iterative scheme, as follows:(20)
x
k
+
1
=
x
k
-
α
t
k
γ
k
-
1
g
k
+
α
t
k
2
d
k
,
α
∈
1,2
.Yet, we need to determine the iterative value of the accelerated parameterγ
k
=
γ
k
H
A
D
D
. As we mentioned previously, this parameter can be appropriately defined using Taylor’s expansion of the proposed iteration (20) in two successive iterative points:(21)
f
x
k
+
1
≈
f
x
k
+
g
k
T
α
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
+
1
2
α
2
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
T
∇
2
f
ξ
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
.The parameter ξ in the previous expansion fulfills the condition(22)
ξ
∈
x
k
,
x
k
+
1
,
ξ
=
x
k
+
κ
x
k
+
1
-
x
k
=
x
k
+
κ
α
t
k
2
d
k
-
α
t
k
γ
k
-
1
g
k
,
0
≤
κ
≤
1
. In the next relation we substitute the value ▽
2
f
(
ξ
) from (21) by the scalar matrix γ
k
+
1
I, which leads to(23)
f
x
k
+
1
=
f
x
k
+
g
k
T
α
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
+
1
2
α
2
γ
k
+
1
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
T
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
.From (23), it is possible to derive the approximation factor γ
k
+
1
=
γ
k
+
1
H
A
D
D of the HADD scheme:(24)
γ
k
+
1
H
A
D
D
=
γ
k
+
1
=
2
f
x
k
+
1
-
f
x
k
-
α
g
k
T
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
α
2
t
k
2
t
k
d
k
-
γ
k
-
1
g
k
T
t
k
d
k
-
γ
k
-
1
g
k
.With the aim of preserving the Second-Order Necessary Condition and Second-Order Sufficient Condition, we assume positivity of the acceleration parameter:γ
k
+
1
>
0
. In practical computation, it is possible that (24) generates negative value for γ
k
+
1
. We resolve this situation by taking γ
k
+
1
=
1 in such cases. As a consequence, then the first vector direction becomes the negative gradient vector -
g
k
. In this special case, the next iterative point of the iteration (20) becomes (25)
x
k
+
2
=
x
k
+
1
-
α
t
k
+
1
g
k
+
1
+
α
t
k
+
1
2
d
k
+
1
.In order to present the main HADD algorithm, we need two additional auxiliary procedures. The first one is previously displayed Algorithm1, by which we calculate the second vector direction, d
k. The second procedure is the Backtracking line search algorithm for calculating the iterative step size value.Algorithm3 describes the main algorithm, termed the HADD algorithm.Algorithm 2:The Backtracking line search procedure.
Require: Objective function f
(
x
), the direction d
k of the search at the point x
k, and numbers 0
<
σ
<
0.5 and β
∈
(
0,1
).
1:t
=
1.
2: Whilef
(
x
k
+
t
d
k
)
>
f
(
x
k
)
+
σ
t
g
k
T
d
k, take t
≔
t
β.
3: Returnt
k
=
t.Algorithm 3:HADD method.
Require:
0
<
ρ
<
1, 0
<
τ
<
1, x
0
∈
R
n and α
∈
(
1,2
).
1: Setk
=
0
. For given x
0, take γ
0
=
1 and calculate f
(
x
0
) and g
(
x
0
).
2: Ifg
k
<
ϵ, then return x
k, f
(
x
k
) and stop the algorithm, else continue by the next step.
3: Compute the iterative step length,t
k, by Algorithm 2.
4: Compute second vector direction,d
k, by the rule Second direction described in Algorithm 1.
5: Computex
k
+
1 using (20), then calculate f
(
x
k
+
1
) and g
k
+
1
.
6: Calculate the approximation parameterγ
k
+
1 using (24).
7: Ifγ
k
+
1
<
0 take γ
k
+
1
=
1.
8: Setk
≔
k
+
1 and go to Step 2.
9: Returnx
k
+
1 and f
(
x
k
+
1
)
.


## 4. Convergence of the HADD Method

The convergence properties of the established HADD iterative method are considered on the set of uniformly convex and strictly convex quadratic functions. In the case of uniformly convex functions the statements are the same as exposed in [1, 4]. For that reason, we just restate the following lemma, in which decreasing of the objective function in two successive points is estimated with respect to the HADD scheme. Thereupon, the upcoming theorem confirms linear convergence of our hybrid accelerated model.Lemma 2.
Suppose the functionf is twice continuously differentiable and uniformly convex on R
n. With that, let the sequence {
x
k
} be generated by Algorithm 3. Then the next estimation is true(26)
f
x
k
-
f
x
k
+
1
≥
μ
g
k
2
, where(27)
μ
=
σ
M
,
σ
1
-
σ
L
β
.Theorem 3.
For the twice continuously differentiable and uniformly convex functionf on R
n and the sequence {
x
k
} generated by Algorithm 3, the following holds:(28)
l
i
m
k
→
∞
g
k
=
0
. Therewith, the sequence {
x
k
} converges to the optimal solution at least linearly.We show now that the iteration (20) is convergent regarding the set of strictly convex quadratic functions(29)
f
x
=
1
2
x
T
A
x
-
b
T
x
.In (29), it is assumed that A is a real n
×
n symmetric positive definite matrix and that vector b
∈
R
n is given. The smallest and the largest eigenvalues of the matrix A, respectively, are denoted by λ
1 and λ
n.Lemma 4.
Letf be the strictly convex quadratic function defined by (29), where A
∈
R
n
×
n is a symmetric positive definite matrix. Let λ
1 and λ
n be the smallest and the largest eigenvalues of A. Then, the following inequalities are valid for the hybrid accelerated gradient model (20):(30)
λ
1
≤
γ
k
+
1
t
k
+
1
≤
4
λ
n
σ
,
k
∈
N
,Proof.
Let us calculate the difference in two successive iterative points of the goal function (29):(31)
f
x
k
+
1
-
f
x
k
=
1
2
x
k
+
1
T
A
x
k
+
1
-
b
T
x
k
+
1
-
1
2
x
k
T
A
x
k
+
b
T
x
k
.
Including the iteration (20) we continue computations: (32)
f
x
k
+
1
-
f
x
k
=
1
2
x
k
-
α
t
k
γ
k
-
1
g
k
+
α
t
k
2
d
k
T
A
x
k
-
α
t
k
γ
k
-
1
g
k
+
α
t
k
2
d
k
-
b
T
x
k
-
α
t
k
γ
k
-
1
g
k
+
α
t
k
2
d
k
-
1
2
x
k
T
A
x
k
+
b
T
x
k
=
1
2
x
k
T
A
x
k
-
1
2
α
t
k
γ
k
-
1
g
k
T
A
x
k
+
1
2
α
t
k
2
d
k
T
A
x
k
-
1
2
α
t
k
γ
k
-
1
g
k
T
A
x
k
+
1
2
α
2
t
k
2
γ
k
-
2
g
k
T
A
g
k
-
1
2
α
t
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
t
k
2
d
k
T
A
x
k
-
1
2
α
2
t
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
2
t
k
4
d
k
T
A
d
k
-
b
T
x
k
+
α
t
k
γ
k
-
1
b
T
g
k
-
α
t
k
2
b
T
d
k
-
1
2
x
k
T
A
x
k
+
b
T
x
k
.Applying the equality g
k
=
A
x
k
-
b and the symmetry property of A, we get (33)
f
x
k
+
1
-
f
x
k
=
-
α
t
k
γ
k
-
1
g
k
T
A
x
k
+
α
t
k
2
d
k
T
A
x
k
-
α
2
t
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
2
t
k
2
γ
k
-
2
g
k
T
A
g
k
+
1
2
α
2
t
k
4
d
k
T
A
d
k
+
α
t
k
γ
k
-
1
b
T
g
k
-
α
t
k
2
b
T
d
k
.
The right hand side of the previous expression can be further transformed as follows:(34)
f
x
k
+
1
-
f
x
k
=
α
t
k
γ
k
-
1
b
T
g
k
-
x
k
T
A
g
k
+
α
t
k
2
x
k
T
A
d
k
-
b
T
d
k
-
α
2
t
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
t
k
2
γ
k
-
2
g
k
T
A
g
k
+
1
2
α
2
t
k
4
d
k
T
A
d
k
=
α
t
k
g
k
T
t
k
d
k
-
γ
k
-
1
g
k
-
1
2
α
2
t
k
2
γ
k
-
1
g
k
T
A
t
k
d
k
-
γ
k
-
1
g
k
+
1
2
α
2
t
k
3
d
k
T
A
t
k
d
k
-
γ
k
-
1
g
k
=
α
t
k
g
k
T
-
1
2
α
2
t
k
2
γ
k
-
1
g
k
T
A
+
1
2
α
2
t
k
3
d
k
T
A
t
k
d
k
-
γ
k
-
1
g
k
.The replacement of f
(
x
k
+
1
)
-
f
(
x
k
) by the right hand side of (34) into (24) leads us to(35)
γ
k
+
1
=
2
α
t
k
g
k
T
-
1
/
2
α
2
t
k
2
γ
k
-
1
g
k
T
A
+
1
/
2
α
2
t
k
3
d
k
T
A
t
k
d
k
-
γ
k
-
1
g
k
-
α
t
k
g
k
T
t
k
d
k
-
γ
k
-
1
g
k
α
2
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
T
t
k
2
d
k
-
t
k
γ
k
-
1
g
k
.
After some calculations, we obtain(36)
γ
k
+
1
=
t
k
d
k
-
γ
k
-
1
g
k
T
A
t
k
d
k
-
γ
k
-
1
g
k
t
k
d
k
-
γ
k
-
1
g
k
T
t
k
d
k
-
γ
k
-
1
g
k
.Previous expression confirms that γ
k
+
1 is the Rayleigh quotient of the real symmetric matrix A at the vector t
k
d
k
-
γ
k
-
1
g
k, which leads us to the conclusion(37)
λ
1
≤
γ
k
+
1
≤
λ
n
,
k
∈
N
. The left hand side in inequalities (30) arrives from the fact 0
≤
t
k
+
1
≤
1. To prove the right hand side of (30), we use the estimation [[3], eq. (3.8)]:(38)
t
k
>
β
1
-
σ
γ
k
α
L
. Previous inequality implies(39)
γ
k
+
1
t
k
+
1
<
L
α
β
1
-
σ
.We can approximate the Lipschitz constant L by the largest eigenvalue λ
n and use the fact that α
≤
2
,
0
<
σ
<
0.5 and β
∈
(
σ
,
1
). Then (39) is restated to(40)
γ
k
+
1
t
k
+
1
<
L
α
β
1
-
σ
<
2
λ
n
σ
·
0.5
=
4
λ
n
σ
.Estimation of the Lipschitz constant L by the largest eigenvalue λ
n is certainly valid since the matrix A is symmetric and g
(
x
)
=
A
x
-
b
. From these two facts we conclude that(41)
g
x
-
g
y
=
A
x
-
A
y
=
A
x
-
y
≤
A
x
-
y
=
λ
n
x
-
y
,which completes the proof.Theorem 5.
Let the iterations (19) be applied on strictly convex quadratic function f given by the expression (29). Suppose that the condition(42)
λ
n
<
2
λ
1
αholds for the largest and the smallest eigenvalues of symmetric positive definite matrix A. Then, the following estimations are true:(43)
p
i
k
+
1
2
≤
δ
2
p
i
k
2
,
q
i
k
+
1
2
≤
λ
n
2
q
i
k
2
,where(44)
δ
=
max
⁡
1
-
σ
λ
1
2
λ
n
,
λ
n
λ
1
-
1and p
i
k
,
q
i
k
∈
R
,
k
,
i
,
n
∈
N
. Therewith(45)
l
i
m
k
→
∞
g
k
=
0
.Proof.
Let us consider the orthonormal system of eigenvectors{
v
1
,
v
2
,
…
,
v
n
} of the matrix A. Thereon, we construct the sequence of values {
x
k
} by applying Algorithm 3 on strictly convex quadratic function f defined by (29). Then, for some k
∈
N and for some constants p
1
k
,
p
2
k
,
…
,
p
n
k
,
q
1
k
,
q
2
k
,
…
,
q
n
k
∈
R it follows that(46)
g
k
=
A
x
k
-
b
=
∑
i
=
1
n
p
i
k
v
i
,
d
k
=
∑
i
=
1
n
q
i
k
v
i
.
Applying (20), further we conclude that(47)
g
k
+
1
=
A
x
k
-
α
t
k
γ
k
-
1
g
k
+
α
t
k
2
d
k
-
b
=
I
-
α
t
k
γ
k
-
1
A
g
k
+
α
t
k
2
A
d
k
.Having in mind the representation (46), one can verify(48)
g
k
+
1
=
∑
i
=
1
n
p
i
k
+
1
v
i
=
∑
i
=
1
n
1
-
α
t
k
γ
k
-
1
λ
i
p
i
k
+
α
t
k
2
λ
i
q
i
k
v
i
=
∑
i
=
1
n
1
-
α
t
k
γ
k
-
1
λ
i
p
i
k
v
i
+
α
t
k
2
∑
i
=
1
n
λ
i
q
i
k
v
i
. To prove (49)
p
i
k
+
1
2
≤
δ
2
p
i
k
2
,
q
i
k
+
1
2
≤
λ
n
2
q
i
k
2
, i.e., the inequalities (43), we only need to verify that (50)
1
-
α
λ
i
γ
k
t
k
-
1
≤
δ since λ
i
≤
λ
n for all i
∈
{
1,2
,
…
,
n
}. There are two possibilities:
(1)α
λ
i
≤
t
k
-
1
γ
k
.
This case implies the next set of inequalities:(51)
1
>
α
λ
i
γ
k
t
k
-
1
=
α
λ
i
γ
k
·
t
k
≥
α
λ
1
γ
k
β
1
-
σ
γ
k
L
α
=
λ
1
β
1
-
σ
L
>
λ
1
σ
·
0.5
λ
n
=
λ
1
2
λ
n
σ
.
As a consequence, we can conclude that(52)
1
-
α
λ
i
γ
k
t
k
-
1
≤
1
-
λ
1
2
λ
n
σ
≤
δ
.
(2)α
λ
i
≥
t
k
-
1
γ
k
.
In this case, one can verify the following estimations:(53)
1
<
α
λ
i
γ
k
t
k
-
1
≤
α
λ
n
λ
1
⇒
1
-
α
λ
i
γ
k
t
k
-
1
≤
α
λ
n
λ
1
≤
δ
.The representation (46) and the fact that {
v
1
,
v
2
,
…
,
v
n
} is an orthonormal system of eigenvectors lead to the next conclusion(54)
g
k
2
=
∑
i
=
1
n
d
i
k
2
.Now, knowing that the parameter δ under condition λ
n
<
2
λ
1
/
α satisfies 0
<
δ
<
1, we confirm that the final statement is true.(55)
l
i
m
k
→
∞
g
k
=
0Remark 6.
The assumption (42) used in the previous theorem is required in order to prove that the HADD process is convergent for the strictly convex quadratics. Therewith, knowing that the hybrid parameter α
∈
(
1,2
) implies λ
n
/
λ
1
∈
(
1,2
) points to the conclusion that Theorem 5 is applicable to very few cases. However, this is not entirely so since we choose only one particular value α
∈
(
1,2
) for the practical computations. Regarding this matter, the authors in [3] numerically confirmed that the optimal value of the hybrid parameter α is the one close to the left limit of the interval (
1,2
), i.e., the value which is very close to 1. Therefore, we choose α
=
1.1 for numerical tests displayed in the next section. Choosing the similar values for hybrid parameter α, the condition (42) becomes very close to the condition λ
n
<
2
λ
1, used in [12], under which Q-linear convergence rate of the preconditioned BB method was established.


## 5. Computational Tests and Comparisons

The performance of the C+
+ implementation of derived HADD model is investigated on a set of 630 test unconstrained optimization problems picked from [13]. We conduct the testings on a Workstation Intel Celeron 1.6 GHz. The following stopping criteria are used: (56)
g
k
≤
1
0
-
6
,
f
x
k
+
1
-
f
x
k
1
+
f
x
k
≤
1
0
-
16
. The values of the Backtracking parameters are set up as follows: σ
=
0.000
1 and β
=
0.8.We compare the hybrid accelerated HADD method with its forerunner ADD scheme, as well as with the hybrid accelerated HSM method. The number of function evaluations is the performance profile measured in all tests. The dominance of the ADD method regarding the number of iterations among the other comparative models was confirmed in [4]. However, from that research we do not have any information about the behavior of the ADD method when the number of function evaluations is involved. With respect to this parameter, the HSM scheme upgrades the accelerated SM method as well as Nesterov’s line search algorithm; see [3]. For these reasons, our experimental goal is to numerically prove better performance feature of the HADD method, considering the number of function evaluations, when compared with the ADD and the HSM method.In Table1, we display the number of problems, out of 630, for which an algorithm achieved the minimum number of function evaluations. In the same table, we also display the total number of problems for which all three algorithms achieved an equal number of function evaluations. Based on the results displayed in this table, it is obvious that the HADD scheme convincingly outperforms the other two comparative models.Table 1
Comparison between the HADD, ADD, and HSM methods regarding the minimal number of function evaluations.
Comparative methods
HADD
ADD
HSM
=
Number of function evaluations
142
0
18
50For more clear visualization of the performance of the HADD algorithm versus the ADD and the HSM algorithms, we display in Figure1 the Dolan-Moré’s performance profile subject to the number of function evaluations metric. As we can see, the HADD scheme is more robust and therewith more efficient than the other two methods.Figure 1
Performance profile for the HADD, ADD, and HSM methods regarding the number of function evaluations metric.Obtained numerical results confirm that applied hybridization process is a good way to improve some important characteristics of chosen accelerated methods. Preferable outcomes of the HADD scheme, regarding analyzed characteristic, come from the properly chosen hybrid valueα, together with derived accelerated parameter γ
H
A
D
D. Good convergent properties of defined HADD process can be a reason for applying proposed hybridization on some other gradient and accelerated gradient models.


## 6. Conclusion

We present a hybrid accelerated double direction gradient method for solving unconstrained optimization problems. The HADD method is derived by applying good properties of the hybrid representation introduced in [3] in conjunction with the form of double direction optimization model with accelerated parameter presented in [4]. The convergence of defined optimization model is provided on the set of uniformly convex and strictly convex quadratic functions.The HADD scheme reserves preferable features of both forerunner methods. Therewith, according to conducted numerical experiments, it outperforms the ADD and HSM methods regarding the requested number of function evaluations. We evaluated the Dolan-Moré performance profiles of comparative methods and showed that the HADD iteration is the most efficient compared to the other two algorithms.



---

*Source: 1523267-2018-11-06.xml*