Prosiding Seminar Nasional Matematika dan Pembelajarannya. Jurusan Matematika, FMIPA UM. 13 Agustus 2016

Prosiding Seminar Nasional Matematika dan Pembelajarannya. Jurusan Matematika, FMIPA UM. 13 Agustus 2016

METODE NUMERIK STEPEST DESCENT DENGAN ARAH PENCARIAN RERATA ARITMATIKA Rukmono Budi Utomo Universitas Muhammadiyah Tangerang [email protected] [email protected] Abstrak Penelitian ini mengkaji tentang Metode numerik Stepest Descent dengan arah pencarian Rerata Aritmatika. Penelitian dilakukan dengan memahami terlebih dahulu mangenai metode numerik Stepest Descent dengan arah pencarian gradien beserta algoritmanya. Setelah itu dikonstruksi metode numerik Stepest Descent dengan arah pencarian Rerata Aritmatika beserta algoritmanya. Dalam penilitian ini juga diberikan contoh penggunaan kedua metode numerik dalam menyelesaikan masalah optimisasi tanpa kendala beserta analisinya. Kata kunci: metode numerik steepest descent, arah pencarian gradien, rerata aritmatika

PENDAHULUAN Tidak selamanya solusi analitik dari suatu permasalahan matematika khususnya masalah optimisasi dapat dengan mudah ditemukan. Terkadang ditemukan kendala yang cukup rumit sehingga solusi analitik dari permasalahan optimisasi tersebut tidak mudah ditemukan. Berdasarkan hal tersebut solusi numerik merupakan sesuatu hasil yang cukup realistis untuk dicari meski hasilnya merupakan hampiran atau pendekatan. Metode numerik merupakan suatu metode pendekatan (approximation) dari solusi sejati, dan berdasarkan hal tersebut terdapat besarnya angka kesalahan (eror) yang dihasilkan oleh perhitungan numerik. Kesalahan ini lebih sering diakibatkan baik karena pemotongan suku atau pembulatan nilai. Masalah optimisasi merupakan persoalan yang banyak menggunakan metode numerik dalam mencari solusi penyelesaian tatkala solusi analitik sulit ditemukan. Menurut kendalanya (constrain), masalah optimisasi dibagi dua yakni masalah optimisasi dengan kendala dan tanpa kendala, sedangkan menurut variabel bebasnya masalah optimisasi juga dibagi atas dua, yakni masah optimisasi dengan satu variabel bebas dan banyak variabel bebas. Masalah optimisasi juga dibagi atas dua bagian berdasarkan banyaknya fungsi objektif yang dioptimalkan, yakni masalah optimisasi dengan satu fungsi objektif dan banyak fungsi objektif. Metode numerik untuk menyelesaikan masalah optmisasi dengan kendala dapat menggunakan metode Kuhn-Tucker atau pengali Lagrange, sedangkan untuk masalah optimisasi tanpa kendala dengan satu variabel bebas dapat menggunakan metode Golden Rasio, Fibonacci, Biseksi, Dichotomus dan Secant. Lebih lanjut untuk menyelesaikan masalah optmisasi dengan lebih dari satu variabel bebas dapat menggunakan metode Aksial, Newton, Hook and Jeeves, Stepest Descent, Arah Konjugasi, dan Rosenberg. Untuk menyelesaikan masalah optimisasi dengan banyak fungsi objektif dapat menggunakan program linear multi objektif, namun hal tersebut tidak dibahas dalam tulisan ini Makalah ini membahas mengenai metode numerik Steepest Descent degan arah pencarian (direction) berupa rerata aritmatika. Diketahui bahwa metode Steepest Descent pada umumnya menggunakan arah pencarian gradien biasa dk  Z  X k  , sedangkan pada n

penelitian ini arah pencarian dimodifikasi menjadi rerata aritmatika d k 

1

 Z  X k  k 1

n

dan

n

dk 

Z  X 1    Z  X k  k 2

n

. Penelitian dilakukan dengan memahami terlebih dahulu

mengenai metode numerik Steepest Descent dengan arah pencarian gradien biasa kemudian menyusun algoritma untuk metode Steepest Descent dengan arah pencarian rerata aritmatika Dalam tulisan ini juga akan diberikan contoh perhitungan numerik untuk metode Steepest Descent dengan kedua arah pencarian tersebut beserta analisis dan perbandingan keakuratan solusi antara keduanya. PEMBAHASAN Definisi Ruang Vektor Himpunan tak kosong V merupakan ruang vektor apabila x, y, z V dan a, b  R sedemikian hingga memenuhi aksioma-aksioma sebagai berikut: i. x  y V ii. x y  yx iii. iv. v. vi. vii. viii. ix.

 x  y  z  x   y  z 0 V 0  V  V  0  0 0 V  x    x   0 ax V a  x  y   ax  ay

 a  b  x  ax  bx  ab  x  a  bx 

x. 1x  x Definisi Norm Diberikan X , Y sembarang dua vektor. Sembarang bilangan riil || X || dinamakan norm dari X apabila memenuhi aksioma-aksioma sebagai berikut i. | X || 0 ii. || aX || 0  X  0 iii. || aX ||| a ||| X ||, a  R iv. | X  Y |||| X ||  || Y || Definisi Ruang Bagian Himpunan bagian W dari V disebut ruang bagian dari V jika W ruang vektor dengan operasi jumlah dan kali sama seperti V Definisi Kombinasi Linear Misalkan X i , 1  i  m vektor-vektor di V maka X disebut kombinasi linear dari vektor-vektor m

X i jika X   ai X i i 1

Definisi Bebas Linear Vektor X i , 1  i  m anggota-anggota V disebut tak bebas linear jika dan hanya jika terhadap m

bilangan-bilangan riil tak semuanya nol sedemikian hingga

a X i 1

i

hanya ai  0 , maka vektor-vektor tersebut dikatakan bebas linear.

2

i

 0 . Apabila pembuat nol

Prosiding Seminar Nasional Matematika dan Pembelajarannya. Jurusan Matematika, FMIPA UM. 13 Agustus 2016

Definisi Basis Ortonormal. 2

Basis ortonormal di

didefinisikan sebagai l1  1, 0  dan l2   0,1 , sedangkan untuk T

basis ortonormal didefinisikan sebagai l1  1,0,

T

,0  , l2   0,1, T

,0  , T

, ln   0,0,

n

,1

T

Definisi Hubungan Dua Vektor Diberikan dua buah vektor X , Y dengan X  {x1 , x2 ,..., xn } dan Y  { y1 , y2 ,..., yn } . Pernyataan berikut dapat dibuktikan benar i. X  Y jika dan hanya jika xi  yi i, i  1, 2,..., n ii.

X  Y jika dan hanya jika xi  yi i, i  1, 2,..., n X  Y jika dan hanya jika xi  yi i, i  1, 2,..., n

iii. Definisi Bola Terbuka Diberikan

x0 

n

serta   0 . Himpunan



B  x0 ,    x 

n



x0  x   merupakan

persekitaran  dari x0 atau disebut bola terbuka dengan pusat x0 dan radius  . Definisi Titik Dalam Titik x0  X  n disebut titik dalam (interior point) dari himpunan X jika   0 sehingga

B  x0 ,    X

Definisi Titik Batas Titik

x0  X 

n

disebut titik batas (boundary point) dari himpunan X jika setiap sekitar 

dari x0 memuat beberapa titik yang berada di X dan beberapa titik yang tidak berada di X Definisi Komplemen Suatu Himpunan Jika X  n ,maka himpunan n  X yang memuat semua titik-titik yang ada di n namun tidak dari X disebut komplemen dari X . Definisi Himpunan Terbuka Himpunan X disebut himpunan terbuka jika setiap titik dari X merupakan titik dalam dari X . Lebih lanjut himpunan Y merupakan himpunan tertutup jika merupakan komplemen dari himpunan terbuka. Definisi Himpunan Tertutup Himpunan X disebut hinmpunan tertutup jika himpunan tersebut memuat semua titik batasnya. Teorema Himpunan Tertutup Sebarang irisan dari himpunan tertutup adalah tertutup. Definisi Himpunan Terbatas Himpunan S dikatakan terbatas jika terdapat M  0 sehingga x  S , berlaku x  M Definisi Himpunan Terbatas Ke atas Himpunan S dikatakan terbatas ke bawah jika y  n dengan semua komponennya berhingga sedemikian hingga x  S , y  x , sebaliknya S dikatakan terbatas ke atas Definisi Bentuk Kuadratik F ( X )  c11 x12  c2 2 x22  ...  cnn xn2  c12 x1 x2  c1,3 x1 x3  ...  c23 x2 x3  ... dengan cij  R ,

1  i, j  n , disebut fungsi bentuk kuadratik dengan n variabel bebas x1 , x2 ,..., xn Definisi Fungsi Definit Bentuk kuadratik X T AX disebut positif (negatif) definit jika X T AX  ()0 untuk semua

X  0 dan terdapat sekurangnya satu vektor tak nol sedemikian hingga X T AX  0 . Apabila tidak memenuhi keduanya, maka bentuk kuadratik tersebut dikatakan indefinite 3

Teorema Fungsi Definit Suatu matriks A dikatakan i. Positif definit jika dan hanya jika i  0 ii.

Negatif definit jika dan hanya jika i  0

iii.

Positif semi definit jika dan hanya jika i  0

iv.

Negatif semi definit jika dan hanya jika i  0

dengan i merupakan nilai-nilai eigen dari matriks A dan ketidaksamaan dicapai untuk sekurang-kurangnya satu j . Lebih lanjut apabila i tidak memenuhi butir i,ii,iii, dan iv maka matriks A disebut indefinite Definisi Minimum Global Fungsi F ( x) dikatakan memiliki minimum global di x0 dalam S jika f ( x)  f ( x0 ) Definisi Minimum Lokal Relatif Fungsi F ( x) dikatakan memiliki minimum lokal di x0 dalam S jika terdapat sekitar  dari x0 sedemikian hingga f ( x)  f ( x0 ) untuk setiap x di dalam persekitaran tersebut. Definisi Deret Taylor Deret Taylor untuk fungsi F ( X ) dengan X  {x1 , x2 ,..., xn } didefinisikan sebagai

F ( X  x)  F ( X )  F ( X )X  ( 2X ) H ( X )(x)  3 dengan 3 merupakan berderajat besar, dan H ( X ) merupakan metrik Hessian yang didefinisikan sebagai '

suku

 2 F 2 F 2F    x 2 x x x1 xn  1 2  1  2 F 2 F 2F     H   x2 x1 x2 2 x2 xn  .. . . .     2 F 2F 2F   x x x x  x 2  n 2 n   n 1 Syarat perlu agar X merupakan titik ekstrim dari fungsi F ( X ) adalah F ( X )  0 dengan

 F F F  F ( X )   , ,...,  xn   x1 x2 Algoritma Stepest Descent Diberikan Z  F ( X )  F ( x2 , x2 ,., xn ) dan akan ditentukan nilai X  {x1 , x2 ,., xn } yang meminimalkan fungsi F ( X ) tersebut i.

ii.

Ambil X1  {x1 , x2 ,., xn }  R n yang merupakan sembarang titik awal dan   0 yang merupakan suatu konstanta positif yang menyatakan besarnya kesalahan eror yang ditoleransi.

lakukan untuk Z  X k  iii.

 Z Z , ,  x1 x2

Dibentuk fungsi gradient Z  X   

,

Z   dan tentukan Z  X1  serta xn 

Apabila Z  X k    , maka iterasi berhenti, sebaliknya iterasi dilanjutkan 4

Prosiding Seminar Nasional Matematika dan Pembelajarannya. Jurusan Matematika, FMIPA UM. 13 Agustus 2016

iv.

Tentukan k dengan cara mencari titik ekstrim Z  X k  k dk  yakni dengan cara menderivatifkan fungsi Z  X k  k dk  dan menyamadengankan nol dengan arah pencarian dk  Z  X k 

v.

Nilai X k ditentukan dengan X k  X k 1  k 1dk 1

Berdasarkan algoritma Stepest Descent dngan arah pencarian gradien dk  Z  X k  , akan dikembangkan suatu metode Stepest Descent dengan arah pencarian rerata aritmatika. Algoritma Stepest Descent Dengan Arah Pencaraian Rerata Aritmatika Diberikan fungsi Z  F ( X )  F ( x2 , x2 ,., xn ) dan akan ditentukan X  {x1 , x2 ,., xn } yang meminimalkan fungsi F ( X ) tersebut i.

Ambil X1  {x1 , x2 ,., xn }  R n titik sembarang titik awal dan   0 suatu konstanta positif yang menyatakan besarnya kesalahan eror yang ditolerasnsi.

ii.

Dibentuk Z  X   

 Z Z , ,  x1 x2

k  1, 2,

,

Z   kemudian tentukan untuk Z  X k  , xn 

,n

iii.

Apabila Z  X k    , maka iterasi berhenti, sebaliknya iterasi dilanjutkan

iv.

Cari k dengan cara mencari titik ekstrim Z  X k  k dk  yakni dengan cara menderivatifkan Z  X k  k dk  dan menyamadengankan nol dengan atrah pencarian k n

n

dk 

 Z  X k  k 1

k

dan d k 

Contoh Numerik 1 Tentukan nilai X  {x1 , x2 }

Z  X 1    Z  X k 

yang

k 2

n meminimalkan Z ( x1 , x2 )  2 x12  x22  3x1  x2 dengan

menggunakan metode Stepest Descent dengan toleransi kesalahan   0.03

Solusi Stepest Descent dengan Arah Pencarian Gradien Ambil sebarang titk awal X1  {1, 12}  R 2 . Berdasarkan masalah optimisasi di atas dapat ditentukan Z  X1   7,0 . Karena norm Z  X1   7   maka iterasi dilanjutkan dengan arah pencarian d1  Z  X1   7,0 dan berdasarkan hal tersebut dapat diperoleh 1  Apabila dicari lebih lanjut, akan diperoleh nilai

1 . 4

3 1 X 2   ,  dengan nilai gradien 4 2

Z  X 2   0,0 dan norm Z  X 2   0   . Berdasarkan hal tersebut iterasi berhenti sehingga nilai

X 2   x1 , x2  yang meminimalkan masalah optimisasi di atas adalah

3 1 X2   ,  . 4 2

5

Karena Z  X 2   0   hal ini mengindikasikan bahwa solusi numerik ini sama dengan solusi analitiknya. Pada penyelesaian masalah optimisisasi tanpa kendala di atas, terlihat bahwa untuk nilai awal X1  {1, 12}  R 2 dan arah pencarian dk  Z  X k  , solusi numerik yang

3 1 4 2

dihasilkan sama dengan solusi analitik yakni X   ,  dan langkah pengerjaannya hanya menbutuhkan dua iterasi. Solusi Stepest Descent dengan Arah Pencarian Rerata Aritmatika Tetap diambil sebarang titk awal X1  {1, 12}  R 2 . Berdasarkan masalah optimisasi di atas dapat ditentukan Z  X1   7,0 . Karena norm Z  X1   7   maka iterasi dilanjutkan dengan arah pencarian d1  Z  X1   7,0 dan berdasarkan hal tersebut dapat diperoleh 1 

1 . 4

3 1 4 2

Apabila dicari lebih lanjut, akan diperoleh nilai X 2   ,  dengan Z  X 2   0,0 dan dengan

arah

pencarian

rerata

sebagai

berikut

2

d2 

 Z  X k  k 1

k

 Z  X 1   Z  X 2   7      2 , 0 . Karena Z  X 2   0   , iterasi 2  

tetap harus berhenti dan solusi numeric steepest descent dengan arah pencarian rerata aritmatika ini sama dengan solusi dari metode steepest descent dengan arah pencarian gradien biasa yakni 3 1 X  ,  4 2

Contoh Numerik 2 Pandang kembali contoh numerick1. Apabila diambil X1  {1,1}  R 2 , penyelesaian akan coba dilakukan dengan metode Steepest Descent dengan kedua jenis arah pencarian. Solusi Stepest Descent dengan Arah Pencarian Gradien Berdasarkan hal tersebut diperoleh Z  X1    7,1 dengan norm Z  X1   50   . Karena norm masih lebih besar dari  , maka iterasi dilanjutkan. Arah pencarian

d1  Z  X1   7, 1 dan berdasarkan hal tersebut dapat diperoleh 1 

50 . Apabila dicari 198

 76 74  ,  dengan Z  X 2   0.070,0.494 dan nilai norm  99 99 

lebih lanjut, diperoleh X 2  

Z  X 2   0.498   , berdasarkan hal tersebut iterasi dilanjutkan. Dengan cara yang sama, diperoleh d2  Z  X 2    0.070, 0.494 sehingga berdasarkan hal tersebut dapat

diperoleh 2  0.49 . Lebih lanjut diperoleh nilai X 3  0.732,0.504 dengan nilai gradien

Z  X 3   0.072,0.008 dan nilai norm adalah Z  X 3   0.07   .

6

Prosiding Seminar Nasional Matematika dan Pembelajarannya. Jurusan Matematika, FMIPA UM. 13 Agustus 2016

Proses dilanjutkan sehingga diperoleh arah pencarian d3  Z  X 3   0.072, 0.008 dan

3  0.25 .Berdasarkan hal tersebut diperoleh

3 1 X4   ,  4 2

dengan

nilai

gradien

Z  X 4   0,0 dan Z  X 4   0   sehingga iterasi berhenti dan solusi numeriknya juga merupakan solusi analitik. Solusi Stepest Descent dengan Arah Pencarian Rerata Aritmatika Diambil X1  {1,1}  R 2 sebarang nilai awal. Berdasarkan hal tersebut diperoleh nilai gradien

Z  X1   7,1 dengan norm Z  X1   50   . Karena norm masih lebih besar dari  , maka iterasi dilanjutkan. Karena arah pencarian d1  Z  X1   7, 1 maka berdasarkan hal

50  76 74  . Apabila dicari, maka akan diperoleh nilai X 2   ,  198  99 99  dengan nilai gradient Z  X 2   0.070,0.494 dan norm Z  X 2   0.498   . Nilai arah tersebut dapat diperoleh 1 

2

 Z  X k 

 Z  X 1   Z  X 2       3.465, 0.747 .Berdasarkan hal 2 2   tersebut diperoleh 2  0.0053 sehingga dapat ditemukan nilai X 3  0.786,0.743 . pencarian d 2 

k 1

Lebih lanjut Z  X 3   0.144,0.486 dengan norm Z  X 3   0.506   . Karena norm masih lebih besar dari  , maka iterasi dilanjutkan. Dengan cara yang sama akan diperoleh d3  2.262, 0.66 dengan 3  0.00023 sehingga dapat ditemukan X 4  0.785,0.743 dengan Z  X 4   0.14,0.486

dan norm Z  X 4   0.505   . Iterasi dilanjutkan

sehingga diperoleh d4  1.661, 0.616 dan 4  0.0056 . Berdasarkan hal demikian

diperoleh nilai X 5  0.794,0.739 dengan nilai gradient Z  X 5   0.176,0.478 dan

Z  X 5   0.504   . Terlihat bahwa nilai x1 

x1  0.75 namun untuk x2 

2

semakin menjauhi nilai aslinya yakni

terlihat mendekati nilai aslinya yakni x2  0.5  2 meski membutuhkan iterasi yang panjang. Dengan demikian dengan cara ini, iterasi akan tetap berhenti 2

saat Z  X k    , dengan nilai x2 yang semakin akurat dengan solusi asli namun tidak sama halnya dengan x1 yang justru menjauhi nilai aslinya. Lebih lanjut apabila arah pencarian rerata aritmatika didefinisikan dengan n

dk 

Z  X 1    Z  X k  k 2

n

,

maka

akan

diperoleh

nilai

arah

pencarian

2

Z  X 1    Z  X k 

 Z  X 1   Z  X 2      3.535, 0.253 . Berdasarkan 2 2   hal tersebut diperoleh 2  0.0024 sehingga dapat ditemukan nilai X 3  0.759,0.748 . d2 

k 2

Lebih lanjut Z  X 3   0.036,0.496 dengan Z  X 3   0.497   . Karena norm masih 7

 , maka iterasi dilanjutkan. Dengan cara yang sama diperoleh d3  2.368, 0.0033 dengan nilai 3  0.0037 sehingga dapat ditemukan nilai

lebih besar dari

X 4  0.75,0.748 dengan Z  X 4   0,0.496 dan

Z  X 4   0.496   . Dari sini

terlihat bahwa nilai x1  2 telah sama dengan nilai aslinya yakni x1  0.75 , namun x2  2 terlihat menjauhi nilai aslinya. Iterasi tetap akan berhenti di suatu keadaan karena nilai

Z  X k  semakin kecil mendekati nilai epsilon.

KESIMPULAN DAN SARAN Penelitian ini memberikan beberapa kesimpulan dan saran yang diuraikan dalam beberapa poin dibawah ini Kesimpulan Dari penelitian yang telah dilakukan, terdapat beberapa hal yang dapat disimpulkan: i. Dalam suatu masalah optimisasi dua variabel tanpa kendala dengan nilai awal tertentu X 1 , solusi numerik Stepest Descent dengan arah pencarian gradien biasa dan aritmatika akan menghasilkan solusi yang identik dengan solusi analitik pada masalah optimisasi yang dibahas dalam tulisan ini. ii. Solusi masalah optimisasi dengan metode steepest descent dengan arah pencarian rerata aritmatika menghasilkan salah satu nilai dari xi , i  1, 2 yang menjauhi niai aslinya. k

Untuk metode steepest descent dengan arh pencarian d k 

 Z  X k  k 1

k

menghasilkan

nilai x2 yang semakin akurat dengan solusi asli namun tidak sama halnya dengan x1 yang justru menjauhi nilai aslinya. Sedangkan untuk Steepest Descent dengan arah pencarian n

dk 

Z  X 1    Z  X k  k 2

n

akan terbentuk nilai x1 

nilai aslinya yakni x1  0.75 , namun x2 

2

2

yang telah sama dengan

terlihat menjauhi nilai aslinya. Terlepas

dari hal tersebut, suatu saat iterasi akan berhenti di suatu kondisi karena nilai Z  X k  yang semakin kecil mendekati nilai epsilon. Saran Perlu dikonstrusi arah pencarian rerata aritmatika yang pas agar baik nilai x1 maupun x2 yang dihasilkan dapat menuju pada nilai yang seharusnya, yakni mendekati atau sama dengan solusi asalitiknya. Lebih lanjut perlu diselidiki untuk masalah optimisasi yang lain dengan nilai awal X 1 tertentu agar ditemukan kesimpulan umum mengenai kecepatan iterasi menemukan solusi pada metode numerik Steepest Descent dengan arah pencarian gradient biasa dengan gradien rerata aritmatika.

8

Prosiding Seminar Nasional Matematika dan Pembelajarannya. Jurusan Matematika, FMIPA UM. 13 Agustus 2016

DAFTAR RUJUKAN

Anton, Howard. 1991. Aljabar Linier Elementer: Penerjemah Pantur Silaban. Jakarta: Erlangga Bober, William. 2014. An Introduction to Numerical and Analytical Methods with Matlab for Engineers and Scientist. London: Taylor and Francis Group Bazaraa. S. Mochtar. 2006. Nonlinear Programming Theory and Algorithms. London: John-Willey Inter Science Epperson, James. 2013. An Introduction to Numerical Methods and Analysis. USA: John Willey and Sons. Inc K.P.Chong,, Edwin..2001. An Introduction to Optimization. USA: John Wiley & Sons, Inc. Munir, Rinaldi. 2008. Metode numerik. Bandung:Informatika Otto, S.R. and Denier, J.P. 2005. An introduction to Programming and Numerical Methods in Matlab. London: Springer-Verlag Corless, Robert,M. and Fillion, Nicholas. 2013. A Graduate Introduction to Numerical Methods. London: Springer-Verlag Salmah.2011. Diktat Optimisasi. Yogyakarya: FMIPA UGM Sawaragi, Yoshikazu. 1985. Theory of multiobjective optimization. London: Academic Press Inc.

9