METODE NUMERIK STEPEST DESCENT TERINDUKSI NEWTON

Utomo, R. B.

Jurnal Pendidikan Matematika STKIP Garut e-mosharafa.org

METODE NUMERIK STEPEST DESCENT TERINDUKSI NEWTON DALAM PEMECAHAN MASALAH OPTIMISASI TANPA KENDALA INDUCTED NEWTON STEEPEST DESCENT AS A NUMERICAL METHOD TO SOLVE OPTIMIZATION PROGRAM WITHOUT CONSTRAIN Rukmono Budi Utomo Universitas Muhammadiyah Tangerang Tanggerang, Indonesia [email protected]

Abstrak Penelitian teoritis ini mengkaji mengenai metode numerik Stepest Descent yang terinduksi Newton. Penelitian ini dilakukan dengan cara memahami terlebih dahulu mengenai metode numerik Stepest Descent dan Newton, kemudian mengkonstruksi metode baru yang disebut dengan Stepest Descent terinduksi Newton. Pada makalah ini turut disertakan pula contoh perhitungan numerik antara ketiga metode tersebut beserta analisis perhitungannya. Kata Kunci: Metode Stepest Descent, Newton, Metode Stepest Descent terinduksi Newton

Abstract This research is investigating numerical method of Steepest Descent inducted of Newton. Steps of this research can be described as follows: First, the author has to understand the definition and algorithm of Steepest Descent and Newton methods. After that, the second, author constructing the new method called by Steepest Descent inducted newton. In this paper, author also containing examples of numerical counting among that three methods and analyze them self. Keyword: Steepest Descent, Newton, Steepest Descent Inducted Newton.

I. PENDAHULUAN Tidak selamanya solusi analitik dari suatu permasalahan matematika khususnya optimisasi dapat ditemukan. Terkadang ditemukan kendala yang cukup rumit sehingga solusi analitik tidak mudah ditemukan. Berdasarkan hal tersebut solusi numerik merupakan sesuatu hasil yang cukup realistis untuk dicari meski hasilnya merupakan hampiran. Metode numerik merupakan suatu metode pendekatan (approximation) dari solusi sejati, dan karenanya terdapat besarnya angka kesalahan (eror) yang dihasilkan oleh perhitungan numerik [1]. 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 2 yakni masalah optimisasi dengan kendala dan tanpa kendala, sedangkan menurut variabel bebasnya masalah optimisasi juga dibagi atas dua, yakni masah optimisasi dengan 1 varibel bebas dan banyak variabel bebas. Metode numerik untuk menyelesaikan masalah optmisasi dengan

Jurnal “Mosharafa”, Volume 5 Nomor 3 September 2016 p-ISSN: 2086-4280, e-ISSN: 2527-8827

187

Utomo, R. B.


kendala dapat menggunakan metode Kuhn-Tucker, sedangkan untuk masalah optimisasi tanpa kendala dengan 1 variabel bebas dapat menggunakan metode Golden Rasio, Fibonacci, Biseksi, Dichotomus dan Secant. Lebih lanjut untuk menyelesaikan masalah optmisasi dengan lebih dari 1 variabel bebas dapat menggunakan metode Aksial, Newton, Hook and Jeeves, Stepest Descent, Arah Konjugasi, dan Roosenberg [2]. Makalah ini membahas mengenai metode numerik Steepest Descent yang terinduksi newton. Penelitian dilakukan dengan memahami terlebih dahulu mengenai metode numerik Steepest Descent dan Newton kemudian memformulasikan metode baru yang disebut dengan metode Steepest Descent terinduksi Newton. Dalam makalah ini juga akan diberikan contoh perhitungan numerik untuk ketiga metode tersebut beserta analisisnya.

A. Definisi Ruang Vektor Himpunan tak kosong V merupakan ruang vektor apabila x, y, z V dan sedemikian hingga memenuhi aksioma-aksioma sebagai berikut: [3] i. x  y V ii. x y  yx iii.

 x  y  z  x   y  z

vi. vii.

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

viii.

 a  b  x  ax  bx

iv. v.

188

1x  x

x.

B. Definisi Norm Diberikan X , Y sembanrang dua buah vektor. Sembarang bilangan riil || X ||

X dinamakan norm dari memenuhi aksioma-aksioma berikut: i. | X || 0 ii. | aX || 0  X  0 iii. || aX ||| a ||| X ||, a  R iv. | X  Y |||| X ||  || Y ||

apabila sebagai

C. Definisi Kombinasi Linear [3] Misalkan X i , 1  i  m vektor-vektor di

V maka X disebut kombinasi linear dari m

vektor-vektor

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

D. Definisi Bebas Linear [3] Vektor X i , 1  i  m anggota-anggota

II. KAJIAN TEORI

a, b  R

 ab  x  a  bx 

ix.

V disebut tak bebas linear jika dan hanya jika terhadap bilangan-bilangan riil tak semuanya nol sedemikian hingga m

a X i 1

i

i

ai  0 ,

 0 . Apabila pembuat nol hanya maka

vektor-vektor

tersebut

dikatakan bebas linear. E.

Definisi Hubungan Vektor [2] Diberikan dua buah vektor

dengan

X  {x1 , x2 ,..., xn }

Y  { y1 , y2 ,..., yn } .

Pernyataan

X ,Y

dan berikut

adalah benar Jurnal “Mosharafa”, Volume 5 Nomor 3 September 2016 p-ISSN: 2086-4280, e-ISSN: 2527-8827

Utomo, R. B.


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

iii. X  Y jika dan hanya jika

xi  yi

i, i  1, 2,..., n

F.

Definisi Bola Terbuka [2] Diberikan serta  0. ( ) * ‖ Himpunan ‖ + merupakan persekitaran  dari

merupakan himpunan tertutup komplemen dari himpunan terbuka.

K. Definisi Terbatas Ke Atas [5] Himpunan S dikatakan terbatas ke bawah jika dengan semua komponennya berhingga sedemikian sehingga x  S , y  x , sebaliknya S dikatakan terbatas ke atas. L.

Definisi Bentuk Kuadratik [5] F ( X )  c11 x12  c2 2 x22  ...  cnn xn2  c12 x1 x2 c1,3 x1 x3  ...  c23 x2 x3  ...

x0 atau disebut bola terbuka dengan pusat

dengan cij  R , 1  i , j  n disebut fungsi

x0 dan radius  .

bentuk G. Definisi Titik Dalam [4] Titik disebut titik dalam (interior point) dari himpunan X jika

  0 sehingga B  x0 ,    X

.

kuadratik

dengan

H. Definisi Titik Batas [4] Titik disebut titik batas (boundary point) dari himpunan X jika

x0 memuat beberapa

titik yang berada di X dan beberapa titik yang tidak berada di X . I.

Definisi Komplemen [4] Jika , maka himpunan yang memuat semua titik-titik yang ada di namun tidak dari X disebut komplemen dari X . J.

Definisi Himpunan Tertutup [5] Himpunan X disebut himpunan terbuka jika setiap titik dari X merupakan titik interior dari X . Lebih lanjut himpunan Y

n

variabel

x1 , x2 ,..., xn M. Definisi Kondisi Kuadratik [6] Bentuk kuadratik X t AX disebut positif

X t AX  ()0 untuk

(negatif) definit jika

setiap sekitar  dari

jika

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. N. Definisi Minimum Global [6] Fungsi memiliki F ( x) dikatakan minimum global di

f ( x)  f ( x0 )

x0 dalam S jika

.

O. Definisi Minimum Lokal [6] Fungsi memiliki F ( x) dikatakan minimum lokal (relatif) di jika


terdapat

sekitar



x0 dalam S dari

x0 189

Utomo, R. B.

sedemikian setiap

x


hingga

f ( x)  f ( x0 ) untuk

 Z Z Z  , , ,  xn   x1 x2

ii. Dibentuk Z  X   

di dalam persekitaran tersebut.

P. Definisi Deret Taylor [1] Deret Taylor untuk fungsi

F(X )

gradient fungsi Z saat X 1 , kemudian tentukan untuk Z  X 1  serta lakukan untuk Z  X k 

X  {x1 , x2 ,..., xn } didefinisikan iii. Jika

dengan

Z  X k    ,

maka

iterasi

sebagai

berhenti, sebaliknya iterasi dilanjutkan iv. Cari k dengan cara mencari titik F ( X  x)  F ( X ) F ( X )X  H ( X )(x)  3 ekstrim Z  X k  k d k  yakni dengan dengan 3 merupakan suku berderajat cara menderivatifkan fungsi besar, dan H ( X ) matrik Hessian yang dan menyamaZ  X k  k d k  didefinisikan sebagai dengankan nol dengan arah pencarian ( X )' 2

d k  Z  X k 

 2F 2F 2F    2  x1 x2 x1 xn   x1  2 F 2 F 2F     2 H   x2 x1 x2 x2 xn  .. . . .     2F 2F 2F   x x x x  x 2  n 2 n   n 1

Xk

v. Nilai

ditentukan

dengan

X k  X k 1  k 1dk 1

Syarat perlu agar X merupakan titik ekstrim dari fungsi F ( X ) adalah F ( X )  0 dengan F ( X ) didefinisikan

R. Algoritma Newton [7] Tahapan-tahapan dalam metode Newton analog dengan Stepest Descent, yakni diberikan fungsi

Z  F ( X )  F ( x2 , x2 ,., xn ) dan

X  {x1 , x2 ,., xn } yang

 F F F  sebagai F ( X )   , ,...,  xn   x1 x2

ditentukan

Q. Algoritma Stepest Descent [7] Diberikan fungsi

Stepest Descent, namun Nilai X k adalah

Z  F ( X )  F ( x2 , x2 ,., xn ) ditentukan

nilai

dan

X  {x1 , x2 ,., xn }

meminimalkan fungsi F ( X ) tersebut. Lakukan langkah i sampai iii dalam

akan yang





X k  X k 1   H  X k 1  Z  X k 1  dengan 1

H  X k 1  merupakan 1

invers

metrik

Hessian ketika X k 1 . Lebih lanjut iterasi

meminimalkan fungsi F ( X ) tersebut.

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

190

nilai

akan

berhenti ketika Z  X k    .

III. PEMBAHASAN Berdasarkan algoritma Stepest Descent dan Newton, akan dikembangkan suatu


Utomo, R. B.


metode baru yang disebut Metode Stepest Descent terinduksi Newton.

Z  X 1    7, 0 .

A.

Arah pencarian d1  Z  X 1    7, 0 dan

Algoritma Stepest Terinduksi Newton Diberikan dan

X  {x1 , x2 ,., xn }

yang

meminimalkan fungsi F ( X ) tersebut.

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

 Z Z Z  , , ,  xn   x1 x2

ii. Dibentuk Z  X   

Tentukan untuk Z  X 1  serta Z  X k  iii. Jika

Z  X k    ,

maka

iterasi

berhenti, sebaliknya iterasi dilanjutkan. iv. Cari k dengan cara mencari titik ekstrim fungsi Z  X k  k d k  yakni dengan cara menderivatifkan fungsi Z  X k  k d k  dan menyama- dengankan nol dengan arah pencarian

 

d k   H  X k 1  Z X k 1 1

B.

Contoh Numerik 1 Tentukan

nilai

X  {x1 , x2 }

yang

meminimalkan Z ( x1, x2 )  2 x1  x2  3x1  x2 2

2

dengan menggunakan metode Stepest Descent dan Newton dengan toleransi kesalahan ò  0.03 C.

Solusi dengan Stepest Descent Ambil sebarang titk awal

X1  {1, 12} R2 . Berdasarkan masalah optimisasi

di

atas

norm

Z  X 1   7   maka iterasi dilanjutkan. berdasarkan hal tersebut dapat diperoleh

fungsi akan

Z  F ( X )  F ( x2 , x2 ,., xn )

ditentukan

Descent

Karena

dapat

ditentukan

1 

1 . Apabila dicari, maka diperoleh 4

3 1 4 2

nilai X 2   ,  dengan Z  X 2    0, 0 dan Z  X 2   0   . Iterasi

berhenti

sehingga

nilai

X   x1 , x2  yang meminimalkan masalah

3 1 4 2

optimisasi di atas adalah X 2   ,  .

Z  X 2   0

Karena

hal

ini

mengindikasikan bahwa solusi numerik ini sama dengan solusi analitiknya. D. Solusi dengan Newton Ambil sebarang titk

awal


di

atas Z  X 1    7, 0 .

dapat ditentukan Karena norm

Z  X 1   7  

maka

iterasi

dilanjutkan.Dibentuk matriks Hessian 4 0 H   . Berdasarkan hal tersebut 0 2 4 0  14 0 1 H  X1    dan H X     1  1 . 0 2 0 2  Berdasarkan hal diatas akan diperoleh

 H  X 1  Z  X 1    74 , 0 . 1

t

Dengan

cara yang sama dapat dicari X 2  { 34 , 12} dengan nilai gradien Z  X 2    0, 0 dan

Z  X 1   0   .Iterasi berhenti sehingga


191

Utomo, R. B.

nilai


X   x1 , x2  yang

masalah

optimisasi

di

meminimalkan atas

berhenti sehingga solusi nilai X   x1 , x2 

adalah

yang meminimalkan masalah optimisasi di

3 1 X 2   ,  . Dari solusi yang diperoleh 4 2

atas adalah X 3   ,  . Berrdasarkan hal

melalui Stepest Descent dan Newton dengan pengambilan titik awal X 1 yang sama akan menghasilkan solusi numerik yang identik dengan solusi analitik. E.

Solusi dengan Stepest Descent Terinduksi Newton Ambil sebarang titik awal


di

atas dapat ditentukan nilai norm Z  X 1    7, 0 .Karena

Z  X 1   7   maka iterasi dilanjutkan. Arah

pencarian

d1   H  X 1  Z  X 1    , 0 1

dengan

demikian

Berdasarkan

t

7 4

hal

1 

diperoleh tersebut

35 49

.

diperoleh

3  X 2   ,1 .dengan Z  X 2    0,1 . 4  Karena

dilanjuttkan. Dengan analog diperoleh 4 0  14 0 1 H  X2    dan H X     1  1 0 2 0 2  dengan  H  X 2  Z  X 2    0,

.

1 t 2

Berdasarkan hal tersebut diperoleh

2  1 dan X 3   ,  dengan 3 1 4 2

Z  X 3    0, 0 dan

Karena 192

norm

Z  X 3   0   ,

gradien

Z  X 3   0   . maka

di atas pula, maka solusi numerik dalam solusi ini identic dengan solusi analitiknya. F.

Contoh Numerik 2 Pandang kembali contoh numerik 1.

Apabila diambil nilai

X1  {1,1} R2

,penyelesaian akan dilakukan dengan tiga metode. G. Penyelesian dengan Stepest Descent Berdasarkan hal tersebut diperoleh nilai norm Z  X 1    7,1 dengan

Z  X 1   50   . Karena norm masih dari  , maka iterasi Arah pencarian d1  Z  X 1    7, 1 dan berdasarkan hal

lebih besar dilanjutkan.

tersebut dapat diperoleh 1 

Z  X 2   1   , maka iterasi

1

3 1 4 2

iterasi

dicari,

maka

 76 74  X 2   ,  dengan  99 99 

50 . Apabila 198

akan

diperoleh

nilai

Z  X 2    0.070, 0.494 dan

gradient

nilai

norm

Z  X 2   0.498   , maka berdasarkan hal tersebut iterasi dilanjutkan. Dengan cara analog, maka akan diperoleh nilai dan d 2  Z  X 2    0.070, 0.494 berdasarkan hal tersebut dapat diperoleh

2  0.49 .

Lebih lanjut dengan caa yang

sama diperoleh nilai X 3  0.732, 0.504

dengan gradien Z  X 3    0.072,0.008 dan Jurnal “Mosharafa”, Volume 5 Nomor 3 September 2016 p-ISSN: 2086-4280, e-ISSN: 2527-8827

Utomo, R. B.


norm Z  X 3   0.07   .

nilai

Proses

I.

dilanjutkan

diperoleh nilai d3  Z  X 3    0.072, 0.008 serta

3  0.25 .

Berdasarkan

hal

tersebut

3 1 4 2

diperoleh X 4   ,  dengan nilai gradien

Z  X 2   0   .

Z  X 2    0, 0 dan

Berdasarkan hal tersebut iterasi berhenti dan solusi numeriknya juga merupakan solusi analitik.

Penyelesian dengan Stepest Descent Terinduksi Newton Diambil X1  {1,1} R

hal

tersebut

dengan

hal

tersebut

2

Berdasarkan Z  X 1    7,1

t

diperoleh

Z  X 1   50  

dengan

dan

 1 0 1 H  X 1    4 1  . Berdasarkan hal tersebut 0 2 

 H  X 1  Z  X 1    ,  sehingga diperoleh nilai X 2  { 34 , 32} dengan nilai 1

7 4

1 2

t

gradien Z  X 2    0, 2

t

Z  X 2   2  

dan sehingga

iterasi

1

X 3  { 34 , 12}

t

X 3  { 34 , 12}

yang

1  4751 dan nilai

t

nilai

norm

Z  X 1   1.997   . Lebih lanjut diperoleh nilai

2  0.96 dan

X 3  0.612,0.5

dengan nilai norm Z  X 3   0.552   . Kemudian

diperoleh

X 4  { 34 , 12} dengan

3  1 dan Z  X 4   0  

sehingga iterasi stop. Solusi numerik dengan metode ini identik dengan solusi analitik.

IV. PENUTUP Dari penelitian yang telah dilakukan, terdapat beberapa hal yang dapat disimpulkan: 1. Dalam suatu masalah optimisasi dua variabel tanpa kenda dengan nilai awal

serta

sehingga iterasi berhenti. Berdasarkan hal tersebut solusi numerik dengan Newton adalah

 

Z X 1  50   . Berdasarkan

Z  X 2    0.552,1.92 dan

Z  X 3   0  

dengan

t

X 2  0.612,1.460 dengan nilai gradien

dilanjutkan. Dengan langkah yang sama diperoleh nilai

 H  X 2  Z  X 2    0, 1

Z  X 1    7,1

diperoleh

langkah analog diperoleh

iterasi

dilanjutkan. Lebih lanjut dibentuk matrik 4 0 H  X1    Hessian dan  0 2

Berdasarkan

hal tersebut iterasi dilanjutkan dan dengan

H. Penyelesian dengan Newton Diambil X1  {1,1} R

2

sekaligus

tertentu X1 , solusi numerik Stepest Descent akan menghasilkan solusi yang sama dengan Newton, dan dalam langkah iterasi yang sama. Dalam hal yang tertentu pula solusi numerik ini identik dengan solusi analitik pada masalah optimisasi yang dibahas dalam makalah ini.

merupakan solusi analitik. Jurnal “Mosharafa”, Volume 5 Nomor 3 September 2016 p-ISSN: 2086-4280, e-ISSN: 2527-8827

193

Utomo, R. B.


2. Dalam nilai awal

tertentu X 1 dan

dalam suatu masalah optimisasi, solusi numerik yang dihasilkan oleh metode Stepest Descent terinduksi Newton akan menghasilkan nilai yang sama dengan solusi yang dihasilkan oleh kedua metode di atas meskipun memerlukan iterasi yang lebih panjang. Hal ini dikarenakan nilai

dk

[3] Howard

[4]

[5]

[6]

pada metode Stepest Descent diinduksi dengan d k   H  X k 1  Z  X k 1  1

[7]

3. Adakalanya metode Stepest Descent lebih baik dari Newton dan hal ini dapat dilihat pada contoh kedua yakni dengan soal yang sama seperti contoh satu,

namun

titik

awal

X 1 yang

berbeda. 4. Dari contoh dua, metode Stepest Descent terinduksi membutuhkan iterasi yang lebih panjang dari dua metode sebelumnya. Hal ini dikarenakan adanya induksi dari Newton kepada Stepest Descent untuk menggantikan arah pencarian d k pada Stepest Descent

Anton, Aljabar Linier, Penerjemah Pantur Silaban, Jakarta: Erlangga, 1991. Edwin K. P. Chong, An Introduction to Optimization, USA: John Wiley & Sons, Inc. 2001. S. Bazaraa. Mochtar, Nonlinear Programming Theory and Algorithms, London: Willey Interscience, 2006. Yoshikazu Sawaragi, Theory of multiobjective optimization, London: Academic Press Inc. 1985. Rukmono Budi Utomo, (2016, Mei), Materi Ajar Metode Numerik FKIP UMT, http://www.fkip.umt.ac.id/download s.

RIWAYAT HIDUP PENULIS Rukmono Budi Utomo, M.Sc. Lahir di Tangerang 26 September 1991. Penulis merupakan alumnus S1 Matematika Undip (2013), S2 Matematika UGM (2015) dan sekarang selain bekerja sebagai Dosen di Prodi Pendidikan Matematika UMT, Penulis juga mahasiswa program Doktoral Matematika ITB.Nama Penulis dilengkapi dengan gelar.

UCAPAN TERIMA KASIH Ucapan terima penulis sampaikan kepada Universitas Muhammadiyah Tangerang atas segala dukungan sehingga paper ini dapat terselesaikan.

DAFTAR PUSTAKA [1] Rinaldi

Munir, Metode numeric, Bandung: Informatika, 2008. [2] Salmah. Diktat Optimisasi. Yogyakarya: FMIPA UGM, 2011. 194


METODE NUMERIK STEPEST DESCENT TERINDUKSI NEWTON

Recommend Documents