Global Convergence of an Extended Descent Algorithm without Line Search for Unconstrained Optimization ()
1. Introduction
Consider an unconstrained optimization problem (UP)
(1)
where
is a continuously differentiable function. In general, the iterative algorithms for solving (UP) usually take the form:
(2)
where
and
are current iterative point, a positive step length and a search direction, respectively. For simplicity, we denote
by
and
by
.
The main task in the iterative formula (2) is to choose search direction
and determine step length
along the direction. There are many classic methods to choose search direction
, such as the steepest descent methods, Newton-type methods, Variable metric methods (see [1] ), and conjugate gradient methods
(3)
where
is a parameter (see [2] [3] [4] ). For step length
, it is usually determined by line search procedure, such as exact line search, Wolfe line search, Armijo line search, and so on. However, these line search procedures may involve extensive computation of objective functions and its gradients, which often becomes a significant burden for large-scale problems. Evidently, it is a good idea that line search procedure is avoided in algorithm design in order to reduce the evaluations of objective functions and gradients.
Based on the above consideration, some authors have started to study the algorithms without line search. Recently, some conjugate gradient algorithms without line search were investigated. In [5] , Sun and Zhang studied some well-known conjugate gradient methods without line search, for instance, Fletcher-Reeves method, Hestenes-Stiefel method, Dai-Yuan method, Polak- Ribière method and Conjugate Descent method. In [6] , Chen and Sun researched a two-parameter family of conjugate gradient methods without line search. In [7] [8] , Wang and Zhu put forward to conjugate gradient path methods without line search. Shi, Shen and Zhou proposed descent methods without line search in [9] and [10] , respectively. Further, Zhou presented the steepest descent algorithm without line search in [11] .
Inspired by the above literatures, in this paper we will extend the descent algorithm without line search of [10] to more general case, and discuss its global convergence. The rest of this paper is organized as follows. In Section 2, we describe the extended descent algorithm without line search. In Section 3, we analyze its global convergence. Further, we generalize the search direction to more general form, and obtain global convergence of corresponding algorithm. Finally, numerical results are reported in Section 4.
2. Extended Descent Algorithm
To proceed, we first assume that [2]
(H1) The function f has lower bound on
, where
is available.
(H2) The gradient g is Lipschitz continuous in an open convex set
that contains
, i.e., there exists
such that
(4)
Now we give the extended algorithm.
Algorithm 2.1. Given a starting point
, a positive constant
, three
parameters
and
such that
,
. Let
.
Step 1. If
, then stop; otherwise go to Step 2.
Step 2. Compute
(5)
Step 3. Set search direction
(6)
Step 4. Compute step length by the following rule. When
,
is determined by Wolfe line search, i.e., it satisfies that
(7)
(8)
When
,
(9)
where
satisfies that
and
is a positive sequence which has a sufficient large upper bound.
Step 5. Set next iterative point
(10)
Step 6. Set
, and go to Step 1.
Remark 2.1. Note that the formula of
and
in Algorithm 2.1 are the generalized forms of those in [10] .
3. Global Convergence
Lemma 3.1. If Algorithm 2.1 generates an infinite sequence
, then all search directions
are descent, and
, it holds that
(11)
Proof. If
, it is obvious that
. If
, by (5) and (6), we have
(12)
This completes the proof. ,
Lemma 3.2 (Mean value theorem, see [1] ). Suppose that the objective function
is continuously differentiable on an open convex set
, then
(13)
where
,
. If
is twice continuously differentiable on
, then
(14)
and
(15)
Lemma 3.3.
,
(16)
Proof. Where
, it holds that
by (5). Then
, we have
Using induction principle and noting that
, it yields that
Therefore (16) holds. The proof is completed. ,
Theorem 3.1. If (H1), (H2) hold, and Algorithm 2.1 generates an infinite sequence
, then
(17)
and
(18)
Proof. When
, from (13), (4), Lemma 3.1, Lemma 3.3 and
, it yields that
(19)
which implies that
is a decreasing sequence. And it is clear that the sequence
generated by Algorithm 2.1 is contained in
by (H1), and there exists a constant
such that
. Therefore
Thus
which combining with (19) yields
(20)
Since
has an upper bound, (17) holds.
On the other hand, by (9) and Lemma 3.1, we have
(21)
By the same analysis as the above proof, (18) holds. The proof is completed. ,
Lemma 3.4 (see [12] ). If the conditions in Theorem 3.1 hold and
, then both the sequence
and
have a bound.
Theorem 3.2. If the conditions in Theorem 3.1 hold, then
(22)
Proof. Suppose
, then there exists a positive
such that
(23)
In the following, we carry out our proofs in two cases.
Case 1. We complete the proof by utilizing reduction to absurdity. Suppose that
. By (17), we have
(24)
From Lemma 3.4, we know that there exists
such that
. Combining (23), we have
It is known that
So
(25)
which contradicts with (24). Therefore (22) holds.
Case 2. When
, the proof is the same as that in [10] and here is omitted.
It follows from the proofs of Case 1 and Case 2 that (22) holds. This completes the proof. ,
Remark 3.1. Search direction of Algorithm 2.1 can be extended to more general form as follows:
(26)
where the function
satisfies the following conditions(see [10] ):
a) It is continuous and strictly monotone increasing when
;
b)
and
;
c)
is continuous, strictly monotone increasing when
, and
Evidently, there are many functions satisfying the conditions (a)-(c). For
example,
,
,
, etc (see [10] ). We denote Algorithm
2.1 in which
is determined by (26) as Algorithm 3.1. By using proof technique of above Theorem 3.2, it is easy to get its convergence theorem.
4. Numerical Results
In this section, we report some preliminary numerical experiments. The test problems and their initial values are drawn from [13] .
In numerical experiment, we take the parameter
,and stop the iteration if the inequality
is satisfied. The detailed numerical results
are reported in Table 1, in which NI, NF and NG denote the total number of iterations, the total number of function evaluations and the total number of gradient evaluations, respectively. From Table 1, we can see the extended algorithm has good numerical results.
5. Conclusion
In this paper, we extended the descent algorithm without line search of [10] to more general case, and got its global convergence. Compared with [10] , the extended algorithm has more effective numerical perfermance, so it is effective. In the future, we will further research the descent algorithms without line search, and try to get some new descent algorithms without line search, which not only convergence globally, but also have good numerical results.
Acknowledgements
We gratefully acknowledge the scholarship fund of education department of Guangxi Zhuang autonomous region, Guangxi basic ability improvement project fund for the middle-aged and young teachers of colleges and universities (2017KY0068, KY2016YB069), Guangxi higher education undergraduate course teaching reform project fund (2017JGB147), NNSF of China (11761014), Guangxi natural science foundation (2017GXNSFAA198243).