close

Вход

Забыли?

вход по аккаунту

?

1.4932439

код для вставкиСкачать
A comparative study of three new conjugate gradient methods with exact line search
Mohamed Hamoda, Mohd Rivaie, Abdelrhaman Abshar, and Mustafa Mamat
Citation: AIP Conference Proceedings 1682, 020030 (2015);
View online: https://doi.org/10.1063/1.4932439
View Table of Contents: http://aip.scitation.org/toc/apc/1682/1
Published by the American Institute of Physics
Articles you may be interested in
A comparative study of two new conjugate gradient methods
AIP Conference Proceedings 1643, 616 (2015); 10.1063/1.4907502
A new classical conjugate gradient coefficient with exact line search
AIP Conference Proceedings 1739, 020082 (2016); 10.1063/1.4952562
A modification of classical conjugate gradient method using strong Wolfe line search
AIP Conference Proceedings 1739, 020071 (2016); 10.1063/1.4952551
A new steepest descent method with global convergence properties
AIP Conference Proceedings 1739, 020070 (2016); 10.1063/1.4952550
A Comparative Study of Three New Conjugate Gradient
Methods with Exact Line Search
Mohamed Hamodaa , Mohd Rivaieb , Abdelrhaman Absharc, Mustafa Mamatd
a,c
School of Informatics and Applied Mathematics, Universiti Malaysia Terengganu, 21030 Terengganu, Malaysia
a
ehmuda@yahoo.com, ctomcatkassala@yahoo.com
b
Department of Computer Science and Mathematics, Univesiti Teknologi MARA ,23000 Terengganu, Malaysia
b
rivaie75@yahoo.com
d
Department of Computational & Applied Mathematics, Faculty of Informatics and Computing, Universiti Sultan
Zainal Abidin, 22200 Terengganu, Malaysia
d
must@uniza.edu.my
Abstract. Conjugate Gradient methods play an important role in solving unconstrained optimization, especially for large
scale problems. In this paper, we compared the performance profile of the classical conjugate gradient coefficients
FR, PRP with three new E k . These three new E k possess global convergence properties using the exact line search.
Preliminary numerical results show that the three new E k are very promising and efficient when compared to CG
coefficients FR, PRP.
Keywords: Conjugate gradient method, exact line search, global convergence, large scale, unconstrained optimization.
PACS: 02.60.Pn, 02.60.Cb, 02.70.C
INTRODUCTION
Consider the unconstrained optimization problem:
min f ( x) , x  R n
(1)
where f : R n o R be bounded from below and a continuously differentiable function, and R n denotes an ndimensional Euclidean space. We use g(x) to denote the gradient of f at x . Conjugate gradient methods are
efficient for solving (1), especially when the dimension n is large. The conjugate gradient method for solving (1)
generates a sequence of iterates by letting,
(2)
xk 1 xk D k d k ,
k 0,1,2,...
where xk is current iterate point and D k is a step length, which is computed by carrying out some line search, and
d k is the search direction defined by
dk
­
° g k
®
°̄ g k E k d k 1
if
k
0,
if
k t 1,
(3)
where g k g ( xk ) and E k is a scalar. If the line search is exact, the step length D k is obtained in the direction d k
by the rule
D k a rg min f ( xk D d k )
(4)
D t0
Well-known conjugate gradient methods include the Hestenes-Stiefel (HS) [1], Fletcher – Reeves
(FR) [2], Polak-Ribiere-Polyak (PRP) [3,4], conjugate descent (CD) [5], Liu – Storey (LS) [6], and Dai –
Yuan (DY) [7]. The parameters E k of these methods are specified as follows:
E kHS
E kDY
g kT ( g k g k 1 )
T
( g k g k 1 ) d k 1
, E kFR
g kT g k
T
g k 1 g k 1
, E kPRP
g kT ( g k g k 1 )
g kT 1 g k 1
, E kCD
g kT g k
T
d k 1 g k 1
g kT g k
( g k g k 1 )T d k 1
The 22nd National Symposium on Mathematical Sciences (SKSM22)
AIP Conf. Proc. 1682, 020030-1–020030-6; doi: 10.1063/1.4932439
© 2015 AIP Publishing LLC 978-0-7354-1329-0/$30.00
020030-1
,
E kLS
g kT ( g k g k 1 )
d kT1 g k 1
,
There has been much research on global convergence properties of these methods (e.g. [8,9,10,11,12,13]).
In this paper, we will show three new E k with another two classical methods in the next section. In the global
convergence analysis section we will discuss the sufficient descent condition and the global convergence. Then we
will present the numerical results and discussion. Finally, we will present the conclusions in the last section.
Three New E k Parameter and Algorithm
Here, we propose the three new formulas which is known as E kRMIL , E kRAMI and E kAMRI , where,
E kRMIL
g kT ( g k
g k 1 )
d k 1
2
,
E kRAMI
gk
g kT ( g k g k 1
gk )
and
d kT1 (d k 1 g k )
E kAMRI
gk
2
gk
g kT g k 1
g k 1
d k 1
2
More information on these methods can be found in [14,15,16], where the information of the two well
known classical formulas E kFR and E kPRP can be found in [2,3]. The following algorithm is a general algorithm for
solving optimization problems by Conjugate gradient methods.
Algorithm 1.
Step 1: Given x0  R n , H t 0, set d0 g0 if g 0 d H then stop.
Step 2: Compute D k by exact line search (4).
Step 3: Let xk 1 xk D k d k , g k 1 g ( xk 1 ). If g k 1 H then stop.
Step 4: Compute E k and generated d k 1 by (3).
Step 5: Set k k 1 go to Step 2.
Global Convergence Analysis
In this section, we will discuss the convergence properties of the new formulas with the exact line search.
Now we will begin with the sufficient descent condition.
Sufficient Descent Condition.
For the sufficient descent condition to hold,
g kT d k d c g k
2
for all k t 0 and c ! 0
(5)
The following theorem shows that E k formulas with exact line search possess the sufficient descent condition.
Theorem 1. Let {xk } and {d k } be sequence generated by the method of the form (2), (4) and (5) where the step size
D k is determined by the exact line search (4). Then (5) holds for all k t 0 .
Proof. We proof by induction, that if k 0 then,
g 0T d 0
c g 0
2
hence, the condition holds true, now we need to prove that: g kT d k d c g k
from (3) we have,
d k 1
multiply both sides by
2
for all k t 1
g k 1 E k 1d k
g kT1
g kT1 d k 1
g kT1 ( g k 1 E k 1 d k )
for exact line search, we know that g kT1 d k
g kT1 d k 1
g k 1
g k 1
2
E k 1 g kT1 d k
0 . Thus
2
(6)
hence this condition holds true for k 1. Therefore, the sufficient descent condition holds.
020030-2
Global Convergence Properties
The following assumption is often used in the studies of the conjugate gradient methods.
Assumption1
(i) f (x) is bounded from below on the level set : {x  R n , f ( x) d f ( x0 )} , where x0 is the starting point.
(ii) In some neighborhood N of :, f (x) is continuously differentiable, and its gradient is Lipschitz continuous,
that is, for all x, y  N , there exists a constant L ! 0 such that g ( x) g ( y ) d L x y .
The following lemma which is famous for global convergence properties is by Zoutendijk [8].
Lemma 1. Suppose assumption1 holds, let xk be generated by Algorithm1 and d k satisfy (5) then we have
f
4
gk
¦d
k 0
f
2
k
7KHSURRIRIWKLV/HPPDFDQEHVHHQLQ>@.
Theorem 2. Let the condition in Assumption1 holds true. The {xk } is generated by Algorithm1, D k is obtained by
the exact line search (4) and the sufficient descent condition hold true. Then
lim g k
k of
0
Proof. To prove this theorem, we will use the contradiction. That is, if Theorem 2 is not true, then there exist a constant c ! 0,
such that
for all k t 0
gk t c
(7)
from (3) we know that,
d k g k E k d k 1
squaring both sides of the equation, we obtain
dk
2
2
( E k ) 2 d k 1
2E k g kT d k 1 g k
2
for exact line search we know that g kT d k 1 0 , therefore
2
dk
2
gk
( E k ) 2 d k 1
2
(8)
we need to simplify the E kAMRI , so that the proof will be easier,
gk
2
gk
g kT g k 1
g k 1
E kAMRI
d k 1
d
2
gk
d k 1
2
2
(9)
substituting equation (9) into the equation (8), we have
2
dk
d gk
2
gk
d k 1
4
4
d k 1
2
(10)
4
dividing both sides of (10) by g k , we obtain
dk
2
gk
4
1
d
gk
2
1
g k 1
(11)
2
there fore,
dk
2
gk
4
k
d
¦g
i 1
1
i
(12)
2
then from (7) and (12) we get that
gk
4
dk
2
t
c2
k
this implies
020030-3
f
gk
¦d
k 1
4
2
f.
k
ZKLFKFRQWUDGLFWV=RXWHQGLMNFRQGLWLRQWKXVZHKDYH lim g k
k of
0 The proof is completed.
by same way we can prove this theorem for E kRMIL and E kRAMI , (see [14,15])
Numerical Results and Discussions
In this section, we report numerical results for the conjugate gradient methods FR, PRP, RMIL, RAMI and
AMRI . Twenty four test problems are selected from paper [17]. We considered H 105 and the gradient value as
the stopping criteria as Hillstrom [18] suggested that g k d H . Dimensions of the test problems lay in the range from
2 to 10000, also for each test function, we used four initial points, starting from a closer point to the solution and
moving on to the one that is furthest from it. A list of problem functions, dimensions and the initial points used are
shown in Table1. All problems are tested using MATLAB version 7.13.0.564 (R 2011b). We used the exact line
search to compute the step size. The CPU processor used was Intel(R) Core TM i3-M350 (2.27GHz), with RAM 4GB.
In some cases, the computation stopped due to the failure of the line search to find the positive step size, and thus it
was considered a failure. In addition, we considered a failure if the number of iterations exceeds 1000 or CPU time
exceeds 500 (Sec). Numerical results are compared relative to the number of iterations and CPU time. The
performance results are shown in Fig.1 and Fig.2 respectively, using a performance profile introduced by Dolan and
More [19].
TABLE (1). A list of problem functions
No
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Function
Dimension
Initial points
Three Hump
2
(-10,-10),(10,10),(20,20),(40,40)
Six Hump
2
(-10,-10),(-8,8),(8,8),(10,10)
Booth
2
(10,10),(25,25),(50,50),(100,100)
Treccani
2
(5,5),(10,10),(20,20),(50,50)
Zettl
2
(5,5),(10,10),(20,20),(50,50)
Diagonal 4
2,4, 10,100,500,1000
(1,..,1),(3,…,3),(6,…,6),(12,…,12)
Perturbed Quadratic
2,4, 10,100,500,1000
(1,…,1) ,(3,…,3) ,(5,…,5),(10,…,10)
Extended Himmelblau
10,100,500,1000,10000
(50,..,50) ,(70,..,70) ,(100,..,100),(125,…,125)
Extended Rosenbrock
2,4, 10,100,500,1000,10000 (13,…,13),(25,…,25),(30,…,30),(50,…,50)
Shallow
2,4, 10,100,500,1000,10000 (10,…10),(25,…,25),(50,…,50),(70,…,70)
Extended Tridiagonal 1
2,4, 10,100,500,1000,10000 (6,…,6),(12,…,12),(17,…,17),(20,…,20)
Generlyzed Tridiagonal 1
2,4,10,100
(7,…,7),(10,…,10), (13,…,13),(21,…,21)
Extended white & Holst
2,4,10,100,500,1000,10000
(3,…,3),(5,…,5) ,(7,…,7), (10,…,10)
Generalized Quartic
2,4,10,100,500,1000,10000
(1,…,1),(2,…,2),(5,…,5),(7,…,7)
Extended Powell
4,20,100,500,1000
(2,…,2),(4,…,4),(6,…,6),(8,…,8)
Extended Denschnb
2,4,10,100,500,1000,10000
(8,…,8),(13,…,13),(30,…,30),(50,50)
Hager
2,4,10,100
(7,…,7) ,(10,…,10), (15,…,15), (23,…,23)
Extended Penalty
2,4,10,100
(80,…,80),(10,..,100),(111,.,111),(150,…,150)
Quadrtic QF2
2,4,10,100,500,1000
(5,…,5) ,(20,…,20) ,(50,…,50) ,(100,…,100)
Ex - Quadratic Penalty QP2 2,4,10,100,500,1000
(10,…,10) ,(20,…,20), (30,…,30) ,(50,…,50)
Extended Beale
2,4,10,100,500,1000,10000
(-1,…,-1) ,(3,…,3) ,(7,…,7) , (10,…,10)
Diagonal 2
2,4,10,100,500,1000
(1,…,1) ,(5,…,5) ,(10,…,10),(15,…,15)
Raydan1
2,4,10,100
(1,…,1) ,(3,…,3) ,(7,…,7) , (10,…,10)
Sum Squares
2,4,10,100,500,1000
(1,…,1) ,(3,…,3) ,(7,…,7) , (10,…,10)
From our numerical results, we found that PRP and AMRI methods can solve 93.1% of test problems,
followed by the formula RAMI which can solve 92.2% of the problems, and RMIL method solves 91.4% , while
the FR method solves about 69.8% of the test problems. From figures 1 and 2, we can see that the performance of
RAMI and RMIL lies between PRP, AMRI and FR . Moreover, we can say that PRP and AMRI has the best
performance with respect to the number of iterations and CPU time since it’s corresponds to the top curves.
020030-4
1.0
0.8
PS(t)
0.6
0.4
FR
PRP
RMIL
RAMI
AMRI
0.2
0.0
5
10
15
20
25
t
FIGURE 1. Performance profile relative to the number of iterations.
1.0
0.8
PS(t)
0.6
0.4
FR
PRP
RMIL
RAMI
AMRI
0.2
0.0
10
20
30
t
FIGURE 2. Performance profile relative to the CPU time.
CONCLUSION
In this paper, we compare three new E k for unconstrained optimization with two classical E k . We found that
the methods PRP, AMRI , RAMI and RMIL , come out with best numerical results in their efficiency, more than the
classical conjugate gradient method FR .
Our future work will concentrate on studying the convergence properties of these methods using different
inexact line searches.
ACKNOWLEDGMENTS
The authors would like to thank the University of Malaysia Terengganu (Grant no GGP 68007/2013/86),
Alasmrya University of Libya and Red Sea University of Sudan.
020030-5
REFERENCES
1.
M. R. Hestenes, E. Stiefel. Method of conjugate gradient for solving linear equations, J. Res. Nat. Bur.Stand. 49, (1952), pp.
409-436
2. R. Fletcher, C. Reeves. Function minimization by conjugate gradients, Compute. J. 7, (1964), pp. 149–154.
3. B.T. Polyak. The conjugate gradient method in extreme problems, USSR Comp. Math. Phys. 9, (1969), pp. 94–112.
3. E. Polak, G. Ribie`re. Note Sur la convergence de directions conjuge`es, Rev. Francaise Informat Recherche Operationelle,
3e Anne`e 16 ,(1969), pp. 35–43.
5. Fletcher. Practical Method of Optimization, second ed. Unconstrained Optimization, vol. I, Wiley, New York,(1997).
6. Y. Liu, C. Storey. Efficient generalized conjugate gradient algorithms, part 1: theory, J. Optim.Theory Appl. 69, (1992), pp.
129–137.
7. Y. Dai, Y. Yuan. A nonlinear conjugate gradient with strong global convergence properties, SIAM J. Optim. 10, (2000), pp.
177–182.
8. G. Zoutendijk, Nonlinear Programming, in: J. Abadie (Ed.), Computational Methods, Integer and Nonlinear Programming,
North-Holland, Amsterdam, (1970), pp. 37–86.
9. M.J.D. Powell, Non-convex minimization calculation and the conjugate gradient method, Lecture Notes in Mathematics,
1066,Springer-Verlag, Berlin, (1984), pp. 122– 241.
10. M.J.D. Powell. Restart procedure for the conjugate gradient method, Math. Prog. 2, (1977), pp. 241–254.
11. D. Touati-Ahmed, C. Storey. Globally convergent hybrid conjugate gradient methods, J. Optim. Theory Appl. 64, (1990), pp.
379–397.
12. J.C. Gilbert, J. Nocedal. Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim.2,
(1992), pp.21– 42.
13. L. Zhang, W.J. Zhou, D.H. Li. Global convergence of a modified Fletcher–Revves conjugate gradient method with Armijotype line search, Numer. Math. 104, (2006), pp. 561–572.
14. M.Rivaie, M.Mamat, Leong Wah, Ismail.M. A new class of nonlinear conjugate gradient coefficient with global
convergence properties, Appl.Math.comput.218, (2012), pp. 11323-11332.
15. M. Rivaie, A. Abashar, M. Mamat, Ismail. M. The Convergence Properties of a New Type of Conjugate Gradient Methods,
Appl. Math. Sciences. Vol. 8, no.1, (2014), pp. 33 – 44.
16. A. Abashar, M. Mamat, M. Rivaie, Ismail. M. Global Convergence Properties of a New Class of Conjugate Gradient Method
for Unconstrained Optimization, Appl. Math. Sciences. Vol. 8, (2014), pp. 67, 3307 – 3319.
17. N. Andrei. An unconstrained optimization test functions collection, Adv. Modell. Optim. 10, (1977), pp. 147–161.
18. K.E. Hilstrom. A simulation test approach to the evaluation of nonlinear optimization algorithms, ACM. Trans. Math.
Softw. 3, (1977), pp. 305–315.
19. E. Dolan, J.J.More. Benchmarking optimization software with performance profile, Math. Prog. 91, (2002), pp. 201–213.
020030-6
Документ
Категория
Без категории
Просмотров
1
Размер файла
257 Кб
Теги
4932439
1/--страниц
Пожаловаться на содержимое документа