A Class of Three-Dimensional Subspace Conjugate Gradient Algorithms for Unconstrained Optimization

The conjugate gradient method is one of the most important methods used for solving large-scale unconstrained problems, because of its simple structure, lower computation, storage, fast convergence, etc. The general unconstrained optimization problem is as follows: where $f:{\mathbb{R}}^n\to \mathbb{R}$ is continuously differentiable. The function value of $f\left(x\right)$ at $x_k$ is denoted as $f_k$, and its gradient is expressed as $g_k$. Let ${\alpha }_k$ be the step size; we have the following iteration form for conjugate gradient method: where $d_k$ is the search direction, which has the form of where ${\beta }_k\in \mathbb{R}$, referred to as the conjugate parameter. For different selections of ${\beta }_k$, there are several well-known nonlinear conjugate gradient methods [1,2,3,4,5,6]: where $\parallel ·\parallel$ represents the Euclidean norm, and $y_k=g_{k+1}-g_k$.

The step size ${\alpha }_k$ can be obtained in different ways. Zhang and Hager [7] proposed an effective non-monotone Wolfe line search as follows:

The $C_k$ in the Formula (4) is the convex combination of $f_0,f_1,\cdots ,f_k$. $0<\delta <\sigma <1,C_0=f_0,Q_0=1$, $C_{k+1}$ and $Q_{k+1}$ are updated by the following rule: where $0\le {\eta }_{min}\le {\eta }_k\le {\eta }_{max}\le 1$.

The generalized non-monotone line search in [8] is composed of Formula (5) and where $0<\delta <\sigma <1,$ and

For large-scaled optimization problems, some researchers have been looking for more efficient algorithms. In 1995, Yuan and Stoer [9] first proposed the method of embedding subspace technology into the conjugate gradient algorithm framework, namely the two-dimensional subspace minimization conjugate gradient method (SMCG for short). The search direction is calculated by minimizing the quadratic approximation model on the two-dimensional subspace ${\Omega }_{k+1}=Span\{g_{k+1},s_k\}$, namely where ${\mu }_k$ and ${\nu }_k$ are parameters, and $s_k=x_{k+1}-x_k$. Analogously, the calculation of the search direction is directly extended to $Span\{g_{k+1},s_k,s_{k-1}\}$. By this way, we can avoid solving the sub-problem in the total space, which can reduce the computation and storage cost immensely.

Inspired by SMCG, some researchers began to investigate the algorithm of the conjugate gradient method combined with subspace technology. Dai et al. [10] focused on the analysis of the subspace minimization conjugate gradient method proposed by Yuan and Stoer  [9] and integrated SMCG with Barzilai–Borwein [11], a new Barzilai–Borwein conjugate gradient method (BBCG for short) was proposed. In the subspace ${\Omega }_{k+1}=Span\{g_{k+1},s_k\}$, Li et al. [12] discussed the case where the search direction was generated by minimizing the conic model when the non-quadratic state of the objective function was stronger. Wang et al. [13] changed the conic model of [12] into the tensor model. Zhao et al. [14] discussed the case of regularization model. Andrei [15] further expanded the search direction, developed it into a three-dimensional subspace ${\Omega }_{k+1}=Span\{-g_{k+1},s_k,y_k\}$, and proposed a new SMCG method (TTS). Inspired by Andrei, Yang et al. [16] carried out a similar study. They applied the subspace minimization technique to another special three-dimensional subspace ${\Omega }_{k+1}=Span\{g_{k+1},s_k,s_{k-1}\}$, and obtained a new SMCG method (STT). On the same subspace, Li et al. [17] further studied Yang’s results, analyzed the more complex three parameters, and proposed a new subspace minimization conjugate gradient method (SMCG_NLS). Yao et al. [18] proposed a new three-dimensional subspace ${\Omega }_{k+1}=Span\{g_{k+1},s_k,g_k\}$ and obtained the TCGS method by using the modified secant equation.

According to [19], it can be seen that the key to embedding subspace technology into the conjugate gradient method is to construct an appropriate subspace, select an approximate model, and estimate the terms of the Hessian matrix. The subspace ${\Omega }_{k+1}=Span\{-g_{k+1},s_k,y_k\}$ contains the gradient of the two iteration points. If the difference between the two gradient points is too large, the direction of the gradient change $y_k$ and its value will be affected. We consider making appropriate corrections to the gradient changes of the two iteration points, and then combine the current iteration point gradient with the previous search direction to form a new three-dimensional subspace, and whether this subspace is valuable for research. This paper is taking its as the breakthrough point for research.

In this paper, to avoid the situation in which the changes of the gradient $y_k=g_{k+1}-g_k$ dominate the subspace $Span\{g_{k+1},d_k,y_k\}$, inspired by [20], we construct a similar subspace ${\Omega }_{k+1}=Span\{g_{k+1},s_k,y_k^{*}\}$ in which $y_k^{*}=g_{k+1}-\frac{\parallel g_{k+1}\parallel }{\parallel g_k\parallel }{g}_k$, and then, by solving the optimal solution of an approximate model of the objective function in the given subspace to gain the corresponding parameters and algorithm. It can be shown that the obtained method is a global convergent and has nice numerical performance.

The rest of this paper is organized as follows: in Section 2, the search direction constructed on a new special three-dimensional subspace ${\Omega }_{k+1}$ is presented, and the estimations of matrix-vector production are given. In Section 3, The proposed algorithm and its properties under two necessary assumptions are described in detail. In Section 4, we establish the global convergence of our proposed algorithm under mild conditions. In Section 5, we compare the proposed method numerically with algorithms SMCG_NLS [17] and SMCG_Conic [12]. Finally, in Section 6, we conclude this paper and highlight future work.

The main content of this section is to introduce four search direction models and the selections of initial step sizes on the newly spanned three-dimensional subspace.

This section describes the obtained algorithm and its descending properties under two necessary assumptions in detail.