## Perbandingan Hasil Numerik Metode Konjugat Gradien Hibrid Baru (Ls-Dy) Dan
Metode Hs-Cd

## T. Murdani Saputra
Prodi Matematika FMIPA, Universitas Syiah Kuala, tmurdanisaputra@unsyiah.ac.id

## Ikhsan Maulidi
Prodi Matematika FMIPA, Universitas Syiah Kuala, ikhsanmaulidi@unsyiah.ac.id

## Radhiah
Prodi Matematika FMIPA, Universitas Syiah Kuala, radhiah@unsyiah.ac.id
ABSTRAK ,  Metode  konjugat  gradien  merupakan  suatu metode untuk menyelesaikan sistem persamaan linier pada skala besar, yang mana metode tersebut diperkenalkan oleh Hestenes  dan  Stiefel  untuk  menyelesaikan  permasalahan tersebut.  Metode  konjugat  gradien  merupakan  metode iteratif dan juga merupakan salah satu metode yang efektif dalam  menyelesaikan  optimasi  tak  berkendala.  Dalam tulisan ini, penulis melakukan pengusulan metode konjugat gradien  hibrid  baru  berdasarkan  ide  dari  metode  NH1, NH2,  NH3  dan  NH4.  Metode  hibrid  tersebut  diusulkan berdasarkan  dari  kekurangan  dan  kelebihan  dari  metode sebelumnya  yaitu  metode  HS,  FR,  PRP,  CD,  LS  dan Metode  DY.  Kekurangan  dan  kelebihan  dari  metode- metode  tersebut  diantaranya  proses  kinerja  komputasi (iterasi)  kurang  baik  dan  kekonvergenan  global. Berdasarkan  dari  metode-metode  hibrid  yang  diusulkan tersebut  maka  penulis  mengusulkan  metode  baru  yaitu penggabungan dari metode LS dengan metode DY, dimana metode LS memiliki kelebihan pada kinerja komputasi dan DY kelebihannya pada kekonvergenan globalnya. Metode hibrid baru yang diusulkan tersebut yaitu metode NH5 (LS- DY)  dan  metode  yang  diusulkan  ini  akan  di  ujikan  pada fungsi  tak  linear  orde  tinggi.  Metode  baru  menunjukkan bahwa  fungsi-fungsi  yang  diberikan  dapat  diselesaikan dengan  sangat  efisien  serta  perbandingan  metode  NH5 dengan  metode-metode  sebelumnya  menunjukkan  hasil pada proses komputasinya baik dan dapat bersaing
Kata  Kunci:  metode  konjugat  gradien,  metode  hibrid, knerja komputasi.

## 1. PENDAHULUAN
Salah satu cara dalam menyelesaikan sistem persamaan  linear  adalah  dengan  menggunakan metode konjugate gradient, dimana cara tersebut diperkenalkan  oleh  Hestenes  dan  Stiefel  pada tahun  1952.  Metode  konjugat  gradient  juga merupakan salah satu metode yang efektif dalam menyelesaikan masalah optimasi tak berkendala, berikut masalah optimasi tak berkendala:
min 𝑓(𝑥), 𝑥 ∈ 𝑅 𝑛 (1) dengan 𝑅 𝑛 merupakan  notasi  dari  ruang Euclidean n-dimensi dan 𝑓: 𝑅 𝑛 → 𝑅 merupakan
fungsi turunan kontinu. Metode konjugat gradien merupakan  metode  iteratif  sehingga  persamaan (1.1)  dapat  diselesaikan  dengan  menggunakan persamaan berikut:
1 , 0,1, 2,..., k k k k x x d k  + = + = (2)
dimana 𝛼 𝑘 adalah ukuran langkah yang ditentukan dengan menggunakan line search dan 𝑑 𝑘 adalah  pencarian  arah  (descent  direction). Bentuk dari 𝛼 𝑘 yang merupakan ukuran langkah dimana  ukuran  tersebut  ditentukan  dengan menggunakan line search. Ukuran langkah yang biasa  digunakan  yaitu  exact  atau  inexact  line search  dimensi  satu.  Bentuk  dari  exact  line search sebagai berikut:
0 (x ) min ( ), k k k k k k f d f x d     + = + (3)
Sedangkan  bentuk  dari  inexact  line  search yang biasanya dikenal dengan kondisi armijo dan kondisi  curvature,  adapun  formula  tersebut sebagai berikut:
(x ) ( ) (x ) (x ) ( )     +  +   +   T k k k k k k k T T k k k k k k f d f x f d f d d f x d (4)
dengan 0 < 𝛿 < 𝜎 < 1 (Nocedal  &  Wright, 1999).  Dalam  penelitian  ini,  kondisi  yang digunakan adalah kondisi strong Wolfe. Kondisi tersebut merupakan kondisi armijo dan curvature yang dikenal dengan kondisi Wolfe. Kondisi lain yang  bisa  digunakan  dalam  mencari 𝛼 𝑘 adalah dengan  menggunakan  kondisi  strong  Wolfe, dimana bentuk kondisinya sebagai berikut:
(x ) ( ) (x ) (x ) ( )     +  +   +  −  T k k k k k k k T T k k k k k k f d f x f d f d d f x d (5)
dengan 0 < 𝛿 < 𝜎 < 1 [1]. Dalam penelitian ini, kondisi  yang  digunakan  adalah  kondisi  strong Wolfe.
Untuk  menentukan 𝑑 𝑘 yang  merupakan pencarian arah yang dalam hal ini menggunakan metode  konjugat  gradien  dapat  menggunakan bentuk berikut:
1 , 0 , 0 k k k k k g untuk k d g d untuk k  − − =  =  − +   (6)
dengan g k adalah  gradien  dari 𝑓 di 𝑥 𝑘 ,  dan 𝛽 𝑘 merupakan skalar yang ditentukan oleh beberapa bentuk berikut:
1 1 1 T HS k k k T k k g y d y  − − − = , 2 2 2 k FR k k g g  − = , 1 2 1 T PRP k k k k g y g  − − = 2 1 1 k CD k T k k g d g  − − = , 1 1 1 T LS k k k T k k g y d g  − − − = − , 2 1 1  − − = k DY k T k k g d y dengan 𝑦 𝑘−1 = g 𝑘 − g 𝑘−1 dan merupakan norm Vektor Euclid.
Metode  yang  dituliskan  di  atas  merupakan metode  yang  diperkenalkan  oleh  Hestenes- Stiefel (HS) [2], Fletcher-Reeves (FR) [3], Polak – Ribiѐre (PRP) [4] dan [5], Fletcher (Conjugate Descent  atau  CD)[6],  Liu-Storey  (LS)  [7],  dan Dai-Yuan (DY) [8]. Untuk  skalar tersebut yang dituliskan diatas memiliki beberapa kekurangan dan kelebihan pada proses kinerja komputasi dan kekonvergenan global. Metode PRP, HS dan LS merupakan  metode  yang  memiliki  kinerja komputasi lebih baik, sedangkan sifat konvergensi globalnya lemah. Disisi lain, metode FR,  CD  dan  DY  memenuhi  sifat  konvergensi globalnya kuat sedangkan hasil kerja komputasinya  tidak efisien yang mana tidak bisa bersaing dengan metode lain.
Metode  gabungan  tersebut  menunjukkan baik  dan  terpenuhi  sifat  konvergensi  globalnya dan juga baik dalam proses kinerja komputasinya[9]. Hal yang sama dilakukan oleh [10],  [11]  dan  [12]  yang  dimana  metode  yang diusulkan  adalah  metode  NH1,  NH2,  NH3  dan NH4. Metode tersebut menunjukkan bahwa baik pada  hasil  komputasi  dan  sifat  konvergensi globalnya kuat. Dalam artikelnya, [10] menggabungkan antara metode PRP dan metode FR dan modifikasi dari metode FR yaitu metode MFR, dimana metodenya sebagai berikut:
    1 max 0, min , H
PRP FR k k k    (7)
MFR: 1 1 2 1 T FR k k k k k k k k g d d g d g g  − − − = − + − 1 1 2 1 1 , T FR FR k k k k k k k g d g d g   − − −     = − + +     (8)
pada bentuk persamaan (1.8) [10] menggantikan bentuk FR k  dengan  bentuk
1 H k  sehingga diperoleh persamaan baru yaitu
1 1 1 1 2 1 1 T H H k k k k k k k k g d d g d g   − − −   = − +  +     (9)
Metode  tersebut  merupakan  metode  NH1, sedangkan untuk metode yang kedua yaitu NH2 juga  dilakukan  hal  yang  sama  yaitu  dengan menggabungkan  metode  HS  dan  DY  yang dituliskan dengan 1 H k  , bentuk tersebut kemudian  menggantikan  bentuk  DY  pada metode  MDY  [10]  dan  bentuk  metodenya sebagai berikut:
    2 max 0, min , H HS DY k k k    (10)
dan
MDY: 1 1 2 1 T DY k k k k k k k k g d d g d g g  − − − = − + − 1 1 2 1 1 T DY DY k k k k k k k g d g d g   − − −   = − +  +     (11)
Untuk metode NH2 yaitu
2 2 1 1 2 1 1 T H H k k k k k k k k g d d g d g   − − −   = − +  +     (12)
Metode  selanjutnya  yaitu  metode  NH3  dan NH4  diperoleh  dari  hal  yang  sama  juga  seperti yang dilakukan oleh [9] dan [10]. Dalam artikel [11]  mengusulkan  metode  modifikasi  dari metode  CD  yang  dikenal  diberi  nama  dengan metode  MCD.  Berdasarkan  dari  metode  MCD maka  [11]  mengusulkan  bentuk  metode  baru yaitu  metode  NH3  yang  merupakan  metode gabungan  antara  Metode  LS-  CD  dan  hal  yang juga  dilakukan  oleh  [12]  mengusulkan  metode NH4 merupakan gabungan metode HS-CD yang dimana  bentuk  tersebut  menggunakan  bentuk metode  MCD.  Bentuk  metodenya  sebagai berikut:
    3 max 0, min , H LS CD k k k    (13)
dan MCD: 1 1 2 1 T CD k k k k k k k k g d d g d g g  − − − = − + − 1 1 2 1 1 T CD CD k k k k k k k g d g d g   − − −   = − +  +     , (14)
dengan  menggantikan  bentuk  CD k ,  dengan bentuk  metode  H3,  diperoleh  bentuk  baru  yaitu metode NH3:
NH3: 3 3 1 1 2 1 1   − − −   = − +  +     T H H k k k k k k k k g d d g d g , (15)
dan untuk metode H4 dan NH4 sebagai berikut
H4:     4 max 0, min ,    H HS CD k k k ,            (16) dan
NH4: 4 4 1 1 2 1 1   − − −   = − +  +     T H H k k k k k k k k g d d g d g , (17)
Metode-  metode  tersebut  yang  telah  diusulkan memenuhi  bentuk  descent  yaitu g k T 𝑑 𝑘 = −‖g 𝑘 ‖ 2 .
Berdasarkan  ide  yang  telah  dikemukakan  pada [9], [10], [11] serta [12] maka dalam tulisan ini penulis  akan  mengusulkan  metode  baru  yaitu metode gabungan antara metode LS dan metode
DY yang merupakan metode NH5 (Metode LS- CD) yang dimana bentuk tersebut nantinya akan digantikan  pada  metode  MDY.  Berikut  metode baru yang diusulkan:
H5:     5 max 0, min , H LS DY k k k    ,         (18)
dengan  menggunakan  bentuk  MDY,  maka bentuk metode baru sebagai berikut:
NH5: 5 5 1 1 2 1 1 T H H k k k k k k k k g d d g d g   − − −   = − +  +     . (19)

## 2. ALGORITMA METODE NH5
Langkah  awal  :  Diberikan  titik  awal 𝑥 0 ∈ ℝ 𝑛 , 0 < 𝜀 ≤ 1, 0 < 𝛿 < 1 2 dan 𝛿 < 𝜎 < 1 .
Tetapkan 𝑑 0 = −g 0 , 𝑘 ≔ 0.
Langkah  1:  Jika , k g   berhenti;  jika  tidak lanjutkan ke langkah 2 Langkah  2:  Hitung  ukuran  langkah 𝛼 𝑘 menggunakan kondisi Wolfe (1.4).
(x ) ( ) (x ) (x ) ( )     +  +   +   T k k k k k k k T T k k k k k k f d f x f d f d d f x d
Langkah  3:  Misalkan 𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 ,  jika
1 , k g  +  berhenti;  jika  tidak  lanjutkan  ke langkah 4 Langkah 4: Hitung pencarian arah
5 1 1 1 H k k k k d g d  + + + = − + , dimana     5 max 0, min , H LS DY k k k   
Langkah 5: Beri nilai 𝑘 = 𝑘 + 1 , dan kembali ke langkah 2.

## 3. HASIL DAN PEMBAHASAN
Pada  pembahasan  ini  akan  dilakukan perbandingan  hasil  numerik  antara  metode  HS- CD  dengan  metode  baru  LS-DY.  Parameter 𝛼 𝑘 dilakukan  pencaharian  menggunakan  kondisi wolfe  yang  dimana  konstanta  yang  digunakan adalah 𝜇 =0.3, 𝛿 =0.8. Untuk batas toleransi atau perhentian  yang  digunakan  dalam  tulisan  ini yaitu 𝜀 = 10 −6 .  Fungsi  yang  digunakan  dalam
tulisan ini adalah fungsi non linier tak berkendala yang  diperoleh  dari  [13],  berikut  fungsi- fungsinya:
1. Extended Rosenbrock function   2 2 2 2 2 2 1 2 1 1 0 ( ) ( ) (1 ) , 1.2,1,..., 1.2,1 . 100. n i i i i f c c − − = = − + − = − − =  x x x x x
2. Extended White & Holst function   2 3 2 2 2 2 1 2 1 1 0 ( ) ( ) (1 ) ,
1.2,1,..., 1.2,1 . 100. n i i i i f c c − − = = − + − = − − =  x x x x x
3. Extended quadratic penalty QP1 function   1 2 2 2 2 1 1 0 ( ) ( 2) ( 0.5) ,
1,1,...,1,1 . n n i i i i f − = = = − + − =   x x x x
4. SINCOS function   2 2 2 2 2 2 2 1 2 2 1 2 1 2 2 2 1 2 0 ( ) ( )
sin cos , 3, 0.1,...,3, 0.1 . n i i i i i i i f − − = − = + + + + =  x x x x x
x x x
5. Extended Beale function
  2 2 2 1 2 1 2 2 2 1 2 3 2 2 1 2 0 ( ) (1.5 (1 ))
(2.25 (1 )) (2.625 (1 )) , 1, 0.8,...,1, 0.8 . n i i i i i i i f − = − − = − − + − − + − − =  x x x x x x x
x
Pada  hasil  numerik  setelah  diperoleh  akan dibandingkan hasil numerik antara metode baru (NH5)  dengan  metode  HS-CD  (NH4)  serta metode hibrid lain (metode NH2 dan NH3). Hasil numerik  yang  telah  diperoleh  pada  metode- metode  tersebut,  selanjutnya  akan  digabungkan menggunakan hasil profil yang dijelaskan dalam [14].  Hasil  profil  tersebut  akan  diilustrasikan dalam bentuk gambar yaitu hasil profil iterasi dan running  time  sehingga  dapat  dilihat  perbedaan kemampuan  metode  baru  dengan  metode  yang telah  diusulkan  sebelumnya.  Adapun  hasil profilnya sebagai berikut:
  , ,m , min : =  p m p p m a r a m M , dimana = {𝑝1, 𝑝2, … } , 𝑀 =
{𝑚1, 𝑚2, 𝑚3, … } , 𝑎 𝑝,𝑚 merupakan  hasil  yang diperoleh dari iterasi dan running time. Apabila suatu metode tidak dapat diselesaikan atau hasil numeriknya  tidak  ada  maka,  maka 𝑟 𝑝,𝑚 = 𝑟 𝑀 , diasumsikan  parameter 𝑟 𝑀 ≥ 𝑟 𝑝,𝑚 untuk  semua 𝑝, 𝑚 .    Untuk  melihat  hasil  profil,  maka  dapat bentuk persamaan berikut:
    2 , 1 : log ( )     = s p m p size p P r n P ,
dengan 𝑃 𝑠 (𝜏) adalah peluang untuk metode 𝑚 ∈ 𝑀 dimana hasil ratio 𝑟 𝑝,𝑚 kurang dari faktor 𝜏 ∈ ℝ dari kemungkinan ratio terbaik dan 𝑛 𝑝 adalah banyaknya  fungsi.  Fungsi 𝑃 𝑠 (𝜏) merupakan fungsi distribusi komulatif untuk hasil ratio. Nilai 𝑃 𝑠 (1) merupakan  peluang  dimana  metode  yang diujikan akan lebih baik apabila mencapai angka 1.
Tabel 1. Hasil numerik berupa iterasi dan running time
No Fungsi N NH5 NH2 NH3 NH4 Itr/rt Itr/rt Itr/rt Itr/rt 1 Rosenbrock 10 184/0.4355 249/0.4928 179/0.3677 254/0.4846 100 1010/2.2159 1016/2.3523 1043/2.3039 962/2.2378 1000 8771/55.9225  8695/49.9178  8548/48.3147  8282/48.1698 2 White and Host 10 272/0.6627 279/0.5697 259/0.5479 261/0.6003 50 1024/2.6939 1000/2.3866 968/2.4005 962/2.4171
3 Quadratic Penalty QP1 100 16/0.2221 16/0.2313 15/0.2173 15/0.1980 1000 8/1.2282 12/1.7764 8/1.2274 8/1.2235 4 SINCOS 50 17/0.1675 20/0.1843 17/0.1477 18/0.1691 100 16/0.2708 19/0.3576 24/0.3968 17/0.3202 1000 15/4.7851 15/4.7629 22/6.4625 18/5.7778 5 Beale 2 38/0.1895 31/0.1881 25/0.1599 38/0.1751 5 231/0.6775 159/0.5236 131/0.3867 231/0.7020
Keterangan: N (dimensi dari fungsi), itr (banyaknya iterasi) dan rt (running time).
Untuk melihat perbedaan antara metode baru dan metode dahulu, maka dalam akan digunakan teori hasil profil. Berdasarkan teori hasil profil yang telah dijelaskan di atas, maka hasil numerik berupa iterasi dan running time disajikan dalam gambar 1 dan 2 sebagai berikut
Pada gambar 1 dan 2 merupakan hasil numerik berupa  banyaknya  iterasi  dan  running  time, dari  gambar  tersebut  menunjukkan  bahwa metode  NH5  dapat  bersaing  dengan  metode sebelumnya. Metode NH5 menunjukkan hasil yang baik setiap iterasi dan running time pada fungsi yang dengan metode baru tersebut.

## 4. KESIMPULAN
Pada  tulisan  ini  diusulkan  metode konjugat gradien baru yang diberi nama NH5, dimana metode tersebut digabungkan
berdasarkan  ide  yang  dikemukakan  oleh beberapa artikel sebelumnya. Metode baru ini setelah  diujikan  ke  beberapa  fungsi  tak  linier orde  tinggi  menunjukkan  bahwa  hasil  yang baik  dan  dapat  diselesaikannya  yang  dimana terlihat pada tabel 1 dan juga metode baru ini dapat bersaing dengan metode hibrid sebelumnya.

## 5. DAFTAR PUSTAKA
[1]    Nocedal,  J.,  &  Wright,  SJ.  (1999). Numerical  Optimization.  New  York: Springer-Verlag.
[2]      Hestenes,  MR.,  Stiefel  EL.  (1952). Methods  of  Conjugate  Gradient  for
Solving  Linear  System.  Journal  of Research  of  the  Nattional  Bureau  of Standart. 49(6): 409-432. [3] Fletcher,  R.,  &  Reeves,  C.  (1964).
Function  Minimazation  by  Conjugate Gradient.  The  Computer  Journal,  7:149
– 154.
Gambar 1 . Hasil profil iterasi metode baru (NH5) dengan metode NH2, NH3 dan NH
Gambar 2 . Hasil profil running time metode baru (NH5) dengan metode NH2, NH3 dan NH4
[4] Polak, B., Ribiѐre, G. (1969). Note Surla Convergence des Méthodes de Directions Conjuguées. Francaise Imformat Recherche Opertionelle, 16:35–43.
[5] Polyak,  BT.  (1969).  The  Conjugate Gradient  Method  in  Extreme  Problems, USSR  Computational  Mathematics  and
Mathematical Physics, 9(4): 94-112.
[6] Fletcher, R, (1987). Practical Methods of Optimization,
Unconstrained Optimization. New  York: Wiley.
[7] Liu, YL., & Storey, CS. (1991). Efficient Generalized Conjugate Gradient Algorithms,  Part  1:  Theory.  Journal  of Optimization  Theory  and  Applications, 69(1):129-137.
[8] Dai,  YH.,  &  Yuan,  Y.  (1999).  A
Nonlinear  Conjugate  Gradient  Method with  a  Strong  Global  Convergence Property. SIAM Journal on Optimization, 10: 177-182.
[9] Touati-Ahmed, D., & Storey, C. (1990).
Efficient  Hybrid  Conjugate  Gradient Techniques:  Journal  of  Optimization Theory  and  Applications,  64(2):  379– 397.
[10]  Zhang,  L.,  &  Zhou,  W.  (2007).  Two Descent  Hybrid  Conjugate  Method  for Optimazation. Journal of Computational and  Applied  Mathematics,  216:251- 264.doi: 10.1016/j.cam.2007. 04.028.
[11]  Zhou, A., Zhu, Z., Fan, H., & Qing, Q.
(2011).  Three  New  Hybrid  Conjugate Gradient  Method  for  Optimazation. Applied  Mathematics,  2:303-308.doi: 10.4236/am.2011.23035.
[12]  Saputra,  T.  Murdani.,  Silalahi,  Bib Paruhum.,  &  Guritman,  Sugi.  (2020). Metode  Konjugat  Gradien  Hibrid  Baru:
Metode  HS-CD  Untuk  Menyelesaikan
Masalah  Optimasi  Tak  Berkendala. Journal  Matematika  dan  Statistika  serta Aplikasinya, 8:37-45. doi: 10.24252/msav8i1.12294.
[13]  Andrei,  N.  (2008).  An  Unconstrained Optimization  Test  Function  Collection. Advanced  Modelling  and  Optimization, 10(1): 147-161.
[14]  Dolan,  JED.,  &  Morѐ,  JJ.  (2002). Benchmarking  Optimization  Sofware with  Performance  Profil.  Mathematical Programming. 912(2): 201-213.doi: 10.1007/s101070100263