# A Transformation of Accelerated Double Step Size Method for Unconstrained Optimization

Authors: Predrag S. Stanimirović; Gradimir V. Milovanović; Milena J. Petrović; Nataša Z. Kontrec
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A reduction of the originally double step size iteration into the single step length scheme is derived
under the proposed condition that relates two step lengths in the accelerated double step size gradient
descent scheme. The proposed transformation is numerically tested. Obtained results confirm the
substantial progress in comparison with the single step size accelerated gradient descent method
defined in a classical way regarding all analyzed characteristics: number of iterations, CPU time,
and number of function evaluations. Linear convergence of derived method has been proved.


---

## Body

## 1. Introduction and Background

The SM iteration from [1] is defined by the iterative process(1)
x
k
+
1
=
x
k
-
t
k
γ
k
-
1
g
k
,where x
k
+
1 is a new iterative point, x
k is the previous iterative point, g
k is the gradient vector (search direction), t
k is a step length, and γ
k
>
0 is the acceleration parameter. In [1] it is verified that the accelerated gradient SM iteration (1) outperforms the gradient descent, GD, as well as the Andrei’s accelerated gradient descent AGD method from [2].Double direction and double step size accelerated methods, denoted by ADD and ADSS methods, respectively, for solving the problems of unconstrained optimization are presented in [3, 4]. These two algorithms can be generally formulated through the next merged expression: (2)
x
k
+
1
=
x
k
+
α
k
s
k
+
β
k
d
k
,where x
k is the previous iterative point and real values α
k and β
k denote two step lengths while the vectors s
k and d
k are two vector directions. The values of step lengths are determined by backtracking line search techniques. The gradient is basically used for defining a search direction, but some new suggestions for deriving a descending vector direction are given in [3, 5]. Taking the substitutions(3)
s
k
=
-
γ
k
-
1
g
k
,
β
k
=
α
k
2
,into (2) produces the ADD iterative scheme from [3]:(4)
x
k
+
1
=
x
k
-
α
k
γ
k
-
1
g
k
+
α
k
2
d
k
,where γ
k represents the acceleration parameter for the iteration (4). The benefits of the acceleration properties that arise from the usage of the parameter γ
k are explained in [3]. The so called nonaccelerated version of ADD method (NADD method shortly) is defined in order to numerically verify the acceleration property of the parameter γ
k. Three methods, SM, ADD, and NADD, are numerically compared in [3]. Results show the enormous efficiency of ADD scheme in comparison with its nonaccelerated counterpart NADD. Derivation of the direction vector d
k is explained by the Algorithm 3.2 in [3]. The ADD outperforms its competitive SM method from [1] with respect to the number of iterations.By replacing the vectorss
k and d
k from (2) by -
γ
k
-
1
g
k and -
g
k, respectively, the next iteration is defined as (5)
x
k
+
1
=
x
k
-
α
k
γ
k
-
1
+
β
k
g
k
.The previous scheme is noted as ADSS model and it is proposed in [4]. In the same paper, a huge improvement in performances of this accelerated gradient descent method when compared to the accelerated gradient descent SM method from [1] is numerically confirmed.The main contribution of the present paper is a transformation of the double step size iterative scheme (5) for unconstrained optimization into an appropriate accelerated single step size scheme (called TADSS shortly). Convergence properties of the introduced method are investigated. A special contribution is given by the numerical confirmation that the TADSS algorithm developed from the double step size ADSS model (5) is evidently more efficient than the accelerated SM method obtained in a classical way. Surprisingly, numerical experiments show that the TADSS method overcomes the initial ADSS method.The paper is organized in the following way. The reduction of the double step size ADSS model into the single step size iteration TADSS and the presentation of defined accelerated gradient decent model are given in Section2. Section 3 contains the convergence analysis of derived algorithm for uniformly convex and strictly convex quadratic functions. The results of numerical experiments as well as their comparative analysis of developed method and its forerunners are illustrated in Section 4.


## 2. Transformation of ADSS Scheme into a Single Step Size Iteration

Very advanced numerical results obtained in [4] motivated further research on this topic. An idea is to investigate the properties of a single step size method developed as a reduction of the double step size ADSS model. This reduction is defined by an additional assumption which represents a trade-off between two step length parameters α
k and β
k in the ADSS scheme:(6)
α
k
+
β
k
=
1
.Taking into account assumption (6) into expression (5), which defines the ADSS iteration, leads to the iterative process(7)
x
k
+
1
=
x
k
-
α
k
(
γ
k
-
1
-
1
)
+
1
g
k
.The iteration (7) is noted as transformed ADSS method, or shortly TADSS method. Defined TADSS iteration represents not only a reduction of the double step size ADSS model into the corresponding single step size method, but also a sort of modification of the single step size SM iteration from [1]. This modification can be explained as the substitution of the product t
k
γ
k
-
1, from the SM iteration (1), by the multiplying factor α
k
(
γ
k
-
1
-
1
)
+
1 of the gradient from the TADSS iteration (7).For the sake of simplicity, we use the notationϕ
k
=
α
k
(
γ
k
-
1
-
1
)
+
1 whenever it is possible. The value of the acceleration parameter γ
k
+
1 in (
k
+
1
)th iteration can be derived by using Taylor’s expansion, similarly as described in [1, 3, 4]:(8)
f
(
x
k
+
1
)
≈
f
(
x
k
)
-
g
k
T
ϕ
k
g
k
+
1
2
ϕ
k
g
k
T
∇
2
f
(
ξ
)
ϕ
k
g
k
.The vector ξ in (8) satisfies(9)
ξ
∈
x
k
,
x
k
+
1
,
ξ
=
x
k
+
δ
x
k
+
1
-
x
k
=
x
k
-
δ
ϕ
k
g
k
,
0
≤
δ
≤
1
.Further, it is reasonable to replace in (8) the Hessian ∇
2
f
(
ξ
) by the diagonal matrix γ
k
+
1
I, where γ
k
+
1 is an appropriately chosen real number. This replacement implies (10)
f
(
x
k
+
1
)
≈
f
(
x
k
)
-
ϕ
k
g
k
2
+
1
2
ϕ
k
2
γ
k
+
1
g
k
2
.The relation (10) allows us to compute the acceleration parameter γ
k
+
1:(11)
γ
k
+
1
=
2
f
(
x
k
+
1
)
-
f
(
x
k
)
+
ϕ
k
g
k
2
ϕ
k
2
g
k
2
.Next, the natural inequalityγ
k
+
1
>
0 is inevitable. This condition is required in order to fulfill second-order necessary condition and second-order sufficient condition. The choice γ
k
+
1
=
1 is reasonable in the case when the inequality γ
k
+
1
<
0 appears for some k. This choice produces the next iterative point as(12)
x
k
+
2
=
x
k
+
1
-
α
k
+
1
(
1
-
1
)
+
1
g
k
+
1
=
x
k
+
1
-
g
k
+
1
,which evidently represents the classical gradient descent step.We consider now the(
k
+
1
)th iteration, x
k
+
2, which is given by(13)
x
k
+
2
=
x
k
+
1
-
α
k
+
1
(
γ
k
+
1
-
1
-
1
)
+
1
g
k
+
1
=
x
k
+
1
-
ϕ
k
+
1
g
k
+
1
.Examine the function Φ
k
+
1
(
α
):(14)
Φ
k
+
1
α
=
f
(
x
k
+
1
)
-
α
γ
k
+
1
-
1
-
1
+
1
g
k
+
1
2
+
1
2
α
γ
k
+
1
-
1
-
1
+
1
2
γ
k
+
1
g
k
+
1
2
,defined as the finite part of the Taylor expansion of the function(15)
f
x
k
+
1
-
α
(
γ
k
+
1
-
1
-
1
)
+
1
g
k
+
1under the assumption γ
k
+
2
=
γ
k
+
1. This function is convex when γ
k
+
1
>
0, and its derivative Φ
k
+
1
(
α
)
α
′ is calculated in the following way: (16)
Φ
k
+
1
α
′
=
-
γ
k
+
1
-
1
-
1
g
k
+
1
2
+
α
(
γ
k
+
1
-
1
-
1
)
+
1
γ
k
+
1
g
k
+
1
2
γ
k
+
1
-
1
-
1
=
γ
k
+
1
-
1
-
1
-
1
+
(
α
(
γ
k
+
1
-
1
-
1
)
+
1
)
γ
k
+
1
g
k
+
1
2
=
γ
k
+
1
-
1
-
1
-
1
+
α
-
α
γ
k
+
1
+
γ
k
+
1
g
k
+
1
2
=
γ
k
+
1
-
1
-
1
α
-
1
1
-
γ
k
+
1
g
k
+
1
2
=
γ
k
+
1
-
1
1
-
γ
k
+
1
2
α
-
1
g
k
+
1
2
.Since the inequalityγ
k
+
1
>
0 is achieved, the following is valid:(17)
Φ
k
+
1
α
′
<
0
⟺
α
<
1
,
Φ
k
+
1
α
′
=
0
⟺
α
=
1
.Therefore, the function Φ
k
+
1
(
α
) decreases in the case Φ
k
+
1
α
′
<
0 and achieves its own minimum in the case α
=
1. According to the criteria given by (17), desirable values for α are within the interval (
-
∞
,
1
]. Now, (7) is a kind of the gradient descent process in the case ϕ
k
=
α
k
(
γ
k
-
1
-
1
)
+
1
>
0. Since γ
k
>
0, it is easy to verify the following condition for the step length α
k:(18)
α
k
≤
γ
k
γ
k
-
1
.Since γ
k
/
γ
k
-
1
>
1 in the case γ
k
>
1, this fractional number is not appropriate upper bound for α
k in this case. On the other hand, the inequality γ
k
/
γ
k
-
1
<
0 holds in the case γ
k
<
1, so that γ
k
/
γ
k
-
1 is an appropriate upper bound for α
k in this case.Further analysis of (10) in the case γ
k
<
1 gives(19)
f
(
x
k
)
-
f
(
x
k
+
1
)
≈
ϕ
k
g
k
2
-
1
2
ϕ
k
2
γ
k
+
1
g
k
2
,which implies(20)
f
(
x
k
+
1
)
<
f
(
x
k
)
⟺
ϕ
k
≤
2
γ
k
+
1
.Taking into account γ
k
<
1, it is not difficult to verify that the criterion (20) restricts desirable values for α
k within the interval (21)
α
k
≤
γ
k
(
2
-
γ
k
+
1
)
γ
k
+
1
(
1
-
γ
k
)
.Final conclusion is that the upper bound forα
k is defined in the case γ
k
<
1, γ
k
+
1
<
1, as the minimum between the upper bounds defined in (18) and (21):(22)
α
k
≤
min
⁡
γ
k
γ
k
-
1
,
γ
k
(
2
-
γ
k
+
1
)
γ
k
+
1
(
1
-
γ
k
)
.According to the previous discussion, the iterative stepα
k is derived by the backtracking line search procedure presented in Algorithm 1.Algorithm 1 (calculation of the step sizeα
k by the backtracking line search which starts from the upper bound defined in (22)).
Requirement: objective function f
(
x
), the direction d
k of the search at the point x
k, and real numbers 0
<
σ
<
0.5 and η
∈
(
σ
,
1
).(1)
Setα
=
min
⁡
γ
k
/
γ
k
-
1
,
γ
k
(
2
-
γ
k
+
1
)
/
γ
k
+
1
(
1
-
γ
k
).
(2)
Whilef
(
x
k
+
α
d
k
)
>
f
(
x
k
)
+
σ
α
g
k
T
d
k take α
:
=
η
α.
(3)
Returnα
k
=
α.Finally, the TADSS algorithm of the defined accelerated gradient descent scheme (7) is presented.Algorithm 2 (transformed accelerated double step size method (TADSS method)).
Requirement: 0
<
ρ
<
1, 0
<
τ
<
1, x
0, γ
0
=
1.(1)
Setk
=
0, compute f
(
x
0
), g
0, and take γ
0
=
1.
(2)
Ifg
k
<
ϵ, then go to Step 8; else continue by the next step.
(3)
Find the step sizeα
k applying Algorithm 1.
(4)
Computex
k
+
1 using (7).
(5)
Determine the scalarγ
k
+
1 using (11).
(6)
Ifγ
k
+
1
<
0 or γ
k
+
1
>
1, then take γ
k
+
1
=
1.
(7)
Setk
:
=
k
+
1; go to Step 2.
(8)
Returnx
k
+
1 and f
(
x
k
+
1
).


## 3. Convergence of TADSS Scheme

The content of this section is the convergence analysis of the TADSS method. In the first part of this section a set of uniformly convex functions is considered. The proofs of the following statements can be found in [6, 7] and have been omitted.Proposition 3 (see [6, 7]).
If the functionf
:
R
n
→
R is twice continuously differentiable and uniformly convex on R
n then (1)
the functionf has a lower bound on L
0
=
{
x
∈
R
n
∣
f
(
x
)
≤
f
(
x
0
)
}, where x
0
∈
R
n is available;
(2)
the gradientg is Lipschitz continuous in an open convex set B which contains L
0; that is, there exists L
>
0 such that(23)
(
∀
x
,
y
)
∈
B
g
(
x
)
-
g
(
y
)
≤
L
x
-
y
.Lemma 4.
Under the assumptions of Proposition3 there exist real numbers m, M satisfying (24)
0
<
m
≤
1
≤
M
,such that f
(
x
) has a unique minimizer x
∗ and(25)
∀
x
,
y
∈
R
n
m
y
2
≤
y
T
∇
2
f
x
y
≤
M
y
2
,
∀
x
,
y
∈
R
n
1
2
m
x
-
x
∗
2
≤
f
(
x
)
-
f
(
x
∗
)
≤
1
2
M
x
-
x
∗
2
,
∀
x
,
y
∈
R
n
m
x
-
y
2
≤
g
x
-
g
y
T
(
x
-
y
)
≤
M
x
-
y
2
.The value of decreasing of analyzed function through each iteration is given by the next lemma which is restated and proven in [1]. The same estimation can similarly be found considering iteration (7). Theorem 6 is approved in [1] and confirms a linear convergence of the constructed method.Lemma 5.
For twice continuously differentiable and uniformly convex functionf on R
n and for the sequence {
x
k
} generated by Algorithm (7) the following inequality is valid:(26)
f
(
x
k
)
-
f
(
x
k
+
1
)
≥
μ
g
k
2
,where(27)
μ
=
min
⁡
σ
M
,
σ
(
1
-
σ
)
L
β
.Theorem 6.
If the objective functionf is twice continuously differentiable as well as uniformly convex on R
n and the sequence {
x
k
} is generated by Algorithm 2 then(28)
lim
k
→
∞
g
k
=
0
,and the sequence {
x
k
} converges to x
∗ at least linearly.In the following review the case of strictly convex quadratic functions is analyzed. This set of functions is given by(29)
f
x
=
1
2
x
T
A
x
-
b
T
x
.In the previous expression A is a real n
×
n symmetric positive definite matrix and b
∈
R
n. It is assumed that the eigenvalues of the matrix A are given and lined as λ
1
≤
λ
2
≤
⋯
≤
λ
n. Since the convergence for the most gradient methods is quite difficult to analyze, in many research articles of this profile convergence analysis is reduced on the set of convex quadratics [8–10]. The convergence of TADSS method is also analyzed under similar presumptions.Lemma 7.
By applying the gradient descent method defined by (7) in which parameters γ
k and α
k are given by relation (11) and Algorithm 1 on the strictly convex quadratic function f expressed by relation (29) where A
∈
R
n
×
n presents a symmetric positive definite matrix, the next inequalities hold:(30)
1
2
λ
n
≤
α
k
+
1
(
γ
k
+
1
-
1
-
1
)
+
1
=
ϕ
k
+
1
≤
1
λ
1
,where λ
1 and λ
n are, respectively, the smallest and the largest eigenvalues of A.Proof.
Considering expression (29), the difference between function value in the current and the previous point is(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
.Applying expression (7) the following is obtained: (32)
f
x
k
+
1
-
f
x
k
=
1
2
x
k
-
ϕ
k
g
k
T
A
x
k
-
ϕ
k
g
k
-
b
T
x
k
-
ϕ
k
g
k
-
1
2
x
k
T
A
x
k
+
b
T
x
k
=
-
1
2
ϕ
k
g
k
T
A
x
k
-
1
2
ϕ
k
x
k
T
A
g
k
+
1
2
ϕ
k
2
g
k
T
A
g
k
+
ϕ
k
b
T
g
k
.
Using the facts that the gradient of the function (29) is g
k
=
A
x
k
-
b in conjunction with the equality b
T
g
k
=
g
k
T
b, one can verify the following: (33)
f
x
k
+
1
-
f
x
k
=
-
1
2
ϕ
k
g
k
T
A
x
k
+
x
k
T
A
g
k
-
ϕ
k
g
k
T
A
g
k
-
2
b
T
g
k
=
-
1
2
ϕ
k
g
k
T
A
x
k
-
b
+
g
k
T
A
x
k
-
b
-
ϕ
k
g
k
T
A
g
k
=
-
ϕ
k
g
k
T
g
k
+
1
2
ϕ
k
2
g
k
T
A
g
k
.
Substituting (33) into (11), the parameter γ
k
+
1 becomes(34)
γ
k
+
1
=
2
-
ϕ
k
g
k
T
g
k
+
1
/
2
ϕ
k
2
g
k
T
A
g
k
+
ϕ
k
g
k
T
g
k
ϕ
k
2
g
k
T
g
k
=
g
k
T
A
g
k
g
k
T
g
k
.
The last relation confirms thatγ
k
+
1 is the Rayleigh quotient of the real symmetric matrix A at the vector g
k, so the next inequalities hold:(35)
λ
1
≤
γ
k
+
1
≤
λ
n
,
k
∈
N
,which combined with the fact that 0
≤
α
k
+
1
≤
1 prove the right hand side in (30):(36)
ϕ
k
+
1
=
α
k
+
1
(
γ
k
+
1
-
1
-
1
)
+
1
≤
γ
k
+
1
-
1
-
1
+
1
=
1
γ
k
+
1
≤
1
λ
1
.The estimation (37)
α
k
>
β
1
-
σ
γ
k
L
,proved in [1], is considered in order to prove the left hand side of (30). Using the notation adopted in this paper, expression (37) becomes(38)
α
k
>
η
1
-
σ
γ
k
L
.Inequality (38) and the facts that η
∈
(
σ
,
1
), σ
∈
(
0,0.5
) and α
k
+
1
∈
(
0,1
) lead to the following conclusion: (39)
ϕ
k
+
1
=
α
k
+
1
(
γ
k
+
1
-
1
-
1
)
+
1
>
α
k
+
1
γ
k
+
1
-
α
k
+
1
≥
α
k
+
1
γ
k
+
1
≥
η
1
-
σ
L
≥
1
-
σ
L
≥
1
2
L
.In the last estimation, Lipschitz constant L can be replaced by λ
n. The conclusion that the eigenvalue λ
n of matrix A has the property of Lipschitz constant L is to be derived from the next analysis. Since matrix A is symmetric and g
(
x
)
=
A
x
-
b the following inequality can be provided:(40)
g
(
x
)
-
g
(
y
)
=
A
x
-
A
y
=
A
(
x
-
y
)
≤
A
x
-
y
=
λ
n
x
-
y
.Substituting L by λ
n, inequality (39) becomes (41)
1
2
λ
n
≤
α
k
+
1
(
γ
k
+
1
-
1
-
1
)
+
1
,and this proves the left hand side of inequalities (30).Remark 8.
Comparing the estimations resulting from the similarly proposed lemma in [1, 3, 4] with the estimation derived from the previous lemma, considering the TADSS method, it can be concluded that the estimation provided by the TADSS scheme involves only the eigenvalues λ
1 and λ
n and not the parameter σ from the backtracking procedure.Theorem 9.
Let the additional assumptionsλ
n
<
2
λ
1 for the eigenvalues of matrix A be imposed and let f be the strictly convex quadratic function given by (29). Assume {
v
1
,
v
2
,
…
,
v
n
} is the orthonormal eigenvectors of symmetric positive definite matrix A and suppose that {
x
k
} is the sequence of values constructed by Algorithm 2. The gradients of convex quadratics defined by (29) are g
k
=
A
x
k
-
b and can be expressed as (42)
g
k
=
∑
i
=
1
n
d
i
k
v
i
,for some real constants d
1
k
,
d
2
k
,
…
,
d
n
k and for some integer k. Then the application of the gradient descent method (7) on the goal function (29) satisfies the following two statements: (43)
d
i
k
+
1
2
≤
δ
2
d
i
k
2
,
δ
=
max
⁡
1
-
λ
1
2
λ
n
,
λ
n
λ
1
-
1
,
(44)
lim
k
→
∞
g
k
=
0
.Proof.
Taking into account (7) one can verify (45)
g
k
+
1
=
A
(
x
k
-
ϕ
k
g
k
)
-
b
=
g
k
-
ϕ
k
A
g
k
=
I
-
ϕ
k
A
g
k
,and by taking (42) we get (46)
g
k
+
1
=
∑
i
=
1
n
d
i
k
+
1
v
i
=
∑
i
=
1
n
‍
1
-
ϕ
k
λ
i
d
i
k
v
i
.
In order to prove (43), it is enough to show that 1
-
ϕ
k
λ
i
≤
δ. So, two cases have to be analyzed. In the first one, it is supposed that λ
i
ϕ
k
≤
1. Applying (30) leads to (47)
1
>
λ
i
ϕ
k
≥
λ
1
2
λ
n
⟹
1
-
λ
i
ϕ
k
≤
1
-
λ
1
2
λ
n
≤
δ
.In the other case, it is assumed that λ
i
ϕ
k
≥
1. From this condition arrives the following conclusion: (48)
1
<
λ
i
ϕ
k
≤
λ
n
1
λ
1
⟹
λ
i
ϕ
k
-
1
≤
λ
n
λ
1
-
1
≤
δ
.
Expression (42) implies(49)
g
k
2
=
∑
i
=
1
n
‍
d
i
k
2
.The fact that the parameter δ, from (43), satisfies 0
<
δ
<
1 confirms expression (44).


## 4. Numerical Experience

Numerical results provided by applying the implementation of TADSS, ADSS, and SM methods on22 test functions for unconstrained test problems, proposed in [2, 11], are presented and investigated. We chose most of the functions from the set of test functions presented in [3, 4] and, as proposed in these papers, also investigated the experiments with a large number of variables in each function: 1000, 2000, 3000, 5000, 7000, 8000, 10000, 15000, 20000, and 30000. The stopping criteria are the same as in [1, 3, 4]. Backtracking procedure is developed using the values σ
=
0.0001, η
=
0.8 of needed parameters. Three main indicators of the efficiency are observed: number of iterations, CPU time, and number of function evaluations. First, we compare the performance of the TADSS scheme with the ADSS method. The reasons for this selection is obvious: the TADSS scheme presents a one-step version of ADSS method. Also, the intention to examine behavior of TADSS and compare it with its forerunner is natural. Obtained numerical values are displayed in Table 1 and refer to the number of iterative steps, the CPU time of executions computed in seconds, and the number of evaluations of the objective function.Table 1
Summary of numerical results for TADSS and ADSS tested on22 large scale test functions.
Test function
Number of iterations
CPU time
Number of function evaluations
TADSS
ADSS
TADSS
ADSS
TADSS
ADSS
Extended Penalty
40
50
2
4
1280
1780
Raydan 1
466
34
11
4
8504
4844
Diagonal 1
20
37
0
0
335
1448
Diagonal 3
21
49
0
1
417
1048
Generalized Tridiagonal 1
61
77
0
0
431
719
Extended Tridiagonal 1
60
70
0
0
250
420
Extended Three Expon. Term
40
40
0
0
400
350
Diagonal 4
40
780
0
0
270
2590
Extended Himmelblau
60
70
0
0
300
480
Quadratic QF1
4953
425
15
0
13738
1755
Extended Quad. Penalty QP1
50
60
0
2
571
841
Extended Quad. Penalty QP2
50
60
0
4
569
843
Quadratic QF2
50
60
0
1
583
836
Extended EP1
186
40
1
0
758
487
Extended Tridiagonal 2
638
80
0
0
2052
420
Arwhead
50
64
0
3
601
1082
Engval1
60
70
0
0
290
460
Quartc
10
70
0
0
30
390
Generalized Quartic
60
70
0
0
250
614
Diagonal 7
189
2201
0
33
566
6633
Diagonal 8
160
2213
1
40
586
6709
Diagonal 9
20
43
0
0
352
3646Obtained numerical results, generally, confirm advantages in favor of TADSS, considering all three tested indicators. More precise, regarding the number of iterative steps TADSS shows better results in 17 out of 22 functions, while ADSS outperforms TADSS in 4 out of 22 experiments and for the extended three exponential terms function both methods require the same number of iterations. Results concerning spanned CPU time confirm that both methods, TADSS and ADSS, are very fast. In 9 out of 22 cases TADSS is faster than ADSS, in 2 out of 22 testings ADSS is faster than TADSS, and even in half of examinations the CPU time of both iterations equals zero. On the issue of the number of evaluations of an objective function, TADSS improves ADSS in 17 out of 22 testings and the opposite case appears in 5 out of 22 cases. Table2 displays average results of tested values.Table 2
Average numerical outcomes of220 testings of each method among the 22 test functions tried out on 10 numerical experiments in each iteration.
Average performances
TADSS
ADSS
Number of iterations
331.09
302.86
CPU time (sec)
1.36
4.18
Number of function evaluations
1506.05
1745.23According to results displayed in Table2, it can be concluded that although TADSS outperforms ADSS in 17 out of 22 testings with regard to the number of iterations, average results show slight advantage of ADSS on this matter. Considering the average number of evaluations, there is an opposite case in favor of TADSS. Consumed CPU time is averagely three times less in favor to the TADSS comparing to the ADSS. Generally, it can be concluded that the one-step variant of the ADSS method, constructed TADSS scheme, behaves slightly better than the original ADSS iteration, especially when we consider the speed of executions.Some additional experiments have been carried out in further numerical research. These tests show the comparison between the TADSS and the SM iterations. As mentioned before, both of the schemes, TADSS and SM, are accelerated gradient descent methods with one iterative step size parameter. We choose this additional numerical comparison in order to confirm that the accelerated single step size TADSS algorithm, derived from the accelerated double step size ADSS model, gives better performances with respect to the all three analyzed aspects than the classically defined accelerated single step size SM method. Table3 with 30 displayed test functions verifies the previous assertion.Table 3
Numerical results for30 test functions tested by the TADSS and the SM methods.
Test functions
Number of iterations
CPU time
Number of function evaluations
TADSS
SM
TADSS
SM
TADSS
SM
Extended Penalty
40
589
2
5
1280
2987
Perturbed Quadratic
4276
111972
13
1868
12017
632724
Raydan 1
466
21125
11
178
8504
116757
Diagonal 1
20
10417
0
116
335
56135
Diagonal 3
21
10574
0
209
417
59425
Generalized Tridiagonal 1
61
278
0
2
431
989
Extended Tridiagonal 1
60
3560
0
35
250
30686
Extended Three Expon. Term
40
164
0
1
400
1224
Diagonal 4
40
80
0
0
270
530
Extended Himmelblau
60
168
0
0
300
566
Quadr. Diag. Perturbed
11542
53133
58
1193
56359
547850
Quadratic QF1
4953
114510
15
2127
13738
649643
Extended Quad. Penalty QP1
50
224
0
12
571
2566
Extended Quad. Penalty QP2
50
162
0
7
569
2057
Quadratic QF2
50
118801
0
2544
583
662486
Extended EP1
186
68
1
1
758
764
Extended Tridiagonal 2
638
584
0
0
2052
2144
Arwhead
50
10
0
0
601
30
Almost Perturbed Quadratic
4202
110121
15
2148
14974
627287
Engval1
60
185
0
7
290
2177
Quartc
10
190
0
0
30
430
Generalized Quartic
60
156
0
0
250
423
Diagonal 7
189
90
0
0
566
220
Diagonal 8
160
96
1
0
586
594
Diagonal 9
20
11235
0
118
352
60566
DIXON3DQ
10
112899
0
1908
30
639957
NONSCOMP
10
10
0
0
30
30
HIMMELH
10
30
0
0
40
80
Power Cute
1455
>t
e
4
>t
e
4567
>t
e
Indef
20
>t
e
0
>t
e
50
>t
eIt can be observed from displayed numerical outcomes that the TADSS method provides better results than the SM method considering the number of iterations in 24 out of 30 testings, while the number of opposite cases is 5 out of 30. For the NONSCOMP test function, both models have the same number of iterations. Concerning the CPU time, both algorithms give the same results for 10 test functions. The TADSS method is faster than SM for 19 test functions, while the SM method is faster than TADSS for one test function only. The greatest progress is obtained with respect to the number of evaluations of the objectives. On this matter, using the TADSS algorithm, better results are obtained in 27 out of 30 test functions, while the opposite case holds for two test functions only. For the NONSCOMP test function both of the compared iterations give the same number of evaluations. From Table3, we can also notice that for 2 out of 30 test functions testings are lasting more than the time limiter constant t
e defined in [3], while for all 30 test functions when the TADSS algorithm is applied the time of execution is far less than t
e.The results arranged in Table4 give even more general view on the benefits provided by applying the TADSS method with regard to the SM method. The average values of 28 test functions, which were possible to test by both methods according to the constant t
e, are presented in the table.Table 4
Average values of numerical results for the TADSS and the SM methods calculated on280 tests for each method.
Average performance
TADSS
SM
Number of iterations
976.21
24336.82
CPU time (in seconds)
4.14
445.68
Number of evaluations
4163.68
146475.96The results presented in the previous table confirm that by applying the TADSS method approximately 25 times less iterations and even 35 times less evaluations of the objective function are needed in comparison with the SM method. Finally, when the TADSS is used, the testing is lasting even 107 times shorter than when the SM is applied.The codes for presented numerical experiments are written in the Visual C++ programming language on a Workstation Intel 2.2 GHz.


## 5. Conclusion

The accelerated single step size gradient descent algorithm, called TADSS, is defined as a transformation of the accelerated double step size gradient descent model ADSS, proposed in [4]. More precisely, the TADSS scheme is derived from the accelerated double step size gradient descent scheme ADSS by imposing relation (6) between two step parameters in the ADSS iteration. The efficiency of ADSS model regarding all analyzed characteristics in comparison to the accelerated gradient descent single step size SM method has been numerically proved in [4].The method defined in this way is comparable with its double step size forerunner, ADSS method, as well as with the single step size accelerated gradient descent SM method which is defined in a classical manner.Results illustrated in Tables1 and 2 generally indicate that the TADSS method behaves similarly as the ADSS method. From the point of mean values, the ADSS scheme gives slightly better results considering the number of iterations. On the other hand, a certain improvement regarding the number of function evaluations and needed CPU time is obtained by applying the TADSS iterations.Even greater advantages of derived TADSS method are presented in Tables3 and 4 where the comparisons between the TADSS and the SM are given. Evidently, the TADSS scheme improves the SM method with respect to all three analyzed characteristics, which was the prime goal in the research presented herein.Linear convergence of the TADSS method is proved for the uniformly convex and the strictly convex quadratic functions.Obtained results motivate further investigations of possible accelerated double step size gradient descent models and its transformations into corresponding single step size variants.



---

*Source: 283679-2015-04-07.xml*