© Wuhan University 2024

0 Introduction

Unconstrained optimization methods are widely used in the fields of nonlinear

dynamic systems and engineering computation to obtain the numerical solution of the optimal control problem^[1,2]. In this paper, we consider the following unconstrained optimization problem:

$\mathrm{m}\mathrm{i}\mathrm{n}f\left(\mathit{x}\right),\mathit{x}\in {\mathbb{R}}^n,$(1)

where $f:{\mathbb{R}}^n\to \mathbb{R}$ is sufficiently smooth high-dimensional function. The nonlinear conjugate gradient (CG) methods are highly useful for solving this kind of problem because they can avoid storing and remembering matrices^[3,4]. In general, the iterative formula of the CG method is obtained by

${\mathit{x}}_{k+\mathrm{1}}={\mathit{x}}_k+{\alpha }_k{\mathit{d}}_k,$(2)

where ${\alpha }_k$ is step size along the search direction ${\mathit{d}}_k$, and ${\mathit{d}}_k$ defined by

${\mathit{d}}_k=\{\begin{array}{cc}-{\mathit{g}}_k& ,k=\mathrm{1},\\ -{\mathit{g}}_k+{\beta }_k{\mathit{d}}_{k-\mathrm{1}}& ,k\ge \mathrm{2},\end{array}$(3)

where ${\mathit{g}}_k$ denotes the gradient $\nabla f({\mathit{x}}_k)$. ${\beta }_k$ is scalar and it is chosen differently so that there are different CG methods corresponding to the different ${\beta }_k$. Some well-known formulas for ${\beta }_k$ are given by

${\beta }_k^{\mathrm{H}\mathrm{S}}=\frac{{\mathit{g}}_k^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}$(Hestenes-Stiefel (HS) method^[5]),

${\beta }_k^{\mathrm{F}\mathrm{R}}=\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}$(Fletcher-Reeves (FR) method^[6]),

${\beta }_k^{\mathrm{P}\mathrm{R}\mathrm{P}}=\frac{{\mathit{g}}_k^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}$(Polak-Ribiere-Polyak (PRP) method^[7]),

${\beta }_k^{\mathrm{C}\mathrm{D}}=-\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{g}}_{k-\mathrm{1}}}$ (Conjugate Descent (CD) method^[8]),

${\beta }_k^{\mathrm{L}\mathrm{S}}=\frac{{\mathit{g}}_k^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{-{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{g}}_{k-\mathrm{1}}}$(Liu -Storey (LS) method^[9]),

and

${\beta }_k^{\mathrm{D}\mathrm{Y}}=\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}$(Dai and Yuan (DY) method^[10]),

where $\Vert ·\Vert$ is Euclidean norm and "T" stands for the transpose,${\mathit{y}}_{k-\mathrm{1}}={\mathit{g}}_k-{\mathit{g}}_{k-\mathrm{1}}$. In general, DY and FR methods based on inexact line search have good convergence performance, but the computational efficiency is not as good as that of PRP method. In order to establish methods with both good numerical performance and convergence properties, many scholars have proposed improved conjugate gradient methods in recent years^[11-14]. They showed that the method is globally convergent if the following strong Wolfe line search conditions for ${\alpha }_k$ are satisfied,

$\{\begin{array}{c}f({\mathit{x}}_k+{\alpha }_k{\mathit{d}}_k)-f({\mathit{x}}_k)\le \rho {\alpha }_k{{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_k\\ \left|g({\mathit{x}}_k+{\alpha }_k{\mathit{d}}_k{)}^{\mathrm{T}}{\mathit{d}}_k\right|\le -\sigma {{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_k\end{array},$(4)

where $\mathrm{0}<\rho <\sigma <\mathrm{1}$.

The line search in the conjugate gradient method is usually chosen by a strong Wolfe line search, however, the line search skill usually brings computational burden, especially in solving large-scale nonlinear unconstrained optimization problem. To overcome this problem, Sun and Zhang^[3] introduced five CG methods respectively without line search in which the line search step is replaced by a simple step size formula ${\alpha }_k$:

${\alpha }_k=\frac{-\delta {\mathit{g}}_k^{\mathrm{T}}{\mathit{d}}_k}{{\Vert {\mathit{d}}_k\Vert }_{{\mathit{Q}}_k}^{\mathrm{2}}},$(5)

where ${\Vert {\mathit{d}}_k\Vert }_{{\mathit{Q}}_k}=\sqrt[]{{\mathit{d}}_k^{\mathrm{T}}{\mathit{Q}}_k{\mathit{d}}_k}$, $\delta \in \left(\mathrm{0},v_{\mathrm{m}\mathrm{i}\mathrm{n}}/\mu \right)$ is chosen such that $\delta \mu /v_{\mathrm{m}\mathrm{i}\mathrm{n}}<\mathrm{1}$, $\mu$ is Lipchitz constant defined in Assumption 1 below, and {Q_k} is a sequence of positive definite matrices satisfying for positive constants $v_{\mathrm{m}\mathrm{i}\mathrm{n}}>\mathrm{0}$ and $v_{\mathrm{m}\mathrm{a}\mathbf{x}}>\mathrm{0}$ such that $\forall$$\mathit{d}\in {\mathbb{R}}^n$, $v_{\mathrm{m}\mathrm{i}\mathrm{n}}{\mathit{d}}^{\mathrm{T}}\mathit{d}\le {\mathit{d}}^{\mathrm{T}}{\mathit{Q}}_k\mathit{d}\le v_{\mathrm{m}\mathrm{a}\mathbf{x}}{\mathit{d}}^{\mathrm{T}}\mathit{d}$.

Chen and Sun^[4] extended this technique to two-parameter family CG method, which can be deemed as generalization of the HS and LS without line search. Yu^[15] and Narushima^[16] applied this method to memory gradient method and obtained their global convergence, respectively. Yin and Chen^[17] showed that three-term CG methods without line search are globally convergence. Other modified CG methods without line search reader may see Refs.[18-20].

As supplementary of these results, in this paper, we continue their research and would show that the proposed CG method without line search in which the line search step is replaced by fixed step-length formula (5), is global convergence for following new ${\beta }_k$:

${\beta }_k=\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}},$(6)

where ${\omega }_k\ge \mathrm{0}$, ${\mu }_k\ge \mathrm{0}$. This motivation mainly comes from Refs.[3, 4]. Our main aim is to develop a new method and obtain better property of the new method while keeping its simple structure. It should be noted that the formula (6) includes some important special sub-classes. For example, when ${\omega }_k=\mathrm{0}$, ${\mu }_k=\mathrm{1},$ the proposed CG method can be deemed as DY method without line search; when ${\omega }_k=\mathrm{1}$, ${\mu }_k=\mathrm{0},$ the proposed CG method can be deemed as FR method without line search. Hence, the proposed CG method (6) without line search can be deemed as generalization of the DY and FR.

The rest of this paper is organized as follows. In Section 1, we first give some preliminary results on the CG method without line search and discuss our method sufficient descent property. Furthermore, we prove the global convergence of the proposed method without line search and present algorithm frame. A large amount of numerical experiments are given for illustrative purposes in Section 2. Conclusions appear in Section 3.

1 Analysis of Global Convergence and Algorithm Frame

1.1 Analysis of Global Convergence

We adopt the following assumption on function of which is commonly used in the literature.

Assumption 1^[3] The objective function $f$ is $\mathrm{L}{\mathrm{C}}^{\mathrm{1}}$ in a neighborhood $\mathrm{\Omega }$ of the level set $L:=\{\mathit{x}\in {\mathbb{R}}^n|f\left(\mathit{x}\right)\le f\left({\mathit{x}}_{\mathrm{1}}\right)\}$ and $L$ is bounded. Here, by $\mathrm{L}{\mathrm{C}}^{\mathrm{1}}$ we mean that the gradient $\nabla f\left(\mathit{x}\right)$ is Lipschitz continuous with modulus $\mu ,$i.e., there exist $\mu >\mathrm{0}$ such that

$\Vert \nabla f\left({\mathit{x}}_{k+\mathrm{1}}\right)-\nabla f\left({\mathit{x}}_k\right)\Vert \le \mu \Vert {\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\Vert$

for any ${\mathit{x}}_{k+\mathrm{1}},{\mathit{x}}_k\in \mathrm{\Omega }$.

Assumption 2^[3] The function $f$ is $\mathrm{L}{\mathrm{C}}^{\mathrm{1}}$ and strongly convex on $\mathrm{\Omega }$. In other words, there exists $\lambda >\mathrm{0}$ such that

${\left[\nabla f\left({\mathit{x}}_{k+\mathrm{1}}\right)-\nabla f\left({\mathit{x}}_k\right)\right]}^{\mathrm{T}}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\right)\ge \lambda {\Vert {\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\Vert }^{\mathrm{2}}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{y}{\mathit{x}}_{k+\mathrm{1}},{\mathit{x}}_k\in \mathrm{\Omega }.$

Lemma 1   Suppose that ${\mathit{x}}_k$ is given by (2), (3) and (5). Then

${{\mathit{g}}_{k+\mathrm{1}}}^{\mathrm{T}}{\mathit{d}}_k={\rho }_k{{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_k$(7)

holds for all k, where

${\rho }_k=\mathrm{1}-\frac{\delta {\varphi }_k{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}{{{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}_{Q_k}}$(8)

and

${\varphi }_k=\{\begin{array}{cc}\mathrm{0},& \mathrm{f}\mathrm{o}\mathrm{r}{\alpha }_k=\mathrm{0},\\ \frac{{\left({\mathit{g}}_{k+\mathrm{1}}-{\mathit{g}}_k\right)}^{\mathrm{T}}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\right)}{{\Vert {\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\Vert }^{\mathrm{2}}},& \mathrm{f}\mathrm{o}\mathrm{r}{\alpha }_k\ne \mathrm{0}.\end{array}$(9)

Proof   See Lemma 1 in Ref. [3].

Lemma 2   Suppose that Assumption 1 holds and that ${\mathit{x}}_k$ is given by (2), (3) and (5). Then

$\underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}}\Vert {\mathit{g}}_k\Vert \ne \mathrm{0}\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{s}\sum _{{\mathit{d}}_k\ne \mathrm{0}}\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}}{{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}<\mathrm{\infty }.$(10)

Proof   See Lemma 5 in Ref. [3].

Lemma 3   Suppose that Assumption 2 holds and ${\beta }_k$ is given by (6). Then ${{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_k\le -{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}$.

Proof   We prove Lemma 3 by induction. For $k=\mathrm{1}$, it is easy to obtain that ${\mathit{g}}_{\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{\mathrm{1}}=-{\Vert {\mathit{g}}_{\mathrm{1}}\Vert }^{\mathrm{2}}\le -{\Vert {\mathit{g}}_{\mathrm{1}}\Vert }^{\mathrm{2}}$. Suppose ${\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}\le -{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}$ holds, now we prove that ${\mathit{g}}_k^{\mathrm{T}}{\mathit{d}}_k\le -{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}$ holds.

By (3), (6) and Lemma 1, we have

$\begin{array}{l}{{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_k={{\mathit{g}}_k}^{\mathrm{T}}(-{\mathit{g}}_k+{\beta }_k{\mathit{d}}_{k-\mathrm{1}})\\ ={{\mathit{g}}_k}^{\mathrm{T}}\left(-{\mathit{g}}_k+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{\mathit{d}}_{k-\mathrm{1}}\right)\\ =-{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}\\ =-{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}+{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}\frac{{\rho }_{k-\mathrm{1}}{{\mathit{g}}_{k-\mathrm{1}}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}.\end{array}$

From Corollary 3 in Ref.[3], we know $\mathrm{0}<{\rho }_{k-\mathrm{1}}\le \mathrm{1}$. From the induction hypothesis, we have ${\rho }_{k-\mathrm{1}}{\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}\le -{\rho }_{k-\mathrm{1}}{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}\le \mathrm{0}$. Furthermore, one has

$\begin{array}{l}{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}={\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}\left({\mathit{g}}_k-{\mathit{g}}_{k-\mathrm{1}}\right)\\ ={\mu }_k({\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{g}}_k-{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{g}}_{k-\mathrm{1}})\\ ={\mu }_k({\rho }_{k-\mathrm{1}}{\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}-{\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}})\\ ={\mu }_k\left({\rho }_{k-\mathrm{1}}-\mathrm{1}\right){\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}\ge \mathrm{0},\end{array}$

which is due to ${\mu }_k\ge \mathrm{0}$, ${\rho }_{k-\mathrm{1}}-\mathrm{1}<\mathrm{0}$ and ${\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}\le \mathrm{0}$. From above analysis, we have

${\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}\frac{{\rho }_{k-\mathrm{1}}{{\mathit{g}}_{k-\mathrm{1}}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}\le \mathrm{0},$

where ${\omega }_k$ and ${\mu }_k$ are not equal to zero at the same time. Thus, we obtain ${{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_k=-{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}+{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}\frac{{\rho }_{k-\mathrm{1}}{{\mathit{g}}_{k-\mathrm{1}}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}\le -{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}$. This finishes our proof.

If there exists a constant $c>\mathrm{0}$ such that ${{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_k\le -c{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}$($k\ge \mathrm{1}$), then we say the search direction ${\mathit{d}}_k$ of the method satisfies the sufficient descent condition. Lemma 3 means that the search direction ${\mathit{d}}_k$ is the sufficient descent direction, which is often required in the convergence analysis of CG method.

Theorem 1   Suppose that Assumptions 1, 2 hold and that ${\beta }_k$ is given by (6). Then

$\frac{{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}}\le \frac{{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{4}}}+\frac{H}{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}},$

where $H$ is a positive constant.

Proof   By (3), we have

${\mathit{d}}_k=-{\mathit{g}}_k+{\beta }_k{\mathit{d}}_{k-\mathrm{1}},$

squaring both sides of it, we obtain

${\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}={\Vert -{\mathit{g}}_k+{\beta }_k{\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}$

By Lemma 1 and substituting the expression (6) into above formula, we have

$\begin{array}{l}{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}={\Vert -{\mathit{g}}_k+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}\\ ={\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}-\frac{\mathrm{2}{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{{\mathit{g}}_k}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}\\ +\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\left[{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}\right]}^{\mathrm{2}}}\end{array}$

$\begin{array}{l}={\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}-\frac{\mathrm{2}{\rho }_{k-\mathrm{1}}{{\mathit{g}}_{k-\mathrm{1}}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}\\ +\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\left[{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}\right]}^{\mathrm{2}}}\end{array}$

$\le {\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}\left|\mathrm{1}+\frac{\mathrm{2}{\rho }_{k-\mathrm{1}}{\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}}\right|$

$+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\left[{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}+{\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}\right]}^{\mathrm{2}}}$

$\le {\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}\left|\mathrm{1}+\frac{\mathrm{2}{\rho }_{k-\mathrm{1}}{\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}\right|+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\left[{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}\right]}^{\mathrm{2}}},$

which is due to ${\mu }_k{\mathit{d}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{y}}_{k-\mathrm{1}}>\mathrm{0}$ that is deduced in Lemma 3. By ${\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}\le -{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}$ in Lemma 3 , we have

$\frac{\mathrm{2}{\rho }_{k-\mathrm{1}}{\mathit{g}}_{k-\mathrm{1}}^{\mathrm{T}}{\mathit{d}}_{k-\mathrm{1}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}\le -\frac{\mathrm{2}{\rho }_{k-\mathrm{1}}{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}=-\frac{\mathrm{2}{\rho }_{k-\mathrm{1}}}{{\omega }_k}$

Now by $\mathrm{1}-\delta \mu /v_{\mathrm{m}\mathrm{i}\mathrm{n}}\le {\rho }_{k-\mathrm{1}}$ that is deduced in Ref. [3], and the two inequalities above, we obtain

$\begin{array}{l}{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}\le \left|\mathrm{1}-\frac{\mathrm{2}{\rho }_{k-\mathrm{1}}}{{\omega }_k}\right|{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\left[{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}\right]}^{\mathrm{2}}}\\ \le \left|\mathrm{1}-\frac{\mathrm{2}(\mathrm{1}-\delta \mu /v_{\mathrm{m}\mathrm{i}\mathrm{n}})}{{\omega }_k}\right|{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{{\omega }_k}^{\mathrm{2}}{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{4}}}.\end{array}$

Let $H=\left|\mathrm{1}-\frac{\mathrm{2}\left(\mathrm{1}-\delta \mu /v_{\mathrm{m}\mathrm{i}\mathrm{n}}\right)}{{\omega }_k}\right|$, we obtain

$\begin{array}{l}{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}\le H{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}+\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{4}}},\\ \frac{{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}}\le \frac{{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{4}}}+\frac{H}{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}.\end{array}$

The proof is completed. There holds $\mathrm{1}-\delta \mu /v_{\mathrm{m}\mathrm{i}\mathrm{n}}\le {\rho }_{k-\mathrm{1}}$ for all k if Assumption 1 is valid.

Theorem 2   Suppose that Assumptions 1, 2 hold and that sequence $\left\{{\mathit{x}}_k\right\}$ is given by (2), (3), (5) and (6). Then $\underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}}\Vert {\mathit{g}}_k\Vert =\mathrm{0}$.

Proof   Suppose, by contradiction, that the stated conclusion is not true. Then, in view of $\Vert {\mathit{g}}_k\Vert >\mathrm{0}$, there exists a constant $\epsilon >\mathrm{0}$, such that $\Vert {\mathit{g}}_k\Vert \ge \epsilon$ for all k, and by Theorem 1 we have $\frac{{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}}\le \frac{{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{4}}}+\frac{H}{{\epsilon }^{\mathrm{2}}}$.

Thus, we have a recursive equation which leads to

$\begin{array}{l}\frac{{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{4}}}\le \frac{{\Vert {\mathit{d}}_{k-\mathrm{1}}\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{1}}\Vert }^{\mathrm{4}}}+\frac{H}{{\epsilon }^{\mathrm{2}}}\le \frac{{\Vert {\mathit{d}}_{k-\mathrm{2}}\Vert }^{\mathrm{2}}}{{\omega }_k{\Vert {\mathit{g}}_{k-\mathrm{2}}\Vert }^{\mathrm{4}}}+\frac{\mathrm{2}H}{{\epsilon }^{\mathrm{2}}}\\ \le \cdots \le \frac{{\Vert {\mathit{d}}_{\mathrm{1}}\Vert }^{\mathrm{2}}}{{\omega }_{\mathrm{2}}{\Vert {\mathit{g}}_{\mathrm{1}}\Vert }^{\mathrm{4}}}+\frac{(k-\mathrm{1})H}{{\epsilon }^{\mathrm{2}}}.\end{array}$(11)

Thus, equation (11) means that

$\frac{{\Vert g_k\Vert }^{\mathrm{4}}}{{\Vert d_k\Vert }^{\mathrm{2}}}\le \frac{\mathrm{1}}{ab+(k-\mathrm{1})c}$(12)

where $a=\frac{\mathrm{1}}{{\omega }_{\mathrm{2}}}$, $b=\frac{{\Vert {\mathit{d}}_{\mathrm{1}}\Vert }^{\mathrm{2}}}{{\Vert {\mathit{g}}_{\mathrm{1}}\Vert }^{\mathrm{4}}}$ and $c=\frac{H}{{\epsilon }^{\mathrm{2}}}$, $a,b\mathrm{a}\mathrm{n}\mathrm{d}c$ are constants. From equation (12) we have $\sum _{{\mathit{d}}_k\ne \mathrm{0}}\frac{{\Vert {\mathit{g}}_k\Vert }^{\mathrm{2}}}{{\Vert {\mathit{d}}_k\Vert }^{\mathrm{2}}}=+\mathrm{\infty }$, which is contradictory to Lemma 2. Hence we obtain $\underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}}\Vert \mathit{g}{}_k{}^{}\Vert =\mathrm{0}$.

Theorem 2   denotes that our proposed CG method without line search possesses global convergence.

1.2 Algorithm Frame

Based on the discussion above, now we can describe the algorithm frame for solving the unconstrained optimization problem (1) as follows:

Step 0   Given an initial point ${\mathit{x}}_{\mathrm{0}}\in {\mathbb{R}}^n$, constants ${\epsilon }_{\mathrm{0}}>\mathrm{0}$, $\rho \in (\mathrm{0,1})$, $\sigma \in (\mathrm{0,1})$, ${\omega }_k\ge \mathrm{0}$, ${\mu }_k\ge \mathrm{0}$ and let $k:=\mathrm{0}$.

Step 1   If a stopping criterion $\Vert {\mathit{g}}_k\Vert <{\epsilon }_{\mathrm{0}}$ is satisfied, then stop; otherwise, go to Step 2.

Step 2   Compute a step size ${\alpha }_k$ by formula (6).

Step 3   Let ${\mathit{x}}_{k+\mathrm{1}}={\mathit{x}}_k+{\alpha }_k{\mathit{d}}_k$, compute ${\mathit{d}}_k$ and ${\beta }_k$ by (3) and (6).

Step 4   Let $k:=k+\mathrm{1}$ and go to Step 1.

From above algorithm, we note that the step-length ${\alpha }_k$ depends on the Lipschitz constant, but in general, the Lipschitz constant is not known in previously. It should be noted that if $f(\mathit{x})$ is a twice continuous differentiable strictly convex function, the Lipschitz constant can be replaced by a positive constant^[15]. So, we choose $\delta =\mathrm{1}$.

2 Numerical Experiments

In this section, in order to show the performance of the given method, we test our proposed method with fixed step-length (5) (denoted by OMFSL), method (6) with the strong Wolfe line search (4) (denoted by SSWLS), and some other considered algorithms without line search such as DY and FR method ^[3] and Chen and Sun's method^[4] via 24 test problems from Ref.[21]. We use the same convergence criteria in Ref.[21].

The parameters are chosen as $\rho =\mathrm{0.04}$, $\sigma =\mathrm{0.5}$,${\omega }_k=\mathrm{0.7}$ and ${\mu }_k=\mathrm{0.3}$. All codes are written in MATLAB 7.5 and ran on Lenovo with 1.90 GHz CPU processor, 2.43 GB RAM memory, and Windows XP operating system. In our numerical experiments the no-line-search method with Q_k=I (the unit matrix) show bad convergence behavior. Thus we consider BFGS updates for Q_k in formula (5).

The test results are shown in Tables 1 and 2. The results for each problem by each method are shown in the form of $k/\mathrm{N}\mathrm{G}/\mathrm{N}\mathrm{F}/f(\overline{\mathit{x}})/T_{\mathrm{c}\mathrm{p}\mathrm{u}}$, where $k,\mathrm{N}\mathrm{G},\mathrm{N}\mathrm{F},f(\overline{\mathit{x}}),T_{\mathrm{c}\mathrm{p}\mathrm{u}}$ denote the number of the iteration at the terminate iteration, the total number of calculations of the gradient value of the objective function, the total number of computations of the objective function value, the value of function at the terminate iteration, the CPU time in seconds, respectively. $n$ indicates the variable dimension of the test problems.

From Tables 1 and 2, it is easy to see that OMFSL performs better than other considering methods. Meanwhile, we presented the Dolan and Moré^[22] performance profiles for OMFSL and other considered methods. Note that the performance ratio $p(\tau )$ is the probability for a solver for the tested problems with the factor $\tau$ of the smallest cost. In Figs.1-5, the performance of OMFSL with fixed step-length (5) and other considered methods are presented.

Fig. 1 Performance profile on the absolute errors of $\mathit{f}(\overline{\mathit{x}})$ versus $\mathit{f}({\mathit{x}}^{\mathbf{*}})$

Fig. 2 Performance profile on the number of iteration

Fig. 3 Performance profile on the NG

Fig. 4 Performance profile on the NF

Fig. 5 Performance profile on the Tcpu

As we can see from Fig.1, OMFSL is superior to all other considering methods for the absolute errors of $f(\overline{\mathit{x}})$ versus $f({\mathit{x}}^{\mathrm{*}})$ (the function value at the optimal solution). Figures 2-5 shows that OMFSL is better than all other considered methods for the number of iteration, the number of gradient evaluations (NG), the number of function value evaluations (NF) and CPU time (T_cpu). In conclusion, we can see that OMFSL without line search is very competitive for the test problems, and OMFSL is alternative for solving nonlinear unconstrained optimization problems.

3 Conclusion

In this paper, we have combined a two-parameter conjugate gradient method defined by formula (6) with Sun-Zhang's step-length formula defined by formula (5) and have proved its global convergence property under the appropriate assumptions. This step-length formula (5) might be practical in case that the line search is expensive or hard. We allow certain flexibility in selecting the sequence {Q_k} in practical computation, and we also can consider other updates for Q_k. Our proofs require that the function is at least and the level set is bounded. Reducing the requirement of optimization function and finding completely constant step-length might be topic of further research.

References

All Tables

All Figures

	Fig. 1 Performance profile on the absolute errors of $\mathit{f}(\overline{\mathit{x}})$ versus $\mathit{f}({\mathit{x}}^{\mathbf{*}})$
In the text

	Fig. 2 Performance profile on the number of iteration
In the text

	Fig. 3 Performance profile on the NG
In the text

	Fig. 4 Performance profile on the NF
In the text

	Fig. 5 Performance profile on the Tcpu
In the text