PERBANDINGAN WAKTU EKSEKUSI METODE STEEPEST DESCENT DAN METODE BARZILAI-BORWEIN MENGGUNAKAN PERANGKAT LUNAK MATLAB KIKI SEPTIANI

PERBANDINGAN WAKTU EKSEKUSI METODE STEEPEST DESCENT DAN METODE BARZILAI-BORWEIN MENGGUNAKAN PERANGKAT LUNAK MATLAB

KIKI SEPTIANI

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015

PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Perbandingan Waktu Eksekusi Metode Steepest Descent dan Metode Barzilai-Borwein Menggunakan Perangkat Lunak MATLAB adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Januari 2015 Kiki Septiani NIM G54100017

ABSTRAK KIKI SEPTIANI. Perbandingan Waktu Eksekusi Metode Steepest Descent dan Metode Barzilai-Borwein Menggunakan Perangkat Lunak MATLAB. Dibimbing oleh BIB PARUHUM SILALAHI dan MUHAMMAD ILYAS. Pengoptimuman adalah ilmu yang berhubungan dengan mencari nilai maksimum dan minimum. Suatu masalah pengoptimuman terdiri dari masalah pengoptimuman tak berkendala dan pengoptimuman berkendala. Selama lebih dari empat puluh tahun telah banyak algoritme pencarian langsung untuk masalah pengoptimuman tanpa kendala yang dikembangkan, antara lain adalah metode steepest descent dan metode Barzilai-Borwein. Untuk beberapa kasus, kekonvergenan dari metode steepest descent ke solusi optimal membutuhkan waktu panjang. Hal ini terjadi karena jalur zig-zag dalam menuju solusi optimal. Barzilai dan Borwein memperkenalkan dua stepsize yang menjamin konvergensi yang lebih cepat. Penelitian ini mengonstruksi metode steepest descent dan metode Barzilai-Borwein kemudian melakukan perbandingan waktu eksekusi antara kedua metode tersebut dengan menggunakan perangkat lunak MATLAB. Dalam penelitian ini diperoleh kesimpulan bahwa waktu eksekusi metode Barzilai-Borwein lebih cepat dibandingkan dengan metode steepest descent. Kata kunci: MATLAB, Metode Barzilai-Borwein, Metode Steepest Descent, Pengoptimuman

ABSTRACT KIKI SEPTIANI. Execution Time Comparison between the Steepest Descent and Barzilai-Borwein Methods by Using MATLAB. Supervised by BIB PARUHUM SILALAHI and MUHAMMAD ILYAS. Optimization is a knowledge associated with problems of the maximum and minimum determination. The optimization problems consist of the problems without constraint and with constraint. In the last forty years time, many direct search algorithms for optimization problems without constraint have been developed, including the steepest descent method and the Barzilai-Borwein method. In some cases, the convergence of the steepest descent method requires a longer time to reach the optimal solution. This is due to the zig-zag path undertaken. Barzilai and Borwein introduce two stepsize that guarantees to obtain a convergent solution. This research reconstructs the steepest descent and the Barzilai-Borwein methods and then the execution time required between the both methods were compared using MATLAB. Based on the experiments obtained, the Barzilai-Borwein method reached its convergence value faster than the steepest descent method. Keywords: Barzilai-Borwein Method, MATLAB, Optimization, Steepest Descent Method

PERBANDINGAN WAKTU EKSEKUSI METODE STEEPEST DESCENT DAN METODE BARZILAI-BORWEIN MENGGUNAKAN PERANGKAT LUNAK MATLAB

KIKI SEPTIANI

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015

PRAKATA Puji dan syukur saya panjatkan kepada Allah subhanahu wa ta’ala atas segala nikmat, rahmat, karunia dan pertolongan yang telah diberikan sehingga karya ilmiah ini berhasil diselesaikan. Judul karya ilmiah ini adalah Perbandingan Waktu Eksekusi Metode Steepest Descent dan Metode Barzilai-Borwein Menggunakan Perangkat Lunak MATLAB. Terima kasih saya ucapkan kepada keluarga tercinta Ayahanda Rusdi, Ibunda Dini, dan ketiga adik saya Yonanda, Elsa, dan Didi atas segala doa dan dukungan selama menulis karya ilmiah ini. Ungkapan terima kasih juga saya sampaikan kepada Bapak Dr Ir Bib Paruhum Silalahi, MKom dan Bapak Muhammad Ilyas, MSi, MSc selaku dosen pembimbing yang telah banyak memberi saran, kesabaran dan ilmu, serta Ibu Dra Farida Hanum, MSi selaku dosen penguji. Tidak lupa penulis mengucapkan terima kasih untuk para sahabat Mira Aisyah Romliyah, Leny Yustie Widiasari, Aisatul Mustaqimah, Erjodi Cahyo, Fachriadi Fadhillah, Lola Oktasari, Novia Yuliani, Ervina Marviana, teman-teman seperjuangan Matematika 47, dan kakak- kakak Matematika 46 atas bantuan dan dukungannya serta teman-teman sekalian di luar Departemen Matematika IPB. Semoga karya ilmiah ini bermanfaat. Bogor, Januari 2015 Kiki Septiani

DAFTAR ISI DAFTAR TABEL

vi

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vi

PENDAHULUAN

1

Latar Belakang

1

Tujuan Penelitian

1

TINJAUAN PUSTAKA

2

HASIL DAN PEMBAHASAN

4

Metode Steepest Descent

4

Metode Barzilai-Borwein

6

Ilustrasi Metode Steepest Descent dan Metode Barzilai-Borwein

8

Hasil Komputasi Metode Steepest Descent dan Metode Barzilai-Borwein SIMPULAN DAN SARAN

11 15

Simpulan

15

Saran

15

DAFTAR PUSTAKA

16

LAMPIRAN

17

RIWAYAT HIDUP

32

DAFTAR TABEL 1 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi dua variabel dengan lima kali pengulangan 2 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi tiga variabel dengan tiga kali pengulangan 3 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi empat variabel dengan tiga kali pengulangan 4 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi lima variabel dengan tiga kali pengulangan 5 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi sepuluh variabel dengan lima kali pengulangan 6 Perbedaan iterasi rata-rata metode steepest descent dan metode Barzilai-Borwein 7 Perbedaan waktu eksekusi (dalam second) rata-rata metode steepest descent dan metode Barzilai-Borwein

11

11

12

12

12 13 13

DAFTAR GAMBAR 1 2 3 4 5 6

Hasil metode steepest descent Hasil metode steepset descent yang diperbesar Hasil metode Barzilai-Borwein 1 Hasil metode Barzilai-Borwein 2 Iterasi rata-rata metode steepest descent dan metode Barzilai-Borwein Waktu eksekusi rata-rata metode steepest descent dan metode BarzilaiBorwein

9 9 10 10 14 14

DAFTAR LAMPIRAN 1 Sintaks metode steepest descent percobaan ke-1 dengan dua variabel 2 Sintaks metode Barzilai-Borwein 1 percobaan fungsi dengan dua variabel 3 Sintaks metode Barzilai-Borwein 2 percobaan fungsi dengan dua variabel 4 Sintaks metode steepest descent percobaan ke-1 dengan tiga variabel 5 Sintaks metode Barzilai-Borwein 1 percobaan fungsi dengan tiga variabel 6 Sintaks metode Barzilai-Borwein 2 percobaan fungsi dengan tiga variabel

Tabel 1 untuk fungsi 17 ke-1 Tabel 1 untuk 18 ke-1 Tabel 1 untuk 19 Tabel 2 untuk fungsi 20 ke-1 Tabel 2 untuk 21 ke-1 Tabel 2 untuk 22

7 Sintaks metode steepest descent percobaan ke-1 dengan empat variabel 8 Sintaks metode Barzilai-Borwein 1 percobaan fungsi dengan empat variabel 9 Sintaks metode Barzilai-Borwein 2 percobaan fungsi dengan empat variabel 10 Sintaks metode steepest descent percobaan ke-1 dengan lima variabel 11 Sintaks metode Barzilai-Borwein 1 percobaan fungsi dengan lima variabel 12 Sintaks metode Barzilai-Borwein 2 percobaan fungsi dengan lima variabel 13 Sintaks metode steepest descent percobaan ke-1 dengan sepuluh variabel 14 Sintaks metode Barzilai-Borwein 1 percobaan fungsi dengan sepuluh variabel 15 Sintaks metode Barzilai-Borwein 2 percobaan fungsi dengan sepuluh variabel

Tabel 3 untuk fungsi 23 ke-1 Tabel 3 untuk 24 ke-1 Tabel 3 untuk 25 Tabel 4 untuk fungsi 26 ke-1 Tabel 4 untuk 27 ke-1 Tabel 4 untuk 28 Tabel 5 untuk fungsi 29 ke-1 Tabel 5 untuk 30 ke-1 Tabel 5 untuk 31

PENDAHULUAN Latar Belakang Pengoptimuman bertujuan mencari nilai minimum atau maksimum dari suatu fungsi bernilai real. Secara umum, ada dua jenis pengoptimuman yang sering dihadapi, yaitu pengoptimuman linear dan pengoptimuman taklinear. Masalah pengoptimuman terdiri dari fungsi tujuan dan kendala, jika kendalanya tidak ada maka masalah pengoptimuman tersebut dinamakan masalah pengoptimuman tak berkendala sebaliknya jika kendalanya ada maka masalah pengoptimuman tersebut dinamakan pengoptimuman berkendala. Masalah pengoptimuman tak berkendala satu variabel dapat diselesaikan dengan menggunakan kalkulus. Selama lebih dari empat puluh tahun telah banyak algoritme pencarian langsung (direct search) untuk masalah pengoptimuman tak berkendala yang dikembangkan. Algoritme-algoritme ini memerlukan titik awal (dinyatakan dengan ) untuk memulai proses pencarian solusi optimal langsung dari titik menuju dan seterusnya. Proses akan berhenti jika tidak diperoleh titik yang lebih baik (lebih kecil nilai fungsinya, untuk masalah peminimuman) atau jika diperoleh titik sehingga , atau dengan kriteria pemberhentian lainnya. Beberapa metode pencarian langsung untuk meminimumkan fungsi banyak variabel, yaitu metode golden section, metode Newton, dan algoritme interpolasi kuadratik Powell. Metode steepest descent merupakan salah satu metode klasik untuk menyelesaikan masalah pengoptimuman tak berkendala fungsi banyak variabel. Untuk beberapa kasus kekonvergenan dari metode steepest descent menuju ke solusi optimal lambat, hal ini terjadi karena jalur zig-zag dalam menuju solusi optimal (Sun dan Yuan 2006). Barzilai dan Borwein memperkenalkan dua stepsize yang menjamin konvergensi yang lebih baik. Metode Barzilai-Borwein bertujuan mempercepat konvergensi metode steepest descent (Barzilai dan Borwein 1988). Dalam karya ilmiah ini dibahas perbandingan waktu eksekusi dan banyaknya iterasi antara metode steepest descent dan metode Barzilai-Borwein dengan menggunakan perangkat lunak MATLAB.

Tujuan Penelitian Karya ilmiah ini disusun dengan tujuan melakukan perbandingan waktu eksekusi antara metode steepest descent dan metode Barzilai-Borwein dengan menggunakan perangkat lunak MATLAB.

2

TINJAUAN PUSTAKA Fungsi Kuadratik Suatu fungsi dinamakan fungsi kuadratik dalam variabel jika dapat dituliskan sebagai: , dengan , dan vektor real berukuran , dan matriks real berukuran (Luenberger dan Ye 2008).

Matriks Simetrik Suatu matriks atau

berorde disebut matriks simetrik jika . Matriks diagonal merupakan matriks simetrik. Contoh:

,

(Leon 2001).

Definit Positif Misalkan matriks berukuran dan misalkan adalah bentuk kuadratik yang berpadanan dengan , maka dikatakan definit positif jika untuk setiap (Luenberger dan Ye 2008).

Metode Interpolasi Kuadrat dengan Dua Titik Metode interpolasi kuadrat dengan dua titik adalah metode untuk menentukan hampiran titik minimum suatu fungsi kuadrat dengan menggunakan dua titik. Misalkan diberikan dua titik dan nilai fungsinya (atau ), dan dua nilai turunan dan . Polinomial yang digunakan untuk proses interpolasi adalah . Dengan memasukkan dua titik tersebut ke dalam fungsi diperoleh sistem persamaan linear:

sehingga diperoleh:

= Oleh karena itu, didapatkan pola iterasi:

3

(Sun dan Yuan 2006).

Metode Newton Metode Newton adalah salah satu prosedur iteratif untuk menyelesaikan masalah taklinear. Misalkan persamaan adalah persamaan taklinear dengan merupakan penyelesaian dari persamaan tersebut. Fungsi adalah fungsi yang kontinu dan terturunkan. Pada solusi eksak , nilai fungsi dapat dinyatakan sebagai dan nilai dari fungsi turunan pertama adalah . Nilai adalah solusi yang diperoleh pada iterasi ke- . Misalkan , dapat diartikan sebagai laju perubahan terhadap . Andaikan berubah dari ke maka perubahan pada adalah . Perubahan ini diperlukan untuk mengubah nilai fungsi menuju nol. Selanjutnya, metode Newton dapat diturunkan dari ekspansi deret Taylor orde pertama dari di sekitar , sebagai berikut:

. Tetapkan pendekatan

sehingga didapat:

Barisan Newton yang diperoleh adalah:

dengan menyatakan nilai yang diperoleh pada iterasi ke- . Jika titik awal cukup dekat dengan maka nilai dari akan mendekati dengan (Jensen & Bard 2003).

Metode Least Square (LS) Misalkan pengamatan

diperoleh untuk

(Draper dan Smith 1992).

memiliki solusi suatu

model maka

dan dari data

dengan dapat diduga dengan cara berikut:

4

Hasil Kali Skalar di dalam Vektor-vektor di dalam dapat digambarkan dengan segmen-segmen garis berarah. Jika diberikan sebuah vektor di , maka panjang Euclidenya dapat didefinisikan dalam bentuk hasil kali skalar: jika (Leon 2001).

HASIL DAN PEMBAHASAN Metode Steepest Descent Metode line search descent yang menggunakan vektor gradien (turunan parsial orde pertama dari fungsi ) untuk menentukan arah pencarian di setiap iterasi, dinamakan metode line search descent orde pertama. Metode terkenal yang banyak digunakan adalah metode steepest descent yang pertama kali diperkenalkan oleh Cauchy pada tahun 1847. Metode steepest descent adalah salah satu metode yang tertua dan paling banyak dikenal untuk meminimalkan fungsi dari beberapa variabel. Metode steepest descent sangat penting karena metode ini merupakan salah satu dari yang paling sederhana dan metode peminimuman yang paling mendasar untuk pengoptimuman tanpa kendala (sering disebut sebagai metode gradien). Metode steepest descent merupakan metode iteratif untuk memperoleh solusi pendekatan dari masalah awal. Algoritme yang lebih maju sering termotivasi oleh upaya untuk memodifikasi teknik dasar steepest descent sehingga algoritme baru akan memiliki sifat konvergensi yang unggul. Teknik ini tidak hanya paling sering digunakan dalam penyelesaian masalah baru, tetapi juga standar acuan terhadap teknik lain yang diukur. Metode steepest descent selalu konvergen. Artinya, secara teori metode ini tidak akan berhenti atau akan terus melakukan iterasi sampai kriteria penghentian terpenuhi (Luenberger dan Ye 2008). Pencarian arah adalah hal yang penting dalam metode steepest descent, dan pencarian ini yang membedakan antara algoritme yang satu dengan yang lainnya. Begitu pencarian arah telah ditentukan maka tahap selanjutnya adalah pencarian stepsize (line search, step search). Masalah model kuadrat dinyatakan sebagai berikut: (1) dengan adalah symmetric positive definite (SPD) dan ini setara dengan memecahkan sistem linear:

.

. Masalah

5 Karena diandaikan adalah definit positif, masalah (1) memiliki solusi yang unik yang diberikan oleh . Metode steepest descent yang dikenal juga dengan metode gradien adalah metode yang mencari penurunan tercepat dari: , yang terjadi pada: dan Berikut bentuk iterasi gradien: (2) Untuk beberapa kasus, kekonvergenan dari metode steepest descent ke solusi optimal lambat, hal ini karena jalur zig-zag dalam menuju solusi optimal. Secara intuitif arah adalah arah dengan penurunan tercepat, tetapi secara global tidak berarti menuju titik minimum lokal yang tercepat. Untuk mencari minimum dari , diperoleh:

. Ini berarti gradien dari titik awal menuju titik selanjutnya saling tegak lurus (ortogonal) pada metode steepest descent. Dari persamaan (2) didapat pilihan stepsize optimal sebagai berikut:

dengan

6 Berikut ini diberikan algoritme metode steepest descent: Langkah 1 Batas toleransi . Diberikan titik awal . Langkah 2 Arah pencarian . Langkah 3 Tentukan stepsize yang meminimumkan

Langkah 4 Tentukan Langkah 5 Jika Langkah 6 Selanjutnya (Sun dan Yuan 2006).

dengan

sehingga

. stop. kembali ke langkah 2.

Metode Barzilai-Borwein Barzilai dan Borwein memperkenalkan metode gradien two-point stepsize yang biasanya disebut metode gradien Barzilai-Borwein (atau BB) untuk memecahkan masalah peminimuman fungsi tak berkendala (Barzilai dan Borwein 1988). Berikut bentuk iterasi gradien: (3) Pada awalnya digunakan metode Newton untuk memecahkan suatu persamaan nonlinear , dengan pendekatan yang berasal dari (juga dikenal sebagai metode sekan) dengan iterasi sebagai berikut: (4) dengan

dan misalkan: (5)

Dapat dilihat hubungan antara persamaan (3) dan persamaan (4) untuk menyelesaikan persamaan , . Dalam kasus dimensi lebih tinggi, yaitu koefisien akan dievaluasi menggunakan persamaan (5). Untuk menentukan stepsize metode Barzilai-Borwein 1, perhatikan persamaan berikut:

.

(6)

7 Selanjutnya persamaan (6) diselesaikan dengan metode least-square, dengan , sehingga diperoleh:

. Dengan menggunakan syarat perlu minimum bahwa turunan pertama sama dengan nol, sehingga diperoleh:

Untuk menentukan stepsize metode Barzilai-Borwein 2, perhatikan persamaan berikut: (7) Selanjutnya persamaan (7) diselesaikan dengan metode least-square, dengan , sehingga diperoleh:

8

. Dengan menggunakan syarat perlu minimum bahwa turunan pertama sama dengan nol, sehingga diperoleh:

Berikut ini diberikan algoritme metode gradien Barzilai-Borwein: Langkah 1 Diberikan titik awal , batas toleransi , dengan . Langkah 2 Arah pencarian . Langkah 3 Jika , tentukan dengan pencarian garis untuk , hitung

dengan

(untuk metode Barzilai-Borwein 1) atau

(untuk metode Barzilai-Borwein 2). Langkah 4 Tentukan Langkah 5 Jika Langkah 6 Selanjutnya (Sun dan Yuan 2006).

. , stop. , kembali ke langkah 2.

Ilustrasi Metode Steepest Descent dan Metode Barzilai-Borwein Ilustrasi 1 Dengan menggunakan metode steepest descent, min dengan titik awal . Berikut adalah solusi dari metode steepest descent untuk ilustrasi 1:

9

Gambar 1 Hasil metode steepest descent

Gambar 2 Hasil metode steepest descent yang diperbesar Gambar 1 dan Gambar 2 menunjukkan bahwa dalam menuju solusi optimal, metode steepest descent mengambil arah zig-zag dan tegak lurus (ortogonal) seperti yang telah dijelaskan pada subbab metode steepest descent. Ilustrasi 2 Dengan menggunakan metode Barzilai-Borwein 1, dengan titik awal dan arah:

10 Berikut adalah solusi dari metode Barzilai-Borwein 1 untuk ilustrasi 2:

Gambar 3 Hasil metode Barzilai-Borwein 1 Ilustrasi 3 Dengan menggunakan metode Barzilai-Borwein 2, min dengan titik awal dan arah:

Berikut adalah solusi dari metode Barzilai-Borwein 2 untuk ilustrasi 3:

Gambar 4 Hasil metode Barzilai-Borwein 2 Metode Barzilai-Borwein sebenarnya mirip dengan metode gradien, lebih cepat konvergen sehingga membutuhkan sedikit pekerjaan komputasi. Berbeda dengan metode steepest descent, metode Barzilai-Borwein dalam menuju solusi optimal gradien dari titik awal menuju titik selanjutnya tidak saling tegak lurus (ortogonal).

11 Hasil Komputasi Metode Steepest Descent dan Metode Barzilai-Borwein Fungsi yang digunakan dibangkitkan secara acak dengan ketentuan sebagai berikut: . dengan matriks simetrik berukuran . Banyak variabel yang digunakan yaitu . Setiap komponen vektor ( ) dipilih secara acak dengan . Untuk semua kasus diberikan titik awal adalah vektor nol dan kriteria penghentian adalah . Perbedaan waktu eksekusi antara metode steepest descent dan metode Barzilai-Borwein dapat dilihat pada Tabel 1 untuk fungsi dengan dua variabel, Tabel 2 untuk fungsi dengan tiga variabel, Tabel 3 untuk fungsi dengan empat variabel, Tabel 4 untuk fungsi dengan lima variabel, dan Tabel 5 untuk fungsi dengan sepuluh variabel. Tabel 1 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi dua variabel dengan lima kali pengulangan Percobaan I II III IV V Rata-rata

Metode Steepest Descent Iterasi Waktu (s) 46 22.818351 23 14.314749 7 4.408219 10 6.706132 5 3.055573 18.2 10.260604

Metode BarzilaiBorwein 1 Iterasi Waktu (s) 12 1.723524 8 1.394232 4 0.970558 9 1.510808 5 1.070897 7.6 1.334004

Metode BarzilaiBorwein 2 Iterasi Waktu (s) 11 1.617948 5 1.121589 5 1.084019 6 1.204922 3 0.848222 6 1.175340

Tabel 2 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi tiga variabel dengan lima kali pengulangan Percobaan I II III IV V Rata-rata

Metode Steepest Descent Iterasi Waktu (s) 177 135.238922 40 30.059106 80 57.168624 127 89.093572 111 80.613021 107 78.434649



12 Tabel 3 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi empat variabel dengan lima kali pengulangan Percobaan I II III IV V Rata-rata




Tabel 4 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi lima variabel dengan lima kali pengulangan Percobaan I II III IV V Rata-rata




Tabel 5 Analisis perbedaan banyak iterasi dan waktu eksekusi (dalam second) metode steepest descent dan metode Barzilai-Borwein untuk fungsi sepuluh variabel dengan lima kali pengulangan Percobaan I II III IV V Rata-rata

Metode Steepest Descent Iterasi Waktu (s) > 7000 > 7200 > 5000 > 3600 2296 1113.4 > 5000 > 3600 > 5000 > 3600 > 5000 > 3600



Pada Tabel 1, 2, 3, 4, dan 5 dapat dilihat bahwa waktu eksekusi yang diperoleh untuk menyelesaikan masalah pengoptimuman tak berkendala fungsi banyak variabel dilakukan dengan pengulangan eksekusi. Untuk semua fungsi dilakukan lima kali pengulangan eksekusi dengan fungsi yang sama, sehingga mendapatkan hasil waktu eksekusi yang berbeda-beda. Hal tersebut dipengaruhi oleh keadaan kinerja komputer pada saat melakukan komputasi. Adanya

13 perbedaan hasil eksekusi tersebut, selanjutnya dilakukan penghitungan nilai ratarata waktu eksekusi untuk mempermudah menganalisis perbedaan waktu eksekusi antara metode steepest descent dan metode Barzilai-Borwein. Perbedaan rata-rata banyak iterasi dan waktu eksekusi antara metode steepest descent dan metode Barzilai-Borwein dengan menggunakan perangkat lunak MATLAB, dapat dilihat pada Tabel 6 dan Tabel 7. Tabel 6 Perbedaan iterasi rata-rata metode steepest descent dan metode BarzilaiBorwein Banyak Iterasi Studi Kasus

Ukuran

1 2 3 4 5

Metode Steepest Descent 18.2 107.0 462.4 709.4 > 5000

Metode BarzilaiBorwein 1 7.6 27.0 54.0 74.2 509.8


Tabel 7 Perbedaan waktu eksekusi (dalam second) rata-rata metode steepest descent dan metode Barzilai-Borwein Waktu Eksekusi (s) Studi Kasus 1 2 3 4 5

Ukuran

Metode Steepest Descent

Metode BarzilaiBorwein 1

10.260604 78.434649 435.520938 570.444200 > 3600

1.334004 5.372200 13.470665 23.814913 581.736473


Perbedaan iterasi dan waktu eksekusi rata-rata metode steepest descent dan metode Barzilai-Borwein disajikan juga dalam bentuk grafik sebagai berikut:

14 800 700 SD

Banyak Iterasi

600

BB 1

500

BB 2

400 300 200 100

0 2×2

3×3

4×4

5×5

10 × 10

Gambar 5 Iterasi rata-rata metode steepest descent dan metode BarzilaiBorwein 700 SD 600

BB 1 BB 2

Waktu Eksekusi (s)

500 400 300 200 100 0 2×2

3×3

4×4

5×5

10 × 10

Gambar 6 Waktu eksekusi rata-rata metode steepest descent dan metode Barzilai-Borwein Pada Gambar 5 menunjukkan perbedaan iterasi rata-rata metode steepest descent dan metode Barzilai-Borwein. Iterasi metode steepest descent lebih besar

15 dibandingkan dengan metode Barzilai-Borwein. Untuk data berukuran , metode steepest descent tidak diplot pada grafik. Hal ini disebabkan iterasi yang masih berlanjut selama lebih dari 24 jam. Pada Gambar 6 jelas terlihat perbedaan waktu eksekusi rata-rata metode steepest descent dan metode Barzilai-Borwein. Pada data berukuran perbedaan waktu eksekusi rata-rata metode steepest descent dan metode BarzilaiBorwein tidak terlihat menonjol. Pada data berukuran dan data berukuran sudah mulai terlihat waktu eksekusi metode steepest descent semakin naik. Sebaliknya, metode Barzilai-Borwein juga sudah mengalami kenaikan akan tetapi sangat kecil. Pada data berukuran terlihat sangat menonjol perbedaan waktu eksekusi rata-rata antara metode steepest descent dan metode Barzilai-Borwein. Untuk metode Barzilai-Borwein dengan kasus stepsize yang berbeda, perbedaan waktu eksekusi rata-rata sangat kecil. Pada data berukuran , data berukuran , dan data berukuran metode Barzilai-Borwein 1 waktu eksekusi rata-rata lebih besar dibandingkan dengan waktu eksekusi rata-rata metode Barzilai-Borwein 2. Sebaliknya, pada data berukuran dan data berukuran waktu eksekusi rata-rata metode Barzilai-Borwein 1 lebih kecil dibandingkan dengan metode Barzilai-Borwein 2. Untuk data berukuran , waktu eksekusi rata-rata metode steepest descent tidak diplot pada grafik sedangkan metode Barzilai-Borwein 1 dan metode Barzilai-Borwein 2 sebesar 581.7364732 second dan 409.311843 second. Hal ini disebabkan waktu eksekusi yang sangat lama yaitu lebih dari 24 jam dan prosesnya masih berlanjut.

SIMPULAN DAN SARAN Simpulan Metode steepest descent merupakan salah satu metode klasik untuk menyelesaikan pengoptimuman tak berkendala fungsi banyak variabel dan paling sering digunakan. Metode steepest descent sangat lambat ke solusi optimal, hal ini terjadi karena jalur zig-zag dalam menuju solusi optimal. Metode steepest descent berkinerja buruk dan iterasi yang dihasilkan lebih banyak untuk dimensi yang lebih tinggi. Barzilai dan Borwein memperkenalkan dua stepsize yang menjamin konvergensi yang lebih baik. Metode Barzilai-Borwein bertujuan mempercepat konvergensi metode steepest descent. Berdasarkan analisis pada studi kasus yang dilakukan dengan menggunakan perangkat lunak MATLAB, hasil perbandingan waktu eksekusi metode Barzilai-Borwein lebih cepat dibandingkan dengan metode steepest descent baik untuk dimensi rendah maupun untuk dimensi tinggi.

Saran Karya Ilmiah ini dapat dilanjutkan dengan metode yang berbeda atau dengan menggunakan perangkat lunak yang berbeda.

16

DAFTAR PUSTAKA Barzilai J, Borwein JM. 1988. Two-point stepsize gradient methods. IMA Journal of Numerical Analysis. 8(1):141-148.doi: 10.1093/imanum/8.1.141. Draper N, Smith H. 1992. Analisis Regresi Terapan. Ed ke-2. Sumantri B, penerjemah. Jakarta (ID): Gramedia Pustaka Utama. Terjemahan dari: Applied Regression Analysis. Jensen PA, Bard JF. 2003. Operations Research Models and Methods. New York (US): John Wiley and Sons. Leon SJ. 2001. Aljabar Linear dan Aplikasinya. Ed ke-5. Bondan A, penerjemah; Hardani HW, editor. Jakarta (ID): Penerbit Erlangga. Terjemahan dari: Linear Algebra with Applications. Luenberger DG, Ye Y. 2008. Linear and Nonlinear Programming. Ed ke-3. New York (US): Springer. Sun W, Yuan YX. 2006. Optimization Theory and Methods. New York (US): Springer.

17 Lampiran 1 Sintaks metode steepest descent percobaan ke-1 Tabel 1 untuk fungsi dengan dua variabel

18 Lampiran 2 Sintaks metode Barzilai-Borwein 1 percobaan ke-1 Tabel 1 untuk fungsi dengan dua variabel

19 Lampiran 3 Sintaks metode Barzilai-Borwein 2 percobaan ke-1 Tabel 1 untuk fungsi dengan dua variabel

20 Lampiran 4 Sintaks metode steepest descent percobaan ke-1 Tabel 2 untuk fungsi dengan tiga variabel

21 Lampiran 5 Sintaks metode Barzilai-Borwein 1 percobaan ke-1 Tabel 2 untuk fungsi dengan tiga variabel

22 Lampiran 6 Sintaks metode Barzilai-Borwein 2 percobaan ke-1 Tabel 2 untuk fungsi tiga variabel

23 Lampiran 7 Sintaks metode steepest descent percobaan ke-1 Tabel 3 untuk fungsi dengan empat variabel

24 Lampiran 8 Sintaks metode Barzilai-Borwein 1 percobaan ke-1 Tabel 3 untuk fungsi dengan empat variabel

25 Lampiran 9 Sintaks metode Barzilai-Borwein 2 percobaan ke-1 Tabel 3 untuk fungsi dengan empat variabel

26 Lampiran 10 Sintaks metode steepest descent percobaan ke-1 Tabel 4 untuk fungsi dengan lima variabel

27 Lampiran 11 Sintaks metode Barzilai-Borwein 1 percobaan ke-1 Tabel 4 untuk fungsi dengan lima variabel

28 Lampiran 12 Sintaks metode Barzilai-Borwein 2 percobaan ke-1 Tabel 4 untuk fungsi dengan lima variabel

29 Lampiran 13 Sintaks metode steepest descent percobaan ke-1 Tabel 5 untuk fungsi dengan sepuluh variabel

30 Lampiran 14 Sintaks metode Barzilai-Borwein 1 percobaan ke-1 Tabel 5 untuk fungsi dengan sepuluh variabel

31 Lampiran 15 Sintaks metode Barzilai-Borwein 1 percobaan ke-1 Tabel 5 untuk fungsi dengan sepuluh variabel

32

RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 14 September 1992 sebagai anak pertama dari empat bersaudara, dari pasangan Rusdi dan Dini. Pada tahun 1998, penulis lulus dari TK Islam Raudatul Amanah Bekasi. Pada tahun 2001, penulis lulus dari SD Negeri Kaliabang Tengah V Bekasi. Pada tahun 2007, penulis lulus dari SMP Negeri 234 Jakarta. Pada tahun 2010, penulis lulus dari SMA Negeri 89 Jakarta dan pada tahun yang sama penulis diterima di Departemen Matematika IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Selama masa perkuliahan penulis aktif pada lembaga kemahasiswaan IPB, di antaranya Staf Biro Keuangan Gumatika IPB tahun kepengurusan 2012/2013 dan menjadi Staf Divisi Kewirausahaan Gumatika IPB tahun kepengurusan 2011/2012. Penulis juga aktif dalam kepanitiaan di antaranya Olimpiade Mahasiswa IPB (OMI), Matematika Ria, Math Ice, IPB Mathematics Challenge, Math Camp, dan SPIRIT FMIPA IPB. Selain itu, penulis juga aktif di UKM Futsal Putri IPB.

PERBANDINGAN WAKTU EKSEKUSI METODE STEEPEST DESCENT DAN METODE BARZILAI-BORWEIN MENGGUNAKAN PERANGKAT LUNAK MATLAB KIKI SEPTIANI

Recommend Documents