# Accelerated Double Direction Method for Solving Unconstrained Optimization Problems

Authors: Milena J. Petrović; Predrag S. Stanimirović
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

An iterative method for solving a minimization problem of unconstrained optimization is presented. This multistep curve search method uses the specific form of iteration with two direction parameters, the approximation of Hessian by appropriately constructed diagonal matrix, and the inexact line search procedure. It is proved that constructed numerical process is well defined under some assumptions. Considering certain conditions, the method is linearly convergent for uniformly convex and strictly convex quadratic functions. Numerical results arising from defined algorithms are also presented and analyzed.


---

## Body

## 1. Introduction

In this paper, we derive a first-order numerical method for solving the following nonlinear unconstrained optimization problem:(1)
min
⁡
f
(
x
)
,
x
∈
ℝ
n
,
where f
(
x
) is twice continuously differentiable function. The iteration of the form
(2)
x
k
+
1
=
x
k
+
α
k
s
k
+
α
k
2
d
k
is considered. Here, x
k
+
1 represents a new iterative point, x
k is the previous iteration, and α
k denotes the stepsize, while s
k and d
k generate search directions. Each of these directions is calculated by particular algorithms. Similar to other iterative methods for solving the unconstrained optimization problems, the crucial moment is to find the appropriate descent direction vectors s
k, d
k and the optimal step length α
k. In the proposed iteration (2), there are two direction vectors, and that was a motivation for naming this method as Accelerated Double Direction method (or shortly A
D
D method). The decisive point of our research stands actually on two-direction form of the analyzed method and its implementation. Originally, the method of this particular form, but for different assumptions, is described in [1, 2]. In [1, 2], the implementation of the likely defined method is omitted so in a way in this work we extend and fulfill the similar topic. To allow the method to become suitable for the implementation, we modify choice of the vectors d
k and s
k. Another contribution of this paper is obtaining better numerical results with respect to the number of iterations among some known methods for unconstrained optimization.Further, the following notation is used:(3)
g
(
x
)
=
∇
f
(
x
)
,
G
(
x
)
=
∇
2
f
(
x
)
,
g
k
=
∇
f
(
x
k
)
,
G
k
=
∇
2
f
(
x
k
)
,
where ∇
f
(
x
) denotes the gradient of f and ∇
2
f
(
x
) denotes the Hessian of f. As usual, x
T denotes the transpose of x.There are some known procedures for deriving appropriate search directions. We mention several of them (see [1, 3, 4]).On the other hand, computation of the step length is also important. The common way to determine stepsizeα
k is the inexact line search technique. The only requirement in the line search procedure is decreasing in the objective function values. This way we calculate the step length which is appropriate enough for our iterative optimization problem (see [5–12]).In the present paper, we use a combination of the iterative scheme (2) and the accelerated gradient descent method from [13]. More precisely, the first term, α
k
s
k, in (2) is defined using the principles from the [13] method. The second term, α
k
2
d
k, appears as the correction factor which is defined from the Taylor expansion series.The paper is organized as follows. In Section2, the basic motivation and idea for deriving the accelerated gradient descent method of the form (2) are explained. The algorithm of derived Accelerated Double Direction method, in short A
D
D method, is presented in Section 3, where also the main result of this work is analyzed. The convergence of A
D
D method is proved in Section 4. Numerical tests and comparisons of derived A
D
D method with the accelerated gradient descent method with line search (so-called S
M method) originated in [13] as well as with nonaccelerated version of A
D
D method (N
A
D
D method) are given in Section 5.


## 2. Preliminaries

The accelerated gradient descent (A
G
D) methods of the form
(4)
x
k
+
1
=
x
k
-
θ
k
t
k
g
k
use θ
k
>
0 as an acceleration parameter. The first A
G
D method is originated in [14]. A type of A
G
D method is considered in [13]. This A
G
D method is called S
M method and it is derived starting from the Newton iterative method with the line search
(5)
x
k
+
1
=
x
k
-
t
k
S
k
g
k
,
where S
k is an appropriate approximation of the Hessian inverse, presented as a symmetric n
×
n positive definite matrix. Taking S
k
=
γ
k
-
1
I, γ
k
>
0 as an approximation of the inverse of the Hessian, the authors in [13] derived an accelerated modified Newton scheme:
(6)
x
k
+
1
=
x
k
-
t
k
γ
k
-
1
g
k
,
where step length t
k is computed by means of the backtracking inexact line search procedure and γ
k is the length of the acceleration parameter given by the following expression:
(7)
γ
k
+
1
=
2
γ
k
γ
k
[
f
(
x
k
+
1
)
-
f
(
x
k
)
]
+
t
k
∥
g
k
∥
2
t
k
2
∥
g
k
∥
2
.In this paper, we are using the motivation for calculating an accelerated parameter,γ
k, from Taylor’s extension of an objective function. But, unlike S
M method, we choose to evaluate a method which contains two direction vectors.A multistep minimization iterative process (2) with two direction vectors is described in [1, 2]. This algorithm considers generally nondifferentiable functions and it consists of three partial subalgorithms, each explaining one of the needed parameters: two direction vectors s
k and d
k and the stepsize α
k. Since this work considers uniformly convex or strictly convex quadratic functions, we modify the proposed subalgorithms in a way according to the present conditions. In a further section, we give three supplemented algorithms based on propositions originally written in [1].


## 3. Main Algorithm

Taking into consideration the results obtained in [1, 13], we can construct new iterative method. That process has a form predefined by (2), where the parameter s
k has properties taken from S
M method. Using the same notation as in the previous section, the process (2) becomes
(8)
x
k
+
1
=
x
k
-
α
k
γ
k
-
1
g
k
+
α
k
2
d
k
,
assuming that the direction vector s
k is, according to S
M method, defined by -
γ
k
-
1
g
k. Practically, deriving the direction vector s
k is reduced to deriving the positive real number γ
k. Taking vector d
k and step length α
k defined similarly as in [1], we get
(9)
x
k
+
1
-
x
k
=
α
k
2
d
k
-
α
k
γ
k
-
1
g
k
.
Now, from Taylor’s expansion of the second rate, the approximation of f
(
x
k
+
1
) can be brought as follows:
(10)
f
(
x
k
+
1
)
≈
f
(
x
k
)
+
g
k
T
(
α
k
2
d
k
-
α
k
γ
k
-
1
g
k
)
+
1
2
(
α
k
2
d
k
-
α
k
γ
k
-
1
g
k
)
T
∇
2
f
(
ξ
)
(
α
k
2
d
k
-
α
k
γ
k
-
1
g
k
)
.
The matrix ∇
2
f
(
ξ
) is, like in [13], replaced by γ
k
+
1
I and the parameter ξ fulfills the following condition:
(11)
ξ
∈
[
x
k
,
x
k
+
1
]
,
ξ
=
x
k
+
δ
(
x
k
+
1
-
x
k
)
=
x
k
+
δ
(
α
k
2
d
k
-
α
k
γ
k
-
1
g
k
)
,
0
≤
δ
≤
1
.
Knowing this, the expression (10) becomes
(12)
f
(
x
k
+
1
)
=
f
(
x
k
)
+
α
k
g
k
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
+
1
2
γ
k
+
1
(
α
k
2
d
k
-
α
k
γ
k
-
1
g
k
)
T
(
α
k
2
d
k
-
α
k
γ
k
-
1
g
k
)
.
From (12), γ
k
+
1 is computed in the following way:
(13)
γ
k
+
1
=
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
)
.It is supposed thatγ
k
+
1
>
0; otherwise, the second-order necessary condition and second-order sufficient condition will not be fulfilled. If in some iterative step it happens that γ
k
+
1
<
0, we take γ
k
+
1
=
1.Then, the next iterative pointx
k
+
2 is computed by
(14)
x
k
+
2
=
x
k
+
1
-
α
k
+
1
g
k
+
1
+
α
k
+
1
2
d
k
+
1
=
x
k
+
1
-
α
k
+
1
(
g
k
+
1
-
α
k
+
1
d
k
+
1
)
.According to the posed assumptions in this paper, original calculations for obtaining the values of step lengthα
k and direction vector d
k given in [1] are modified by Algorithms 1 and 2.Algorithm 1:Calculation of the step length α
k by reducing the curve search rule from [1] to the backtracking line search starting from α
=
1.
Require: Objective function f
(
x
), the direction d
k of the search at the point x
k and numbers 0
<
σ
<
0.5 and β
∈
(
σ
,
1
).
(1) Set α
=
1
(2) while f
(
x
k
+
α
d
k
)
>
f
(
x
k
)
+
σ
α
g
k
T
d
k take α
:
=
α
β
(3) Return α
k
=
α.Algorithm 2:Calculation of direction vector d
k.
Require: The stepsize α
k.
(1) α
=
α
k.
(2)          d
k
(
α
)
=
{
d
k
*
,
k
≤
m
-
1
∑
i
=
2
m
α
i
-
1
d
k
-
i
+
1
*
,
k
≥
m
,
where d
k
* is the solution of the problem min
x
∈
ℝ
⁡
Φ
k
(
d
), and Φ
k
(
d
) is defined by
Φ
k
(
d
)
=
g
k
T
d
+
1
2
γ
k
+
1
I.Supplemented further, the main contribution in this paper is presented by Algorithm3.Algorithm 3:Accelerated Double Direction method (ADD method).
Require:  0
<
ρ
<
1, 0
<
τ
<
1, x
0
(1) Set k
=
0, compute f
(
x
0
), g
0 and take γ
0
=
1.
(2) If ∥
g
k
∥
<
ϵ, then go to Step  9, else continue by the next Step.
(3) Find the stepsize α
k applying by Algorithm 1.
(4) Compute d
k by Algorithm 2.
(5) Compute x
k
+
1 using (8), f
(
x
k
+
1
) and g
k
+
1.
(6) Determine the scalar γ
k
+
1 using (13).
(7) If γ
k
+
1
<
0, then take γ
k
+
1
=
1.
(8) Set k
:
=
k
+
1, go to Step  2.
(9) Return x
k
+
1 and f
(
x
k
+
1
).Remark 1.
It is possible to compare iterations (9) proposed in the present paper with the general iterative scheme proposed in [15]. The search direction in [15] is defined as a linear combination of g
k
+
1 and x
k
+
1
-
x
k. On the other hand, the search direction in (9) is defined as a particular linear combination of -
g
k and the vector d
k defined in Algorithm 2.


## 4. Convergence Analysis

In this section, the convergence analysis of constructed method is discussed. We will first analyze a set of uniformly convex functions and afterwards a subset of strictly convex functions. We will start with the following proposition and lemma that can be found in [16, 17].Proposition 22 (see [16, 17]).
If the functionf
:
ℝ
n
→
ℝ is twice continuously differentiable and uniformly convex on ℝ
n, then (1)
the function
f
has a lower bound on
L
0
=
{
x
∈
ℝ
n
∣
f
(
x
)
≤
f
(
x
0
)
}
, where
x
0
∈
ℝ
n
is available;
(2)
the gradient
g
is Lipschitz continuous in an open convex set
B
which contains
L
0
; that is, there exists
L
>
0
such that
(15)
∥
g
(
x
)
-
g
(
y
)
∥
≤
L
∥
x
-
y
∥
,
∀
x
,
y
∈
B
.Lemma 3 (see [16, 17]).
Under the assumptions of Proposition2, there exist real numbers m, M satisfying
(16)
0
<
m
≤
1
≤
M
,
such that f
(
x
) has a unique minimizer x
* and
(17)
m
∥
y
∥
2
≤
y
T
∇
2
f
(
x
)
y
≤
M
∥
y
∥
2
,
∀
x
,
y
∈
ℝ
n
;
1
2
m
∥
x
-
x
*
∥
2
≤
f
(
x
)
-
f
(
x
*
)
≤
1
2
M
∥
x
-
x
*
∥
2
,
∀
x
∈
ℝ
n
;
m
∥
x
-
y
∥
2
≤
(
g
(
x
)
-
g
(
y
)
)
T
(
x
-
y
)
≤
M
∥
x
-
y
∥
2
,
∀
x
,
y
∈
ℝ
n
.The estimation of decreasing of a given uniformly convex function in each iteration is described in the following lemma taken from [13].Lemma 4 (see [13]).
For a twice continuously differentiable and uniformly convex functionf on ℝ
n and for sequence {
x
k
} generated by Algorithm 3 the following inequality is valid:
(18)
f
(
x
k
)
-
f
(
x
k
+
1
)
≥
μ
∥
g
k
∥
2
,
where
(19)
μ
=
{
σ
M
,
σ
(
1
-
σ
)
L
β
}
.Proof.
The proof follows directly from the proof of Lemma  4.2 in [13] using s
k
=
-
γ
k
-
1
g
k instead of d
k.The following theorem guarantees a linear convergence of Accelerated Double Direction method. The proof is the same as the proof of Theorem(
4.1
) in [13].Theorem 5 (see [13]).
If the objective functionf is twice continuously differentiable and uniformly convex on ℝ
n and the sequence {
x
k
} is generated by Algorithm 3, then
(20)
lim
⁡
k
→
∞
∥
g
k
∥
=
0
and the sequence {
x
k
} converges to x
* at least linearly.We now consider the case of strictly convex quadratic function which has the form(21)
f
(
x
)
=
1
2
x
T
A
x
-
b
T
x
,
where A is real n
×
n symmetric positive definite matrix and b
∈
ℝ
n. This particular case is observed since the convergence of gradient methods is generally difficult and nonstandard. In the following analysis, we will use some known assumptions taken from [18–20]. Let λ
1
≤
λ
2
≤
⋯
≤
λ
n be eigenvalues of the matrix A. In [20], the Q-linear rate of convergence is presented for BB method under the assumption λ
n
<
2
λ
1.Lemma 6.
Letf be a strictly convex quadratic function given by the expression (21) which involves symmetric positive definite matrix A
∈
ℝ
n
×
n and the gradient descent method (8). Let λ
1 and λ
n be, respectively, the smallest and the largest eigenvalues of A. Let the parameters γ
k, α
k, and d
k be determined according to (13) and Algorithm 3. Then, the following holds:
(22)
λ
1
≤
γ
k
+
1
α
k
+
1
≤
2
λ
n
σ
,
k
∈
ℕ
.Proof.
According to (21), the difference between the values of the objective strictly convex quadratic function in current and previous iterative point is
(23)
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
.
Knowing the fact thatx
k
+
1
=
x
k
-
α
k
γ
k
-
1
g
k
+
α
k
2
d
k, it follows that
(24)
f
(
x
k
+
1
)
-
f
(
x
k
)
=
1
2
(
x
k
-
α
k
γ
k
-
1
g
k
+
α
k
2
d
k
)
T
A
(
x
k
-
α
k
γ
k
-
1
g
k
+
α
k
2
d
k
)
-
b
T
(
x
k
-
α
k
γ
k
-
1
g
k
+
α
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
α
k
γ
k
-
1
g
k
T
A
x
k
+
1
2
α
k
2
d
k
T
A
x
k
-
1
2
α
k
γ
k
-
1
x
k
T
A
g
k
+
1
2
α
k
2
γ
k
-
2
g
k
T
A
g
k
-
1
2
α
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
k
2
x
k
T
A
d
k
-
1
2
α
k
3
γ
k
-
1
g
k
T
A
d
k
+
1
2
α
k
4
d
k
T
A
d
k
-
b
T
x
k
+
α
k
γ
k
-
1
b
T
g
k
-
α
k
2
b
T
d
k
-
1
2
x
k
T
A
x
k
+
b
T
x
k
.
Replacing the equivalenceg
k
=
A
x
k
-
b, we obtain
(25)
f
(
x
k
+
1
)
-
f
(
x
k
)
=
-
α
k
γ
k
-
1
x
k
T
A
g
k
+
α
k
2
x
k
T
A
g
k
-
α
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
k
2
γ
k
-
2
g
k
T
A
g
k
+
1
2
α
k
4
d
k
T
A
d
k
+
α
k
γ
k
-
1
b
T
g
k
-
α
k
2
b
T
d
k
.
Further grouping gives
(26)
f
(
x
k
+
1
)
-
f
(
x
k
)
=
α
k
γ
k
-
1
(
b
T
g
k
-
x
k
T
A
g
k
)
+
α
k
2
(
x
k
T
A
d
k
-
b
T
d
k
)
-
α
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
k
2
γ
k
-
2
g
k
T
A
g
k
+
1
2
α
k
4
d
k
T
A
d
k
and this leads to
(27)
f
(
x
k
+
1
)
-
f
(
x
k
)
=
-
α
k
γ
k
-
1
g
k
T
g
k
+
α
k
2
g
k
T
d
k
-
α
k
3
γ
k
-
1
d
k
T
A
g
k
+
1
2
α
k
2
γ
k
-
2
g
k
T
A
g
k
+
1
2
α
k
4
d
k
T
A
d
k
.
Using the symmetry properties of matrix A implies
(28)
f
(
x
k
+
1
)
-
f
(
x
k
)
=
α
k
g
k
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
-
1
2
α
k
2
γ
k
-
1
g
k
T
A
(
α
k
d
k
-
γ
k
-
1
g
k
)
+
1
2
α
k
3
d
k
T
A
(
α
k
d
k
-
γ
k
-
1
g
k
)
=
(
α
k
g
k
T
-
1
2
α
k
2
γ
k
-
1
g
k
T
A
+
1
2
α
k
3
d
k
T
A
)
(
α
k
d
k
-
γ
k
-
1
g
k
)
.
Switching the last equivalence into (13), γ
k
+
1 becomes
(29)
γ
k
+
1
=
2
[

(
α
k
g
k
T

-

(
1
/
2
)
α
k
2
γ
k
-
1

g
k
T
A

+

(
1
/
2
)
α
k
3
d
k
T
A
)

(
α
k
d
k
-
γ
k
-
1
g
k
)
α
k
2
(
α
k
d
k
-
γ
k
-
1
g
k
)
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
-
α
k
g
k
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
α
k
2
(
α
k
d
k
-
γ
k
-
1
g
k
)
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
]
and further
(30)
γ
k
+
1
=
2
(
(
α
k
g
k
T
-
1
2
α
k
2
γ
k
-
1
g
k
T
A
+
1
2
α
k
3
d
k
T
A
-
α
k
g
k
T
)
×
(
α
k
d
k
-
γ
k
-
1
g
k
)
(
α
k
g
k
T
-
1
2
α
k
2
γ
k
-
1
g
k
T
A
+
1
2
α
k
3
d
k
T
A
-
α
k
g
k
T
)
)
×
(
α
k
2
(
α
k
d
k
-
γ
k
-
1
g
k
)
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
)
-
1
.
Finally,(31)
γ
k
+
1
=
2
·
1
2
α
k
2
(
α
k
d
k
-
γ
k
-
1
g
k
)
T
A
(
α
k
d
k
-
γ
k
-
1
g
k
)
α
k
2
(
α
k
d
k
-
γ
k
-
1
g
k
)
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
,
which implies definitive expression for γ
k
+
1:
(32)
γ
k
+
1
=
(
α
k
d
k
-
γ
k
-
1
g
k
)
T
A
(
α
k
d
k
-
γ
k
-
1
g
k
)
(
α
k
d
k
-
γ
k
-
1
g
k
)
T
(
α
k
d
k
-
γ
k
-
1
g
k
)
.
Since A is a real symmetric positive definite matrix and since the previous expression for γ
k
+
1 presents the Rayleigh quotient of the real symmetric matrix A at the vector α
k
d
k
-
γ
k
-
1
g
k, it can be concluded that
(33)
λ
1
≤
γ
k
+
1
≤
λ
n
,
k
∈
ℕ
.
The fact 0
≤
α
k
+
1
≤
1 implies the left hand side of inequality (22). The right hand side of the same inequality arises from the inequality
(34)
α
k
>
β
(
1
-
σ
)
γ
k
L
,
which is proved in [13], in Lemma 4. The direct consequence of the previous expression is
(35)
γ
k
+
1
α
k
+
1
<
L
β
(
1
-
σ
)
.
We know that A is symmetric and g
(
x
)
=
A
(
x
)
-
b. Considering these two relevant facts, we can conclude that
(36)
∥
g
(
x
)
-
g
(
y
)
∥
=
∥
A
x
-
A
y
∥
=
∥
A
(
x
-
y
)
∥
≤
∥
A
∥
∥
x
-
y
∥
=
λ
n
∥
x
-
y
∥
,
which means that in the last expression the largest eigenvalue λ
n of matrix A has the property of Lipschitz constant L. In the backtracking algorithm, we chose that parameters σ and β take the values 0
<
σ
<
0.5 and β
∈
(
σ
,
1
). As a resulting inequality, we have
(37)
γ
k
+
1
α
k
+
1
<
L
β
(
1
-
σ
)
=
λ
n
β
(
1
-
σ
)
<
2
λ
n
σ
and with this expression we are ending the proof.Theorem 7.
For the strictly convex quadratic functionf given by (21) and the gradient descent method (2), under the additional assumptions λ
n
<
2
λ
1 for the eigenvalues of matrix A, one has
(38)
(
p
i
k
+
1
)
2
≤
δ
2
(
p
i
k
)
2
,
(
q
i
k
+
1
)
2
≤
λ
n
2
(
q
i
k
)
2
,
where
(39)
δ
=
max
⁡
{
1
-
σ
λ
1
2
λ
n
,
λ
n
λ
1
-
1
}
,
as well as
(40)
lim
⁡
k
→
∞
∥
g
k
∥
=
0
.Proof.
Suppose that{
v
1
,
v
2
,
…
,
v
n
} are orthonormal eigenvectors of symmetric positive definite matrix A and let {
x
k
} be the sequence of values constructed by Algorithm 3. For some k and value x
k, g
k
=
A
x
k
-
b. On the other hand,
(41)
g
k
=
∑
i
=
1
n
‍
p
i
k
v
i
,
d
k
=
∑
i
=
1
n
‍
q
i
k
v
i
for some real constants p
1
k
,
p
2
k
,
…
,
p
n
k and q
1
k
,
q
2
k
,
…
,
q
n
k.
From (2), it follows that
(42)
g
k
+
1
=
A
(
x
k
-
α
k
γ
k
-
1
g
k
+
α
k
2
d
k
)
-
b
=
(
I
-
α
k
γ
k
-
1
A
)
g
k
+
α
k
2
A
d
k
,
which together with (41) gives
(43)
g
k
+
1
=
∑
i
=
1
n
‍
p
i
k
+
1
v
i
=
∑
i
=
1
n
‍
(
(
1
-
α
k
γ
k
-
1
λ
i
)
p
i
k
+
α
k
2
λ
i
q
i
k
)
v
i
=
∑
i
=
1
n
‍
(
1
-
α
k
γ
k
-
1
λ
i
)
p
i
k
v
i
+
α
k
2
∑
i
=
1
n
‍
λ
i
q
i
k
v
i
.
To prove (38), it is enough to show that |
1
-
(
λ
i
/
γ
k
α
k
-
1
)
|
≤
δ since |
λ
i
|
≤
λ
n for all i
∈
{
1,2
,
…
,
n
}. There are two cases. First, if λ
i
≤
γ
k
/
α
k implying (22), we can conclude the following:
(44)
1
>
λ
i
γ
k
α
k
-
1
≥
σ
λ
1
2
λ
n
⟹
1
-
λ
i
γ
k
α
k
-
1
≤
1
-
σ
λ
1
2
λ
n
≤
δ
.
Now, let us examine another case γ
k
/
α
k
<
λ
i. Since
(45)
1
<
λ
i
γ
k
α
k
-
1
≤
λ
n
λ
1
,
we have
(46)
|
1
-
λ
i
γ
k
α
k
-
1
|
≤
λ
n
λ
1
-
1
≤
δ
.
To prove (40), the representation (41) is used:
(47)
∥
g
k
∥
2
=
∑
i
=
1
n
‍
(
p
i
k
)
2
.
Knowing that 0
<
δ
<
1 together with the proved inequalities (38) leads us to expression (40) which is the final conclusion.


## 5. Numerical Results

In order to numerically prove the acceleration property ofA
D
D method, we constructed the nonaccelerated version of this scheme and named it Nonaccelerated Double Direction method, shortly N
A
D
D method. For that purpose, we had to eliminate the acceleration parameter γ
k. Since γ
k presents an approximation of the inverse of the Hessian, the question was what the adequate substitution for γ
k in iteration (9) is. The natural choice for nonaccelerated counterpart of A
D
D method is defined by taking constant value γ
k
=
1 for all k in each iteration (9). Then, the Hessian is approximated by the identity matrix in each iteration. That is way the nonaccelerated form of the process is obtained and iteration (9) becomes
(48)
x
k
+
1
-
x
k
=
α
k
2
d
k
-
α
k
g
k
.We tested the presented Accelerated Double Direction method, in shortA
D
D method, on a large scale of unconstrained test problems given in 25 functions proposed in [21]. Through the execution, we investigate the number of iterative steps since our primary goal is to reduce this number. Each of 25 functions is tested for 10 numerical experiments. In order to have more general view of analyzed characteristic number of iterations, we choose to test cases of large number of variables: 1000, 2000, 3000, 5000, 7000, 8000, 10000, 15000, 20000, and 30000. A
D
D method is compared with S
M method, since in [13] S
M method is already compared with A
G
D method and G
D (gradient descent) method from [14], but for a lower number of variables (500, 1000, 2000, 3000, 5000, 7000, 8000, 10000, and 15000). In the same paper, it is proved that S
M method outperformed A
G
D and G
D methods with respect to the number of iterative steps. Since our aim is to improve the numerical results with respect to this characteristic by using constructed A
D
D method, it is enough to show that on this matter A
D
D algorithm obtains better results than S
M. The stopping criteria for A
D
D Algorithm 3 are like those in [13] for S
M method:
(49)
∥
g
k
∥
≤
1
0
-
6
,
|
f
(
x
k
+
1
)
-
f
(
x
k
)
|
1
+
|
f
(
x
k
)
|
≤
1
0
-
16
.The codes that are used for testing are written in theC
+
+ programming language on a Workstation Intel Celeron 2.2 GHz.The presented results in Table1 show the enormous dominance of A
D
D method with respect to the number of iterations. Among the 25 tested functions, a very big difference in the number of iterations in favor of A
D
D method is obvious. Precisely, in cases of even 20 of the tested functions,ADD is significantly more effective with respect to the analyzed characteristic than S
M method.Table 1
Number of iterations needed in developingSM, ADD, and NADD on 25 large-scale test functions.
Test function
SM
ADD
NADD
Extended penalty
589
70
>t
e
Perturbed quadratic
111972
80
>t
e
Raydan 1
21125
86
>t
e
Diagonal 1
10417
81
>t
e
Diagonal 3
10574
80
>t
e
Generalized tridiagonal 1
278
110
>t
e
Extended tridiagonal 1
3560
120
>t
e
Extended three exponential terms
164
100
3551
Diagonal 4
80
100
>t
e
Extended Himmelblau
168
100
>t
e
Quadratic diagonal perturbed
53133
90
>t
e
Quadratic QF1
114510
80
>t
e
Extended quadratic penalty QP1
224
90
>t
e
Extended quadratic penalty QP2
162
80
>t
e
Quadratic QF2
118801
86
>t
e
Extended EP1
68
100
>t
e
Extended tridiagonal 2
584
120
>t
e
Arrwhead
10
102
>t
e
Almost perturbed quadratic
110121
80
>t
e
Engval1
185
100
>t
e
QUARTC
190
10
10
Generalized quartic
156
100
3258
Diagonal 7
90
3287
>t
e
Diagonal 8
96
3225
>t
e
Diagonal 9
11235
80
>t
eIn Table1, the test results of the N
A
D
D method are also presented. During the test procedures needed execution time for N
A
D
D method was evidently too long. That is why we defined anexecution time limiter parameter
t
e as follows: if the test execution is lasting more than t
e, we will stop further testing and declare that the testing istoo long. The longest execution time in testing A
D
D method is obtained for Diagonal 7 function and it is totaled 3287 seconds. We doubled this time, approximated it, and denoted this approximation as t
e:
(50)
2
·
3287
=
6574
=
1
h
49
min
⁡
34
sec
≈
2
h
≡
t
e
.
Having this criterion included, we were able to test only 3 of 25 test functions by N
A
D
D scheme for the proposed number of variables (1000, 2000, 3000, 5000, 7000, 8000, 10000, 15000, 20000, and 30000). Obtained results show obvious dominance of the acceleration properties of A
D
D method comparing to its nonaccelerated version. The notation >
t
e in Table 1 means that the execution time exceeds t
e.Considering the presented results in Table1 for all 25 given functions and all 250 tests, Table 2 actually illustrates the fact that A
D
D method has approximately 66 times lower number of iterations than S
M method.Table 2
Average results for 25 tested functions on 250 numerical experiments for each method,SM and ADD, generated for large number of variables: 1000, 2000, 3000, 5000, 7000, 8000, 10000, 15000, 20000, and 30000.
Average value
SM
ADD
Number of iterations
22739.68
342.28To get more clear comparison betweenA
D
D and N
A
D
D, we did additional tests for 100 times lower number of variables: 10, 20, 30, 50, 70, 80 100, 150, 200, and 300. The contents of Table 3 display that in this case 9 of 25 test functions were achievable for testing by N
A
D
D scheme.Table 3
Numerical results for 90 tests for each method,ADD and NADD, tested on 9 test functions, generated for a lower number of variables.
Test function
Number of iterations
ADD
NADD
Perturbed quadratic
80
7917
Extended tridiagonal 1
120
901248
Extended three exponential terms
100
3438
Diagonal 4
100
9036
Quadratic diagonal perturbed
102
224031
Quadratic QF1
92
8709
Almost perturbed quadratic
90
7939
Quartic
10
10
Diagonal 9
80
339Remark 8.
During the testing procedures, we were able to test Generalized quartic function for larger number of variables(
1000,2000,3000,5000,7000,8000,10000,15000,20000, and 30000
), but while applying N
A
D
D iteration for a 100 times lower set of variables on this function (specially for n
=
30 and n
=
100
), time limiter parameter is t
e
≫
2
h. That is why this function is not displayed in Table 3.According to the results of Table3, obtained for A
D
D and N
A
D
D methods, we display average values for 90 test executions among the 9 functions that satisfy definedtime limiter condition in Table 4. This table confirms even 1502 times better results in favor of A
D
D method compared to its nonaccelerated dual method N
A
D
D.Table 4
Average results for 9 tested functions on 90 numerical experiments for each method,NADD and ADD, for a lower number of variables: 10, 20, 30, 50, 70, 80, 100, 150, 200, and 300.
Average value
NADD
ADD
Number of iterations
129185.22
86


## 6. Conclusion

We used the proposed form of the iteration for unconstrained optimization problems from [1] to define in similar way a double direction method for uniformly convex functions and for some strictly convex quadratic functions. The presented iterative method is an acceleration gradient descent method, constructed from the Newton method with the line search, approximating the Hessian by appropriate diagonal matrix.The aim of constructing Accelerated Double Direction method, in shortA
D
D method, is to improve the number of iterations for chosen test functions from [21] for a large number of parameters and this goal is successfully obtained. Also, important contribution of A
D
D method is the implementation of specific form of iteration introduced originated in [1].It is proved thatA
D
D is linearly convergent method for the uniformly convex functions and for the special subset of strictly convex quadratic functions.In order to confirm the advantages of accelerated properties ofA
D
D iteration, a nonaccelerated representation of A
D
D scheme, N
A
D
D method, is constructed. Comparative tests substantiate the enormous benefits of A
D
D method. Derived accelerated method is also compered with S
M method whose dominance among the A
G
D method and G
D method has alreday been proven in [13]. A
D
D algorithm generates multiple times better numerical results with respect to the number of iterations compared to S
M method.



---

*Source: 965104-2014-04-02.xml*