An S-Hybridization Technique Using Two-Directional Optimization

Abstract

In this paper, we study a recently established s-hybrid approach for generating gradient descent methods for solving optimization tasks. We present an s-hybrid variant of the accelerated double-direction method. The results obtained based on convergence analysis confirm the first-order consistency of the newly defined method on a set of strictly convex quadratic functions.

1. Background

Our main focus concerns a special form of accelerated gradient methods that contain two vector directions. Aiming to develop as efficient of an optimization method as possible, we explored an approach that combines several different search vectors. In a calculative sense, iterations with two directions have become the preferred choice above others. In [1], the authors suggested the double-direction iterative method for solving non-differentiable problems

(1)$x_{k+1}=x_k+t_k{s}_k+t_k^2{d}_k.$

In (1), $t_k$ is the iterative step length, while $s_k$ and $d_k$ are two differently defined vector directions. These three parameters are described by the following algorithms listed below. These procedures are denoted as the curve search algorithm, the algorithm for deriving vector direction ${\mathbf{s}}_k$, and the algorithm for deriving vector direction ${\mathbf{d}}_k$, respectively.

Curve search algorithm

(2)$t_k=q^{i\left(k\right)},0<q<1$

where $i\left(k\right)$ is the smallest integer from $\{0,1,2,\dots \}$ such that

(3)$F\left(x_k\right)-F(x_k+q^{i\left(k\right)}{s}_k+q^{2i\left(k\right)}{d}_k)\ge \sigma \left(-q^{i\left(k\right)}{g}_k^T{s}_k+{\displaystyle \frac{1}{2}}{q}^{4i\left(k\right)}{F}_D^{″}(x_k;d_k)\right),$

In (3), $\sigma$ is estimated as $0<\sigma <1$, $F_D^{″}$ stands for the second-order Dini upper-directional derivative at $x_k$ in direction d, and the function F presents the Moreau–Yosida regularization of the objective function f associated to the metric M, defined as follows:

$F\left(x\right)=\underset{y\in {\mathbb{R}}^n}{min}\left\{f\left(y\right)+{\displaystyle \frac{1}{2}}{\parallel y-x\parallel }_M^2\right\}.$

Algorithm for deriving vector direction $s_k$

$s_k\left(t\right)=\left\{\begin{array}{cc}{s}_k^{*}\hfill & \mathrm{if}k\le m-1\hfill \\ -\left[\left(1-\sum _{i=2}^m{t}^{i-1}{p}_k^i\right)g_k+\sum _{i=2}^m{t}^{i-1}{p}_k^i{s}_{k-i+1}\right]\hfill & \mathrm{if}k\ge \mathit{mk}\hfill \end{array}\right.,$

$m=card{I}_k$, $m>1$, $I_k=\{0,1,2,\dots \}$ is an index set at k-th iteration.

$p_k^i={\displaystyle \frac{\rho {\parallel g_k\parallel }^2}{(m-1)[{\parallel g_k\parallel }^2+\left|g_k^T{s}_{k-i+1}\right|]}},i=2,3,\dots ,m,$

$0<\rho <1$ and $s_k^{*}\ne 0$, $k\le m-1$ is a vector that satisfies $g_k^T{s}_k^{*}\le 0$.

Algorithm for deriving vector direction$d_k$

$d_k\left(t\right)=\left\{\begin{array}{cc}{d}_k^{*}\hfill & \mathrm{if}k\le m-1\hfill \\ \sum _{i=2}^m{t}^{i-1}{d}_{k-i+1}^{*}\hfill & \mathrm{if}k\ge m\hfill \end{array}\right.,$

$d_k^{*}$ is the solution to the problem

(4)$\underset{d\in R}{min}▽F{\left(x_k\right)}^{T}d+{\displaystyle \frac{1}{2}}{F}_D^{″}(x_k;d_k).$

The results presented in [1] motivated the authors in [2] to define an accelerated gradient version of the iterative rule (1). In ref. [2], the accelerated double-direction method, denoted as the ADD, is presented as follows:

(5)$x_{k+1}=x_k+t_k^2{\mathbf{d}}_k-t_k{{\gamma }_k^{ADD}}^{-1}{\mathbf{g}}_k.$

In (5), $x_k$ is the current iterative point, $t_k$ is the iterative step size, ${\mathbf{g}}_k$ is the gradient of the objective function, ${{\gamma }_k^{ADD}}^{-1}$ is the accelerated parameter of the ADD method, and ${\mathbf{d}}_k$ is the second vector direction.

The step size parameter $t_k$ of the iteration (5) is calculated in the following way:

$t_k=q^{i\left(k\right)},0<q<1,$

$i\left(k\right)$ is the smallest integer from $0,1,2,\dots ,$ such that

$f\left(x_k\right)-f(x_k+q^{i\left(k\right)}{s}_k+q^{2i\left(k\right)}{d}_k)\ge \sigma \left(-q^{i\left(k\right)}{g}_k^T{s}_k+{\displaystyle \frac{1}{2}}{q}^{4i\left(k\right)}{\gamma }_{k+1}\right),$

where $\sigma$ is a real number such that $0<\sigma <1$.

Remark 1.

An alternative method for deriving the iterative step size is using the backtracking line search procedure, originally presented in [3]. In this procedure, we find the iterative step length $t_k$, generally by starting with initial value $t=1$. Applying the Backtracking parameters $0<\sigma <0.5$ and $\beta \in (\sigma ,1)$, this algorithm checks the following condition:

(6) $f(x_k+t{d}_k)>f\left(x_k\right)+\sigma t{g}_k^T{d}_k,$

while updating the reduced value of the iterative step size as next $t:=t\beta$. The optimal initial step length, $t_k=t$, is obtained after fulfilling the exit condition of the backtracking algorithm.

Remark 2.

There are two main approaches for calculating the step length parameter in an optimization method:

1. exact line search;

2. inexact line search.

Using procedure 1, in each iteration, the step size value is derived as the solution to the following problem:

(7) $f(x_k+t_k{d}_k)=minf(x_k+t{d}_k),t>0.$

Clearly, the exact line search requests additional CPU time. Accordingly, the required number of iterations and the number of the function evaluations are certainly increasing. In relation to that, in many contemporary optimization schemes, the step length parameter is derived using the second approach, i.e., through inexact line search procedures. We list some of the commonly applied inexact line search techniques as follows:

• Weak Wolfe’s line search algorithm is given by the following relations [4]:

  $f(x_k+t_k{d}_k)\le f\left(x_k\right)+\delta t_k{g}_k^T{d}_k$

  $g{(x_k+t_k{d}_k)}^T{d}_k\ge \sigma g_k^{T}t{d}_k;$

• Strong Wolfe’s line search rule is expressed as follows:

  $f(x_k+t_k{d}_k)\le f\left(x_k\right)+\delta t_k{g}_k^T{d}_k$

  $|g{(x_k+t_k{d}_k)}^T{d}_k|\ge -\sigma g_k^{T}t{d}_k;$

• Armijo’s Backtracking procedure is introduced in [3] and defined by Relation (6).

• Goldstein’s rule [5] can be stated as a generalization of the Armijo’s with more strict conditions:

  $f(x_k+t_k{d}_k)\le f\left(x_k\right)+\rho t_k{g}_k^T{d}_k$

  $f(x_k+t_k{d}_k)\ge f\left(x_k\right)+(1+\varrho )t_k{g}_k^T{d}_k,$

  where ρ is the parameter, bounded as in Armijo’s procedure, $\rho \in (0,{\displaystyle \frac{1}{2}})$.

The authors in [2] modified the algorithms for deriving vector directions of the iteration (5) in gradient terms. These modifications are illustrated in Algorithms 1 and 2.

• Algorithm 1 Calculation of the vector $s_k$:

  $s_k=-{{\gamma }_k}^{-1}{g}_{k}k$

• Algorithm 2 Calculation of the vector $d_k$:

  $d_k\left(t\right)=\left\{\begin{array}{cc}{d}_k^{*},\hfill & k\le m-1\hfill \\ \sum _{i=2}^m{t}^{i-1}{d}_{k-i+1}^{*},\hfill & k\ge m\hfill \end{array}\right.$

  where $d_k^{*}$ is the solution of the transformed minimization problem (4)

  $\underset{x\in R}{min}▽f{\left(x_k\right)}^{T}d+{\displaystyle \frac{1}{2}}{\gamma }_{k+1}I=g{\left(x_k\right)}^{T}d+{\displaystyle \frac{1}{2}}{\gamma }_{k+1}I.$

Remark 3.

The vector of the search direction is one of the important elements of each gradient minimization scheme for solving unconstrained optimization problems. In solving minimization tasks, it is assumed that the iterative search direction ${\mathit{d}}_k$ satisfies the following inequality:

(8)$g_k^T{d}_k<0,$

where $g_k$ is the gradient of the objective function at point $x_k$. Relation 8 is known as the descending condition. We list only some of the approaches for generating search directions that fulfill Condition (8).

• One of the common methods for deriving a vector direction that fulfills the descending condition is by expressing it as a multiplication of a negative gradient and a positive accelerated parameter. The acceleration factor can be determined using the features of the first or second-order Taylor expansion of the relevant iteration.

• An unpublished idea for accelerated parameter construction relates to the properties of the logarithmic and local double-logarithmic reconstructions described in [6,7,8].

• A similar approach concerns third-order accurate non-polynomial reconstructions and hyperbolic reconstructions of the objective function as a basis for developing an efficient search direction [9,10].

• The vector direction can be generated as a linear combination of the negative gradient vector and the vector ${\mathit{d}}_k$ defined in Algorithm 2, as proposed in [11].

• In [12], the direction vector is presented as multiplication of the gradient and the accelerated parameter ${\theta }_k={\displaystyle \frac{a_k}{b_k}}$, where $a_k=t_k{g}_k^T{g}_k,b_k=-t_k{y}_k^T{g}_k$,

• The search direction of the conjugate gradient algorithm can be formulated as a linear combination of the gradient and the difference between two successive iterative points, as presented in [13].

The last suggestion from the previous Remark 3 induces an idea that can be used as a basis for further studies. This research can relate to comparisons of a chosen conjugate gradient method and the hybrid accelerated method proposed in this paper.

The general form of the conjugate gradient method is given as follows:

(9)$x_{k+1}=x_k+t_k{d}_k,$

where the iterative step length variable $t_k$ is calculated via the exact line search or via one of the listed inexact line searches given in Remark 1. The main specific of a conjugate gradient scheme comes from the method of generating the vector direction $d_k$, which is defined as follows:

$\begin{array}{c}{d}_0=-\left(x_0\right)\\ d_k=-\left(x_k\right)+p_k{d}_{k-1}\\ p_k={\displaystyle \frac{\parallel f{\left(x_k\right)}^2\parallel }{\parallel f{\left(x_{k-1}\right)}^2\parallel }},\end{array}$

i.e.,

(10)$d_k=-g_k+{\displaystyle \frac{⟨g_k,g_k⟩}{⟨g_{k-1},g_{k-1}⟩}}{d}_{k-1}.$

In (10), $⟨g_k,g_k⟩$ symbolize the scalar product of the gradient vectors.

For suggested comparative studies, in relation to the research presented in this paper, it would be valuable to pay special attention on the set of quadratic functions. A quadratic function is defined by the following expression:

(11)$f\left(x\right)={\displaystyle \frac{1}{2}}{x}^{T}Ax+b^{T}x+C,$

where A is a symmetric, positive definite $n\times n$ matrix, $b\in {\mathbb{R}}^n$, and $C\in \mathbb{R}$. Starting with the initial condition $g_1^T{d}_0=0$, after some calculations, an update for the vector $d_k$ is obtained as follows:

(12)$d_k=-g_k+{\beta }_{k-1}{d}_{k-1},$

where

(13)${\beta }_{k-1}={\displaystyle \frac{g_k^T{g}_k}{g_{k-1}^T{g}_{k-1}}}.$

The conjugate gradient method (9) with a vector direction defined by (12), where ${\beta }_{k-1}$ is calculated using Relation (13), is known as the Fletcher–Reeves formulation of the conjugate gradient method [14].

We list several significant variants of the conjugate gradient method that differ with respect to the expressions that define ${\beta }_{k-1}$ quotients [15,16,17]:

${\beta }_{k-1}={\displaystyle \frac{g_k^T(g_k-g_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}};$

${\beta }_{k-1}={\displaystyle \frac{g_k^T(g_k-g_{k-1})}{g_{k-1}^T{g}_{k-1}}};$

${\beta }_{k-1}=-{\displaystyle \frac{g_k^T{g}_k}{d_{k-1}^T{g}_{k-1}}};$

${\beta }_{k-1}={\displaystyle \frac{g_k^T{g}_k}{d_{k-1}^T(g_k-g_{k-1})}}.$

For example, as a comparative minimization model, the conjugate method proposed in [13] can be taken. Providing the suggested comparative analysis would certainly contribute to the optimization community in general.

One of the crucial variables of the ADD scheme (5) is the acceleration factor, calculated using the second-order Taylor expansion of the objective function:

(14)${\gamma }_{k+1}=2{\displaystyle \frac{f\left(x_{k+1}\right)-f\left(x_k\right)-{\alpha }_k{g}_k^T\left({\alpha }_k{d}_k-{\gamma }_k^{-1}{g}_k\right)}{{\left({\alpha }_k{d}_k-{\gamma }_k^{-1}{g}_k\right)}^T\left({\alpha }_k{d}_k-{\gamma }_k^{-1}{g}_k\right)}}$

The most significant contribution achieved in ref. [2] likely concerns the importance of the accelerated parameter. To substantiate this fact, the authors constructed and tested the non-accelerated version of the ADD model, called NADD method. In these studies, the incomparable effectiveness of the ADD method was confirmed.

Recently, in [18], the authors introduced a new hybrid approach for generating accelerated gradient optimization methods. This calculative technique is denoted as s-hybridization. In developing this new approach of constructing an efficient minimization scheme, the authors were guided by research regarding the nearly contraction mappings and nearly asymptotically nonexpansive mappings and the existence of fixed points of these classes of mappings [19,20]. The main idea regarding the s-$hybrid$ schemes arrives from the study presented in [20], where the following three-termed s-iterative rule is presented:

(15)$\begin{array}{c}{x}_1=x\in C,\hfill \\ x_{n+1}=(1-{\alpha }_n)T{x}_n+{\alpha }_{n}T{y}_n,\hfill \\ y_n=(1-{\beta }_n)x_n+{\beta }_{n}T{x}_n\hfill & n\in N.\hfill \end{array}$

In (15), $\left\{{\alpha }_n\right\}$ and $\left\{{\beta }_n\right\}$ are sequences of real numbers satisfying the following conditions:

(16)$\begin{array}{c}\left\{{\alpha }_n\right\},\left\{{\beta }_n\right\}\subset (0,1)\hfill \\ \sum _{n=1}^{\infty }{\alpha }_n{\beta }_n(1-{\beta }_n)=\infty .\hfill \end{array}$

The authors in [18] simplified S-Iteration (15) by applying Condition (17)

(17)${\alpha }_n+{\beta }_n=1,$

which transforms limits (16)–(18)

(18)$\begin{array}{c}\left\{{\alpha }_n\right\}\subset (0,1)\hfill \\ \sum _{n=1}^{\infty }{\alpha }_n^2(1-{\alpha }_n)=\infty .\hfill \end{array}$

Therewith, the s-iteration with one corrective parameter ${\alpha }_n$ is expressed as follows:

(19)$\begin{array}{c}{x}_1=x\in R,\hfill \\ x_{n+1}=(1-{\alpha }_n)T{x}_n+{\alpha }_{n}T{y}_n,\hfill \\ y_n={\alpha }_n{x}_n+(1-{\alpha }_n)T{x}_n\hfill & n\in N.\hfill \end{array}$

Guided by Iteration (19), in connection with the SM method from [21], the authors in [18] proposed the SHSM optimization method (20):

(20)$x_{n+1}=x_n-(1+{\alpha }_n-{\alpha }_n^2){\gamma }_n^{-1}{t}_n{g}_n.$

The authors proved that this model is well defined and established comprehensive convergence analysis.

This paper is organized as follows: in Section 2, we develop the s-hybrid double-direction minimization method based on the obtained results from the relevant studies described in the first section. The convergence analysis is presented in Section 3. Numerical investigations are illustrated in Section 4.

2. S-Hybridization of the Accelerated Double-Direction Method

In this section, we generate the s-hybrid model using the ADD iterative rule,

$T{y}_k=y_k+t_k^2{\mathbf{d}}_k-t_k{{\gamma }_k}^{-1}{\mathbf{g}}_k,$

as a guiding operator in the three-term process (19). Applying the previously stated facts regarding the s-hybridization technique and the ADD method, we develop the shADD process trough the following three-term relations:

(21)$\begin{array}{c}{x}_1=x\in R,\hfill \\ x_{n+1}=(1-{\alpha }_n)T{x}_n+{\alpha }_{n}T{y}_n=(1-{\alpha }_n)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n)+{\alpha }_n(y_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n),\hfill \\ y_n={\alpha }_n{x}_n+(1-{\alpha }_n)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n),\hfill & n\in \mathbb{N}.\hfill \end{array}$

Before we state and prove that the three-termed process (21), rewritten in a merged form, presents an accelerated gradient descent method, we induce the following two important terms.

Proposition 1

(Second-order necessary conditions—unconstrained case [22]). Let $x^{*}$ be an interior point of the set Ω, and suppose that $x^{*}$ is a relative minimum point over Ω of the function $f\in {\mathbb{C}}^2$. Then,

• $\nabla f\left(x^{*}\right)=0$,

• for all $\mathit{d},{\mathit{d}}^T{\nabla }^{2}f\left(x^{*}\right)\mathit{d}\ge 0$.

Proposition 2

(Second-ordered sufficient conditions—unconstrained case [22]). Let $f\in {\mathbb{C}}^2$ be a function defined in a region in which the point $x^{*}$ is an interior point. Suppose in addition that

• $\nabla f\left(x^{*}\right)=0$,

• Hessian of $f,F\left(x^{*}\right)$, is positive definite.

Then, $x^{*}$ is a strict relative minimum point of f.

Lemma 1.

The accelerated gradient iterative form of the shADD process (21) is given by the following relation:

(22) $x_{n+1}=x_n-(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]$

Proof. 

The merged iterative rule of the $shADD$ process (21) can be derived by substituting the expression of $y_n$ from (21) into the previous relation of the same three-term method, i.e., the one that defines $x_{n+1}$:

$\begin{array}{cc}{x}_{n+1}& =(1-{\alpha }_n)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n)\\ & +{\alpha }_n[{\alpha }_n{x}_n+(1-{\alpha }_n)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n)+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n]\\ & =(1-{\alpha }_n)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n)+{\alpha }_n^2{x}_n\\ & +{\alpha }_n(1-{\alpha }_n)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n)-{\alpha }_n{\gamma }_n^{-1}{t}_n{\mathbf{g}}_n+{\alpha }_n{t}_n^2{d}_n\\ & =(1-{\alpha }_n)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n)(1+{\alpha }_n)+{\alpha }_n^2{x}_n-{\alpha }_n{t}_n({\gamma }_n^{-1}{\mathbf{g}}_n-t_n{d}_n)\\ & =(1-{\alpha }_n^2)(x_n+t_n^2{\mathbf{d}}_n-t_n{{\gamma }_n}^{-1}{\mathbf{g}}_n)+{\alpha }_n^2{x}_n-{\alpha }_n{t}_n({\gamma }_n^{-1}{\mathbf{g}}_n-t_n{\mathbf{d}}_{\mathbf{n}})\\ & =x_n-t_n{\gamma }_n^{-1}{\mathbf{g}}_n+t_n^2{\mathbf{d}}_{\mathbf{n}}-{\alpha }_n^2{x}_n+{\alpha }_n^2{t}_n{\gamma }_n^{-1}{\mathbf{g}}_n-{\alpha }_n^2{t}_n^2{d}_n+{\alpha }_n^2{x}_n-{\alpha }_n{t}_n({\gamma }_n^{-1}{\mathbf{g}}_n-t_n{\mathbf{d}}_{\mathbf{n}})\\ & =x_n-t_n({\gamma }_n^{-1}{\mathbf{g}}_n-t_n{\mathbf{d}}_{\mathbf{n}})(1-{\alpha }_n^2+{\alpha }_n),\end{array}$

which proves (22).

Now, we show that Method (22) fulfills the gradient descent property. For this purpose, let us rewrite relation (22) as follows:

$x_{n+1}=x_n+t_n{D}_n,$

where

(23)$D_n=-(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n].$

Knowing that $\left\{{\alpha }_n\right\}\in (0,1)$ implies $1+{\alpha }_n-{\alpha }_n^2>1$. Further, ${{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n$ can be considered as a linear combination of the gradient vector, since the vector direction ${\mathbf{d}}_n$ is derived by Algorithm 2. With that, the parameter ${\gamma }_n$, as an acceleration parameter, is a positive constant. Therefore, direction $D_n$ is the gradient descent vector.

Now, we derive the iterative value of the acceleration parameter for Method (22). To achieve this goal, we use the second-order Taylor series of the objective function f:

$\begin{array}{cc}f\left(x_{k+1}\right)& \approx f\left(x_k\right)-g_k^T(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]\\ & +{\displaystyle \frac{1}{2}}{\left(1+{\alpha }_k-{\alpha }_k^2\right)}^2{(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}^T{\nabla }^{2}f\left(\xi \right)(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}}),\end{array}$

where $\xi$ satisfies the following:

$\xi \in [x_k,x_{k+1}],\xi =x_k+\beta (x_{k+1}-x_k)=x_k-\beta \left(1+{\alpha }_k-{\alpha }_k^2\right)(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}}),0\le \beta \le 1.$

Instead of the function’s Hessian ${▽}^{2}f\left(\xi \right)$, we use the diagonal scalar matrix approximation in the previous Taylor expression, i.e., acceleration matrix ${\gamma }_{k+1}I$:

$\begin{array}{cc}f\left(x_{k+1}\right)& \approx f\left(x_k\right)-g_k^T(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]\\ & +{\displaystyle \frac{1}{2}}{\left(1+{\alpha }_k-{\alpha }_k^2\right)}^2{(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}^T{\gamma }_{k+1}(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}}),\end{array}$

This gives us the expression of the acceleration parameter ${\gamma }_{k+1}^{shADD}$ of the $shADD$ process:

(24)${\gamma }_{k+1}^{shADD}=2{\displaystyle \frac{\left(f\left(x_{k+1}\right)-f\left(x_k\right)\right)-\left(1+{\alpha }_k-{\alpha }_k^2\right){\mathbf{g}}_{\mathbf{k}}^T(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}{{\left(1+{\alpha }_k-{\alpha }_k^2\right)}^2{(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}^T(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}}.$

We assume the positiveness of the derived acceleration parameter ${\gamma }^{shADD}$. This fact confirms that the second-order necessary and sufficient conditions have been fulfilled. In the case of ${\gamma }_{k+1}^{shADD}<0$, we assign ${\gamma }_{k+1}^{shADD}=1$ and derive the next iterative point as

$x_{k+2}=x_{k+1}-(1+{\alpha }_n-{\alpha }_n^2)t_n[{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n].$

Knowing that $\left\{{\alpha }_n\right\}\subset (0,1)$ induces $1+{\alpha }_{k+1}-{\alpha }_{k+1}^2>0$, together with the fact that $0<t_{k+1}<1,$ confirms that the previous scheme is the gradient descent method. □

We end this section by exposing the algorithm of the shADD method, derived on the basis of the previously provided analysis.

Taking the initial values $0<\rho <1$, $0<\tau <1$, $x_0$, ${\gamma }_0^{shADD}=1$, the algorithm of the shADD method is given by the following steps:

1. Set $k=0$, compute $f\left(x_0\right)$, $g_0$, and take ${\gamma }_0^{shADD}=1$;

2. If $\parallel g_k\parallel <ϵ$, then go to Step 9; else, continue to Step 3;

3. Apply the backtracking algorithm to calculate the iterative step length $t_k$;

4. Compute the first vector direction $s_k$ using Algorithm 1;

5. Compute the second vector direction $d_k$ using Algorithm 2;

6. Compute $x_{k+1}$ using the iterative rule (22);

7. Determine the acceleration parameter ${\gamma }_{k+1}^{shADD}$ using (24);

8. If ${\gamma }_{k+1}^{shADD}<0$, then take ${\gamma }_{k+1}^{shADD}=1$;

9. Set $k:=k+1$, go to Step 2;

10. Return $x_{k+1}$ and $f\left(x_{k+1}\right)$.

3. Convergence Features of the shADD Method

We start this section with some relevant known statements that can be found in [23,24].

Proposition 3.

If the function $f:R^n\to R$ is twice continuously differentiable and uniformly convex on ${\mathbb{R}}^n$, then:

1. the function f has a lower bound on $L_0=\{x\in {\mathbb{R}}^n|f\left(x\right)\le f\left(x_0\right)\}$, where $x_0\in {\mathbb{R}}^n$ is available;

2. the gradient g is Lipschitz continuous in an open convex set B that contains $L_0$, i.e., there exists $L>0$ such that

   (25) $\parallel g\left(x\right)-g\left(y\right)\parallel \le L\parallel x-y\parallel ,\forall x,y\in B.$

Lemma 2.

Under the assumptions of Lemma 3, there exist real numbers m, M satisfying the following:

(26) $0<m\le 1\le M,$

such that $f\left(x\right)$ has an unique minimizer $x^{*}$ and

(27) ${m\parallel y\parallel }^2\le y^T{▽}^{2}f\left(x\right)y\le M{\parallel y\parallel }^2,\forall x,y\in {\mathbb{R}}^n;$

(28) ${\displaystyle \frac{1}{2}}m\parallel x-x^{*}{\parallel }^2\le f\left(x\right)-f\left(x^{*}\right)\le {\displaystyle \frac{1}{2}}M{\parallel x-x^{*}\parallel }^2,\forall x\in {\mathbb{R}}^n;$

(29) ${m\parallel x-y\parallel }^2\le {(g\left(x\right)-g\left(y\right))}^T(x-y)\le M{\parallel x-y\parallel }^2,\forall x,y\in {\mathbb{R}}^n;$

Depending on the degree of complexity that a particular non-linear problem may have, the examination of its convergence resorts to establishing convergence on specific sets. Therefore, we expose in this section the convergence analysis of the derived $shADD$ process on the set of strictly convex quadratic functions. The general expression of the strictly convex quadratics is given by (30).

(30)$f\left(x\right)={\displaystyle \frac{1}{2}}{x}^{T}Ax-b^{T}x.$

In (30), A is the real positive definite symmetric matrix, and $b\in {\mathbf{R}}^n$. Further on, we use the following notations regarding the relevant eigenvalues of matrix A: ${\lambda }_1\le {\lambda }_2\le \dots {\lambda }_n.$

Previous research showed that for the strictly convex quadratic an adequate relation, usually, a connection between the smallest and the largest eigenvalues must be fulfilled in order to establish the convergence of the objective optimization method [2,21,25,26]. In the next lemma, we define that connection by applying the $shADD$ method.

Lemma 3.

The relation between the smallest and largest eigenvalues of symmetric positive definite matrix $A\in R^{n\times n}$ that defines the strictly convex quadratic function (30) to which the $shADD$ method (22) is applied is given as follows:

(31) ${\lambda }_1\le {\displaystyle \frac{{\gamma }_{k+1}}{t_{k+1}}}\le {\displaystyle \frac{2{\lambda }_n}{\beta }},k\in N,$

where β is the parameter defined in the backtracking procedure.

Proof. 

To prove (31), we start with the estimation of the difference of the function (30) values in two successive points:

$\begin{array}{cc}f\left(x_{n+1}\right)-f\left(x_n\right)& ={\displaystyle \frac{1}{2}}{x}_{n+1}^{T}A{x}_{n+1}-b^T{x}_{n+1}-{\displaystyle \frac{1}{2}}{x}_n^{T}A{x}_n+b^T{x}_n\\ & ={\displaystyle \frac{1}{2}}{[x_n-(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]]}^{T}A\\ & [x_n-(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]]\\ & -b^T[x_n-(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]-{\displaystyle \frac{1}{2}}{x}_n^{T}A{x}_n+b^T{x}_n\\ & ={\displaystyle \frac{1}{2}}{x}_n^{T}A{x}_n-{\displaystyle \frac{1}{2}}(1+{\alpha }_n-{\alpha }_n^2)t_n{[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]}^{T}A{x}_k\\ & -{\displaystyle \frac{1}{2}}{x}_k^T(1+{\alpha }_n-{\alpha }_n^2)t_{n}A[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]\\ & +{\displaystyle \frac{1}{2}}{(1+{\alpha }_n-{\alpha }_n^2)}^2{t}_n^2{[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]}^{T}A[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]\\ & -b^T{x}_n+b^T(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]-{\displaystyle \frac{1}{2}}{x}_n^{T}A{x}_n+b^T{x}_n\\ & =-{\displaystyle \frac{1}{2}}(1+{\alpha }_n-{\alpha }_n^2)t_n{[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]}^T[A{x}_n-b]\\ & -{\displaystyle \frac{1}{2}}(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n][A{x}_n^T-b^T]\\ & +{\displaystyle \frac{1}{2}}{(1+{\alpha }_n-{\alpha }_n^2)}^2{t}_n^2{{\gamma }_n}^{-2}{\mathbf{g}}_n^{T}A{g}_n-{\displaystyle \frac{1}{2}}(1+{\alpha }_n-{\alpha }_n^2)t_n^3{{\gamma }_n}^{-1}{{\mathbf{d}}_n}^{T}A{g}_n\\ & -{\displaystyle \frac{1}{2}}{(1+{\alpha }_n-{{\alpha }_n}^2)}^2{t_n}^3{{\gamma }_n}^{-1}{{\mathbf{g}}_n}^{T}A{d}_n+{\displaystyle \frac{1}{2}}(1+{\alpha }_n-{{\alpha }_n}^2){t_n}^4{d_n}^{T}A{d}_n\\ & =\left({\displaystyle \frac{1}{2}}(1+{\alpha }_n-{\alpha }_n^2)t_n{[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]}^{T}A-{g_n}^T\right)(1+{\alpha }_n-{{\alpha }_n}^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]\end{array}$

The expression above, which describes the difference between function’s values for two successive points, is determined based on the following facts:

• Matrix A is symmetric, so

  $g_k^{T}A{d}_k=d_k^{T}A{g}_k;$

• The gradient of Function (30) is

  (32)$g_k=A{x}_k-b.$

We now replace the derived difference in the acceleration parameter expression (24):

$\begin{array}{cc}{\gamma }_{k+1}^{shADD}& =2{\displaystyle \frac{\left(f\left(x_{k+1}\right)-f\left(x_k\right)\right)-\left(1+{\alpha }_k-{\alpha }_k^2\right){\mathbf{g}}_{\mathbf{k}}^T(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}{{\left(1+{\alpha }_k-{\alpha }_k^2\right)}^2{(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}^T(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}}\\ & =2{\displaystyle \frac{\left(\left(\frac{1}{2}(1+{\alpha }_n-{\alpha }_n^2)t_n{[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]}^{T}A-g_n^T\right)(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]\right)}{{\left(1+{\alpha }_k-{\alpha }_k^2\right)}^2{(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}^T(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}}\\ & -2{\displaystyle \frac{\left(1+{\alpha }_k-{\alpha }_k^2\right){\mathbf{g}}_{\mathbf{k}}^T(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}{{\left(1+{\alpha }_k-{\alpha }_k^2\right)}^2{(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}^T(t_k^2{\mathbf{d}}_n-t_k{\gamma }_k^{-1}{\mathbf{g}}_{\mathbf{k}})}}\\ & ={\displaystyle \frac{{\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}^{T}A\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}{{\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}^T\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}}.\end{array}$

The obtained expression

${\displaystyle \frac{{\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}^{T}A\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}{{\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}^T\left({\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n\right)}}$

confirms that the acceleration parameter ${\gamma }_{k+1}^{shADD}$ can be written as the Rayleigh quotient of the real symmetric positive definite matrix evaluated at the vector ${\gamma }_n^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n.$ This fact results in the following conclusion:

(33)${\lambda }_1\le {\gamma }_{k+1}\le {\lambda }_n,k\in N.$

According to findings revealed in [21], the value of the iterative step length of the accelerated gradient method derived via the backtracking inexact algorithm satisfies the following:

(34)$t_n>{\displaystyle \frac{\beta (1-\sigma ){\gamma }_n}{L}},$

where L is the Lipschitz constant that figures in Proposition (3), so the following is valid:

(35)${\displaystyle \frac{{\gamma }_n}{t_n}}<{\displaystyle \frac{L}{\beta (1-\sigma )}}.$

Considering relation (32), which defines the gradient of the strictly convex function, we have the following:

$\begin{array}{cc}\parallel g\left(x\right)-g\left(y\right)\parallel & =\parallel Ax-b-Ay+b\parallel \\ & =\parallel (Ax-Ay)\parallel =\parallel A(x-y)\parallel \\ & \le \parallel A\parallel \parallel x-y\parallel \\ & ={\lambda }_n\parallel x-y\parallel .\end{array}$

The previous relation confirms that the largest eigenvalue of the symmetric matrix A fulfills the property of the Lipschitz constant L in (34). Additionally, according to the limitations of the backtracking parameters $\sigma$ and $\beta$$(0<\sigma <0.5),\beta \in (\sigma ,1)$, we derive the following estimations:

${\displaystyle \frac{{\gamma }_{n+1}}{t_{n+1}}}<{\displaystyle \frac{L}{\beta (1-\sigma )}}={\displaystyle \frac{{\lambda }_n}{\beta (1-\sigma )}}<{\displaystyle \frac{{\lambda }_n}{\beta ·\frac{1}{2}}}={\displaystyle \frac{2{\lambda }_n}{\beta }},$

which confirms the right side of Estimation (31). Based on (33) and the fact that the iterative step size is less than 1, the first inequality of (31) arises. □

On the basis of proven estimations (31) relating to the acceleration parameter, backtracking parameter, and the lowest and the largest eigenvalues of the symmetric, positive definite matrix A that figures in the expression (30), using the following theorem, we establish the convergence of the $shADD$ method on the set of strictly convex quadratics.

Theorem 1.

For the strictly convex quadratic function (30), the process (22) is linearly convergent when ${\lambda }_n<2{\lambda }_1$. More precisely, the following relations are valid:

• for some real constants $p_1^k,p_2^k,\dots ,p_n^k$ and $q_1^k,q_2^k,\dots ,q_n^k$, such that

  (36) $g_k=\sum _{i=1}^n{p}_i^k{v}_i,d_k=\sum _{i=1}^n{q}_i^k{v}_i,$

  When the vectors $v_i,i\in (1,\dots ,n)$ represent the orthonormal set of eigenvectors of matrix A, the following inequations are fulfilled:

  (37) ${\left(p_i^{k+1}\right)}^2\le {\delta }^2{\left(p_i^k\right)}^{2}and{\left(q_i^{k+1}\right)}^2\le {\lambda }_n^2{\left(q_i^k\right)}^2,$

  including

  (38) $\delta =max\left\{1-{\displaystyle \frac{\beta {\lambda }_1}{2{\lambda }_n}},{\displaystyle \frac{{\lambda }_n}{{\lambda }_1}}(1+{\alpha }_k-{\alpha }_k^2)-1\right\}.$

• For the gradient (32) of the function (30), the following is valid:

  (39) $\underset{k\to \infty }{lim}\parallel g_k\parallel =0$

Proof. 

Taking the expression of Gradient (32) of Function (30) at the ($n+1$)-th iteration, we obtain the following:

$\begin{array}{cc}{g}_{n+1}& =A{x}_{n+1}-b=A(x_n-(1+{\alpha }_n-{\alpha }_n^2)t_n[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n])-b\\ & =A{x}_n-b-(1+{\alpha }_n-{\alpha }_n^2)t_{n}A[{{\gamma }_n}^{-1}{\mathbf{g}}_n-{\mathbf{d}}_n{t}_n]\\ & =g_n-(1+{\alpha }_n-{\alpha }_n^2)t_{n}A{{\gamma }_n}^{-1}{\mathbf{g}}_n+(1+{\alpha }_n-{\alpha }_n^2)t_n^{2}A{\mathbf{d}}_n\\ & =\left(I-(1+{\alpha }_n-{\alpha }_n^2)t_n{\gamma }_n^{-1}A\right)g_n+(1+{\alpha }_n-{\alpha }_n^2)t_n^{2}A{d}_n.\end{array}$

Applying the orthonormal representations (36) in the previous equation leads us to the following:

(40)$g_{k+1}=\sum _{i=1}^n\left(1-(1+{\alpha }_k-{\alpha }_k^2)t_k{\gamma }_k^{-1}{\lambda }_i\right)p_i^k{v}_i+(1+{\alpha }_k-{\alpha }_k^2)t_k^2\sum _{i=1}^n{\lambda }_i{q}_i^k{v}_i.$

Knowing that $\left|{\lambda }_i\right|\le {\lambda }_n,i\in \{1,2,\dots ,n\},$ we will prove (38) by showing that

$|1-(1+{\alpha }_k-{\alpha }_k^2)t_k{\gamma }_k^{-1}{\lambda }_i|<1.$

For this purpose, let us first assume that ${\lambda }_i<{(1+{\alpha }_k-{\alpha }_k^2)}^{-1}{t}_k^{-1}{\gamma }_k$, i.e.,

${\lambda }_i<{\displaystyle \frac{{\gamma }_k}{(1+{\alpha }_k-{\alpha }_k^2)t_k}}.$

Applying (31), we obtain the following:

$1>{\displaystyle \frac{{\lambda }_i(1+{\alpha }_k-{\alpha }_k^2)t_k}{{\gamma }_k}}\ge {\displaystyle \frac{{\lambda }_1{t}_k}{{\gamma }_k}}\ge {\displaystyle \frac{\beta {\lambda }_1}{2{\lambda }_n}}.$

We rewrite the previous inequalities as follows:

(41)$1-{\displaystyle \frac{{\lambda }_i(1+{\alpha }_k-{\alpha }_k^2)t_k}{{\gamma }_k}}\le 1-{\displaystyle \frac{\beta {\lambda }_1}{2{\lambda }_n}}\le \delta .$

We assume now the opposite case:

${\lambda }_i>{\displaystyle \frac{{\gamma }_k}{(1+{\alpha }_k-{\alpha }_k^2)t_k}}.$

The last inequality gives

$1<{\displaystyle \frac{{\lambda }_i(1+{\alpha }_k-{\alpha }_k^2)t_k}{{\gamma }_k}}\le {\displaystyle \frac{{\lambda }_n(1+{\alpha }_k-{\alpha }_k^2)}{{\lambda }_1}},$

which directly implies

(42)$|1-{\displaystyle \frac{{\lambda }_i(1+{\alpha }_k-{\alpha }_k^2)t_k}{{\gamma }_k}}|\le |{\displaystyle \frac{{\lambda }_n}{{\lambda }_1}}(1+{\alpha }_k-{\alpha }_k^2)-1|\le \delta .$

Estimations (41) and (42) prove (38).

Finally, in order to prove (39), we use the gradient representation from (36),

$g_k=\sum _{i=1}^n{p}_i^k{v}_i,$

which results in the following conclusion:

(43)$\parallel g_k{\parallel }^2=\sum _{i=1}^n{\left(p_i^k\right)}^2.$

Applying the fact that $\delta \in (0,1)$ on inequalities (37) directly proves (39). □

Non-Convex Case Overview

In the previous section, we proved that the shADD method linearly converges to a set of strictly convex quadratics. Although it is not the main subject of this research, in this subsection, we analyze a possible application of the presented scheme when the objective function is non-convex. The importance of providing this introductory discussion on this topic simply arises from the endless array of contemporary non-convex problems such as matrix completion, low-rank models, tensor decomposition, and deep neural networks.

Neural networks, considered as universal function approximators, contain significant symmetric properties. These features define them as non-convex structures. Some of the known techniques for solving machine learning problems and other non-convex problems are as follows:

• Stochastic gradient descent methods,

• Mini batch approach,

• Stochastic variance reduced gradient (SVRG) method,

• Alternating minimization methods,

• Branch and bound methods.

Confirming convergence properties in non-convex optimization is quite difficult. In a theoretical sense, there exist no regular approaches to achieving this goal, as is the case of convex problems. Additionally, there are potentially many local minimums and the existence of saddle points and flat regions when the objective function is non-convex.

Generally, when solving non-convex optimization tasks, theoretical guarantees are very weak, and there is no tried and tested way for ending this process successfully.

Principal component analysis (PCA) is a technique for linear dimensionality reduction, which is useful in proving global convergence of minimization methods when applied on non-convex functions. We propose connecting this approach with the shADD method in further studies. The PCA process can be characterized through the following steps:

• Standardizing the range of continuous initial variables;

• Computing the covariance matrix to identify correlations;

• Computing the eigenvectors and eigenvalues of the covariance matrix to identify the principal components;

• Creating a feature vector to decide which principal components to keep;

• Recasting the data along the principal components axes.

We set the goal problem as follows: determine the dominant eigenvector and eigenvalue of a positive symmetric semidefinite matrix A. We can write this problem as follows:

(44)$u_1=arg\underset{x}{max}{\displaystyle \frac{x^{T}Ax}{x^{T}x}}.$

The equivalent of problem (44) is (45):

(45)$\sqrt{{\lambda }_1}{u}_1=arg\underset{x}{min}{\parallel x{x}^T-A\parallel }_F^2,$

where ${\parallel ·\parallel }_F$ is the Frobenius norm, i.e., ${\parallel B\parallel }_F={\sum }_i{\sum }_j{B}_{i,j}^2$. Taking the objective function, defined in terms of the Frobenius norm,

(46)$f\left(x\right)={\displaystyle \frac{1}{4}}{\parallel x{x}^T-A\parallel }_F^2,$

we see that the gradient of this function is given by the following expression:

(47)$\nabla f\left(x\right)=\parallel x{x}^T-A\parallel x.$

The classical gradient descent update step for Function (46) can be written as follows:

(48)$xn+1=x_n-c_n(x_n{x}_n^T{x}_n-A{x}_n),$

where the adaptive step size parameter fulfills the following relation:

(49)$c_n={\displaystyle \frac{\eta }{1+\eta x_n^T{x}_n}}$

Applying (49) in (48) leads to the following:

(50)$\begin{array}{cc}{x}_{n+1}& =x_n-{\displaystyle \frac{\eta }{1+\eta x_n^T{x}_n}}(x_n{x}_n^T{x}_n-A{x}_n)\\ & =x_n-{\displaystyle \frac{\eta }{1+\eta x_n^T{x}_n}}{x}_n{x}_n^T{x}_n+{\displaystyle \frac{\eta }{1+\eta x_n^T{x}_n}}A{x}_n\\ & =\left(1-{\displaystyle \frac{\eta }{1+\eta x_n^T{x}_n}}{x}_n{x}_n^T\right)x_n+{\displaystyle \frac{\eta }{1+\eta x_n^T{x}_n}}A{x}_n\\ & ={\displaystyle \frac{x_n+\eta A{x}_n}{1+\eta x_n^T{x}_n}}={\displaystyle \frac{1}{1+\eta x_n^T{x}_n}}(I+\eta A)x_n.\end{array}$

After inductively taking the previous relation, we conclude that

(51)$x_N=(I+\eta A)x_0\prod _{t=0}^{T-1}{\displaystyle \frac{1}{1+\eta \parallel x_n{\parallel }^2}}.$

The previous relation (51) confirms that the gradient descent iteration (48) converges linearly, since

(52)${\displaystyle \frac{x_N}{\parallel x_n\parallel }}={\displaystyle \frac{{(I+\eta A)}^T{x}_0}{{\parallel (I+\eta A)}^T{x}_0\parallel }}.$

A similar analysis can be applied to the shADD iteration (22) for Function (46). According to the construction of the vector $d_k$ (Algorithm 2) in (22), we can modify this vector direction as a linear combination of the gradient vector, as explained in the proof of Lemma 1. Considering this fact allows us to rewrite iteration (22) in a simpler form for which Property (52) can be easily proved.

4. Numerical Test Results

In this section, we analyze the numerical performance of the shADD method depending on the choice of parameter $\alpha$ (18), which is aptly named the corrective parameter. For the selected values of this parameter, we track standard numerical metrics, including the number of iterations performed, CPU time, and the number of function evaluations.

As proposed in ref. [27], which presents an extensive comparative analysis of several Khan-hybrid models, for a range of ${\alpha }_k$ values (18), we take a specific numerical value ${\alpha }_k\equiv \alpha \in (0,1)$ for all $k\in \{1,2,3,\dots \}$. This further reinforces the corrective expression of the shADD iteration (22):

$c\left(\alpha \right)=1+\alpha -{\alpha }^2\in (1,2).$

We have observed that for specific values of parameter $\alpha \in (0,1)$, we have the following values of the expression $c\left(\alpha \right):$

(53)$\begin{array}{c}c\left(0.1\right)=1.09=c\left(0.9\right)\\ c\left(0.2\right)=1.16=c\left(0.8\right)\\ c\left(0.3\right)=1.21=c\left(0.7\right)\\ c\left(0.4\right)=1.24=c\left(0.6\right)\\ c\left(0.5\right)=1.25.\end{array}$

All of this motivated us to test the shADD method for these five specified values of $\alpha$. For this purpose, we selected five test functions from [28]. We tested these functions for the five given values of the corrective parameter $\alpha \in \{0.1,0.2,0.3,0.4,0.5\}$ and for ten different values of the number of variables $n\in \{1000,2000,3000,4000,5000,6000,7000,8000,9000,\mathrm{10,000}\}$. For each test function, we summarized the obtained outcomes for all selected numbers of variables. The results obtained from the measured performance metrics (number of iterations, CPU time, and number of evaluations) are presented in Table 1, Table 2, and Table 3, respectively.

We can observe that for the first test function, the Extended Penalty function, the values of the output results regarding the number of iterations and the number of evaluations do not depend on changes in the corrective parameter $\alpha$. For the same function, the changes in CPU time for different values of the corrective parameter are also minimal. However, for the other test functions, there are differences in the final values of all measured metrics depending on the choice of the corrective parameter value. In terms of metrics, regarding the number of iterations, the best results are achieved for $\alpha =0.2$ and $\alpha =0.3$. In the case of measuring CPU time, tests for $\alpha =0.1$ and $\alpha =0.2$ take the least time. In terms of the number of evaluations, the smallest values are achieved for $\alpha =0.2$ and $\alpha =0.3$. A general conclusion we can draw, based on a total of 250 tests, is that it is advisable to use a corrective parameter value of $\alpha =0.2$ or $\alpha =0.3$.

The tests were conducted using a standard termination criterion:

$\parallel g_k\parallel \le {10}^{-6}\mathrm{and}{\displaystyle \frac{|f\left(x_{k+1}\right)-f\left(x_k\right)|}{1+\left|f\right(x_k\left)\right|}}.$

The code was written in the C++ programming language.

5. Conclusions

In this paper, we propose a new s-hybrid variant of the accelerated double-direction minimization model. The explored convergence properties of the developed iterative rule on the set of strictly convex quadratic functions confirm that the method has linear consistency.

Numerical tests were performed for different values of the corrective parameter. This study leaves an open space for further investigations of the numerical performance of the defined process and comparative analysis regarding similar models.

Author Contributions

Conceptualization, V.R. and M.J.P.; methodology, V.R.; software, M.J.P.; validation, V.R. and M.J.P.; formal analysis, V.R. and M.J.P.; investigation, M.J.P.; resources, V.R.; data curation, V.R. and M.J.P.; writing—original draft preparation, V.R. and M.J.P.; writing—review and editing, V.R.; visualization, M.J.P.; supervision, V.R and M.J.P.; project administration, M.J.P.; funding acquisition, V.R. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

The data supporting this study are available from the authors upon request.

Acknowledgments

The author Milena J. Petrović gratefully acknowledges support from the Project supported by Ministry of Science, Technological Development and Innovation of the Republic of Serbia project no. 451-03-65/2024-03/200123.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Tables

Table 1

Number of iterations with respect to the corrective parameter value.

Test Functions	$\mathit{\alpha }=0.1$	$\mathit{\alpha }=0.2$	$\mathit{\alpha }=0.3$	$\mathit{\alpha }=0.4$	$\mathit{\alpha }=0.5$
Extended Penalty function	60	60	60	60	60
Diagonal 1 function	54	70	93	81	87
Diagonal 3 function	190	155	166	177	223
Generalized Tridiagonal 1 function	128	120	120	120	120
Quadratic Diagonal Perturbed function	2588	2407	1455	1618	3779

Table 2

CPU with respect to the corrective parameter value.

Test Functions	$\mathit{\alpha }=0.1$	$\mathit{\alpha }=0.2$	$\mathit{\alpha }=0.3$	$\mathit{\alpha }=0.4$	$\mathit{\alpha }=0.5$
Extended Penalty function	5	3	5	5	4
Diagonal 1 function	3	5	6	6	6
Diagonal 3 function	10	12	14	19	17
Generalized Tridiagonal 1 function	10	9	10	10	10
Quadratic Diagonal Perturbed function	321	200	249	175	294

Table 3

Number of evaluations with respect to the corrective parameter value.

Test Functions	$\mathit{\alpha }=0.1$	$\mathit{\alpha }=0.2$	$\mathit{\alpha }=0.3$	$\mathit{\alpha }=0.4$	$\mathit{\alpha }=0.5$
Extended Penalty function	3729	3729	3729	3729	3729
Diagonal 1 function	13,979	13,785	19,634	14,440	14,870
Diagonal 3 function	7140	4289	3741	9486	7767
Generalized Tridiagonal 1 function	1053	1006	1013	1019	1027
Quadratic Diagonal Perturbed function	8962	8419	5563	6052	12,535

References

1. Djuranović-Miličić, N.I.; Gardašević-Filipović, M. A multi-step curve search algorithm in nonlinear optimization: Nondifferentiable case. Facta Univ. Ser. Inform.; 2010; 25, pp. 11-24.

2. Petrović, M.J.; Stanimirovic, P.S. Accelerated Double Direction Method For Solving Unconstrained Optimization Problems. Math. Probl. Eng.; 2014; 2014, 965104. [DOI: https://dx.doi.org/10.1155/2014/965104]

3. Armijo, L. Minimization of functions having Lipschitz first partial derivatives. Pac. J. Math.; 1966; 6, pp. 1-3. [DOI: https://dx.doi.org/10.2140/pjm.1966.16.1]

4. Wolfe, P. Convergence conditions for ascent methods. SIAM Rev.; 1968; 11, pp. 226-235. [DOI: https://dx.doi.org/10.1137/1011036]

5. Goldstein, A.A. On steepest descent. SIAM J. Control; 1965; 3, pp. 147-151.

6. Petrović, M. A Truly Third Order Finite Volume Scheme on Quadrilateral Mesh. Master’s Thesis; Lund University: Lund, Sweden, 2006.

7. Artebrant, R.; Schroll, H.J. Conservative Logarithmic Reconstruction and Finite Volume Methods. SIAM J. Sci. Comput.; 2005; 27, pp. 294-314. [DOI: https://dx.doi.org/10.1137/03060240X]

8. Artebrant, R.; Schroll, H.J. Limiter-free Third Order Logarithmic Reconstruction. SIAM J. Sci. Comput.; 2006; 28, pp. 359-381. [DOI: https://dx.doi.org/10.1137/040620187]

9. Artebrant, R. Third order acurate non-polynomial reconstruction on ractangular and triangular meshes. J. Sci. Comput.; 2007; 30, pp. 193-221. [DOI: https://dx.doi.org/10.1007/s10915-005-9063-7]

10. Schroll, H.J.; Svensson, F. A Bi-Hyperbolic Finite Volume Method on Quadrilateral Meshes. J. Sci. Comput.; 2006; 26, pp. 237-260. [DOI: https://dx.doi.org/10.1007/s10915-004-4927-9]

11. Potra, F.A.; Shi, Y. Efficient line search algorithm for unconstrained optimization. J. Optim. Theory Appl.; 1995; 85, pp. 677-704. [DOI: https://dx.doi.org/10.1007/BF02193062]

12. Andrei, N. An acceleration of gradient descent algoritham with backtracing for unconstrained optimization. Numer. Algorithms; 2006; 42, pp. 63-173. [DOI: https://dx.doi.org/10.1007/s11075-006-9023-9]

13. Andrei, N. An accelerated conjugate gradient algorithm with guaranteed descent and conjugacy conditions for unconstrained optimization. Optim. Methods Softw.; 2012; 27, pp. 583-604. [DOI: https://dx.doi.org/10.1080/10556788.2010.501379]

14. Fletcher, R.; Reeves, C.M. Function minimization by conjugate gradients. Comput. J.; 1964; 7, pp. 149-154. [DOI: https://dx.doi.org/10.1093/comjnl/7.2.149]

15. Dai, Y.H.; Yuan, J.Y.; Yuan, Y. Modified two-point step-size gradient methods for unconstrained optimization. Comput. Optim. Appl.; 2002; 22, pp. 103-109. [DOI: https://dx.doi.org/10.1023/A:1014838419611]

16. Dai, Y.H.; Yuan, Y. Alternate minimization gradient method. IMA J. Numer. Anal.; 2003; 23, pp. 377-393. [DOI: https://dx.doi.org/10.1093/imanum/23.3.377]

17. Polak, E.; Ribiére, G. Note sur la convergence de méthodes de directions conjuguées. Rev. Fr. d’Inform. Rech. Opér. Sér. Rouge; 1969; 16, pp. 35-43. [DOI: https://dx.doi.org/10.1051/m2an/196903R100351]

18. Petrović, M.J.; Rakočević, V.; Ilić, D. Hybrid optimization models based on S-iteration process. Filomat; 2024; 38.

19. Sahu, D.R. Fixed points of demicontinuous nearly Lipschitzian mappings in Banach spaces. Comment. Math. Univ. Carol.; 2005; 46, pp. 653-666.

20. Agarwal, R.P.; O’Regan, D.; Sahu, D.R. Iterative construction of fixed points of nearly asymptotically nonexpansive mappings. J. Nonlinear Convex Anal.; 2007; 8, 61.

21. Stanimirović, P.S.; Miladinović, M.B. Accelerated gradient descent methods with line search. Numer. Algorithms; 2010; 54, pp. 503-520. [DOI: https://dx.doi.org/10.1007/s11075-009-9350-8]

22. Luenberg, D.G.; Ye, Y. Linear and Nonlinear Programming; Springer Science+Business Media, LLC: New York, NY, USA, 2008.

23. Ortega, J.M.; Reinboldt, W.C. Iterative Solution of Nonlinear Equation in Several Variables; Academic: London, UK, 1970.

24. Rockafellar, R.T. Convex Analysis; Princeton University Press: Princeton, NJ, USA, 1970.

25. Long, J.; Hu, X.; Zhang, L. Improved Newton’s method with exact line searches to solve quadratic matrix equation. J. Comput. Appl. Math.; 2008; 222, pp. 645-654. [DOI: https://dx.doi.org/10.1016/j.cam.2007.12.018]

26. Zhou, Q. An adaptive nonmomotonic trust region method with curlinear searches. J. Comput. Math.; 2006; 24, pp. 761-770.

27. Rakočević, V.; Petrović, M.J. Comparative analysis over accelerated models for solving unconstrained optimization problems with application of Khan’s hybrid rule. Mathemathics; 2022; 10, 4411. [DOI: https://dx.doi.org/10.3390/math10234411]

28. Andrei, N. An Unconstrained Optimization Test Functions Collection. Adv. Model. Optim.; 2008; 10, pp. 1-15. Available online: https://camo.ici.ro/journal/vol10/v10a10.pdf (accessed on 7 February 2025).