1
METODE STEEPEST DESCENT DENGAN UKURAN LANGKAH BARU UNTUK PENGOPTIMUMAN NIRKENDALA
DJIHAD WUNGGULI
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2015
2
3
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA* Dengan ini saya menyatakan bahwa tesis berjudul Metode Steepest Descent dengan Ukuran Langkah Baru utuk Pengoptimuman Nirkendala 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 tesis ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Februari 2015 Djihad Wungguli NIM G551120031
4
RINGKASAN DJIHAD WUNGGULI. Metode Steepest Descent dengan Ukuran Langkah Baru untuk Pengoptimuman Nirkendala. Dibimbing oleh BIB PARUHUM SILALAHI dan SUGI GURITMAN. Masalah pengoptimuman dapat dikategorikan dalam dua bagian yaitu pengoptimuman berkendala dan pengoptimuman nirkendala. Untuk menyelesaikan permasalahan pengoptimuman nirkendala, khususnya untuk fungsi nonlinear dapat digunakan metode steepest descent. Metode steepest descent merupakan prosedur paling mendasar yang diperkenalkan oleh Cauchy pada tahun 1847. Metode ini adalah metode gradien sederhana yang menggunakan vektor gradien untuk menentukan arah pencarian pada setiap iterasi. Kemudian, dari arah tersebut akan ditentukan besar ukuran langkahnya. Pada beberapa kasus, metode steepest descent ini memiliki kekonvergenan yang lambat menuju solusi optimum karena langkahnya berbentuk zig-zag. Hal ini menunjukkan bahwa masalah pemilihan ukuran langkah menjadi masalah penting. Penelitian tentang pencarian ukuran langkah diantaranya adalah metode Barzilai-Borwein, Alternatif Minimisasi dan metode Yuan. Penelitian ini memiliki tiga tujuan utama yaitu: (1) merekonstruksi algoritme steepest descent, Barzilai-Borwein, Alternatif Minimisasi, dan algoritme Yuan; (2) memodifikasi metode steepest descent dengan ukuran langkah baru; dan (3) membandingkan secara eksperimental output dari modifikasi algoritme dengan metode steepest descent, Barzilai-Borwein, Alternatif Minimisasi, dan Yuan untuk kasus fungsi kuadratik ditinjau dari proses iterasi dan running time. Metode dalam penelitian ini disusun melalui tiga tahap, (1) melakukan telaah pustaka metode steepest descent klasik, metode BarzilaiBorwein, metode Alternatif Minimisasi dan metode Yuan, (2) memodifikasi ukuran langkah pada metode steepest descent dengan ukuran langkah yang baru, (3) mengimplementasikan algoritme tersebut menggunakan perangkat lunak. Kemudian dilakukan pengujian dan perbandingan untuk kasus fungsi kuadratik yang dibangkitkan secara acak. Dalam penelitian ini dihasilkan dua modifikasi ukuran langkah baru disebut Algoritme (4.5) dan Algoritme (4.6). Kedua modifikasi ini merupakan gabungan dari metode steepest descent dan metode Yuan. Dari rata-rata hasil perbandingan masalah fungsi kuadratik untuk semua dimensi metode steepest descent memberikan kinerja yang buruk dibandingkan dengan metode lainnya. Selanjutnya pada masalah dengan dimensi yang kecil, metode Yuan mampu menemukan solusi nilai minimum dengan iterasi dan running time yang terkecil. Meskipun demikian Algoritme (4.5) dan (4.6) mampu menyeimbangi kecepatan metode Yuan dan mampu mengungguli hasil dari metode Barzilai-Borwein, serta metode Alternatif Minimisasi. Untuk kasus fungsi kuadratik dengan dimensi yang besar, metode Yuan memberikan hasil yang buruk. Sedangkan, Algoritme (4.5) dan (4.6) menghasilkan iterasi dan running time yang terkecil, hal ini disebabkan oleh tingkat konvergensi yang lebih cepat pada kedua metode ini. Kata kunci: fungsi kuadratik, metode gradien, running time, steepest descent, ukuran langkah baru.
5
SUMMARY DJIHAD WUNGGULI. Steepest Descent Method with New Step Size for Unconstrained Optimization. Supervised by BIB PARUHUM SILALAHI and SUGI GURITMAN. The problem of optimization could be categorized into constrained and unconstrained optimization. The unconstrained optimization problem especially nonlinear function can be solved by steepest descent method. This is a basic procedure as introduced by Cauchy in 1847. It is a simple gradient method that uses gradient vector to determine the search direction in its iteration. Furthermore, from the direction will be determined the size of the step. In many cases, the steepest descent method has a slow convergence towards the optimum solution because of a zigzag steps. It involved indicates that the selection of step size problem is an important issue. There are many studies conducted on searching the step size in the steepest descent method, such as in Barzilai-Borwein, Alternative Minimization and Yuan method. This research has three main objectives: (1) reconstructing the method of steepest descent, Barzilai-Borwein, Alternative Minimization, and the Yuan algorithms; (2) modifying the method of steepest descent by using new step sizes; and (3) comparing experimentally results of modification algorithms steepest descent, Barzilai-Borwein, Alternative Minimization, and Yuan method for quadratic function in terms of the iteration and running time process. This research composed in three stages method, (1) reviewing literatures on the classic steepest descent, Barzilai-Borwein, Alternative Minimization, and Yuan method, (2) modifying the step size in the steepest descent method by new step sizes, (3) computer implementation using software. Furthermore, testing and compared results was carried out using the quadratic function cases that generated randomly. This research has two new step size modifications known as Algorithm (4.5) and (4.6). Both of them are combination of steepest descent and Yuan method. The average results of comparison quadratic function for all steepest descent method dimensions give poor performance compared to the other methods. While for the problem of small dimensions, the Yuan method reached the minimum value solutions with the iteration number and the running time minimum. Nevertheless, the Algorithm (4.5) and (4.6) able to compete the speed of Yuan method and perform better than the Barzilai-Borwein and Alternative Minimization method. For the quadratic functions case with large dimensions, Yuan method gives bad results. While Algorithm (4.5) and (4.6) produce the smallest of iteration and running time than the other methods, it is happen because this is related with the convergence speed within the Algorithm (4.5) and Algorithm (4.6). Keywords: quadratic function, gradient method, running time, steepest descent, .new step size.
6
© Hak Cipta Milik IPB, Tahun 2015 Hak Cipta Dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis ini dalam bentuk apa pun tanpa izin IPB
7
METODE STEEPEST DESCENT DENGAN UKURAN LANGKAH BARU UNTUK PENGOPTIMUMAN NIRKENDALA
DJIHAD WUNGGULI
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Matematika Terapan
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2015
8
Penguji Luar Komisi pada Ujian Tesis: Dr Ir Fahren Bukhari, MSc
9
Judul Tesis : Metode Steepest Descent dengan Ukuran Langkah Baru untuk Pengoptimuman Nirkendala Nama : Djihad Wungguli NIM : G551120031
Disetujui oleh Komisi Pembimbing
Dr Ir Bib Paruhum Silalahi, MKom Ketua
Dr Sugi Guritman Anggota
Diketahui oleh
Ketua Program Studi Matematika Terapan
Dekan Sekolah Pascasarjana
Dr Jaharuddin, MS
Dr Ir Dahrul Syah, MScAgr
Tanggal Ujian: 28 Januari 2015
Tanggal Lulus:
10
PRAKATA Puji dan syukur penulis panjatkan kepada Allah Subhanahu wa ta’ala atas segala nikmat dan karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian yang dilaksanakan sejak bulan Februari 2014 ini ialah teori optimasi, dengan judul Metode Steepest Descent dengan Ukuran Langkah Baru untuk Pengoptimuman Nirkendala. Penulisan tesis ini merupakan salah satu syarat memperoleh gelar Magister Sains pada program studi Matematika Terapan Sekolah Pascasarjana Institut Pertanian Bogor. Dalam proses penulisan tesis ini, penulis menyadari bahwa telah memperoleh dorongan dan bantuan baik moril maupun materil dari berbagai pihak untuk melengkapi keterbatasan-keterbatasan yang dimiliki penulis. Untuk itu, melalui kesempatan ini penulis ingin mengucapkan terima kasih dan rasa hormat yang sebesar-besarnya kepada: 1. Bapak Dr Ir Bib Paruhum Silalahi, MKom selaku pembimbing I dan Bapak Dr Sugi Guritman selaku pembimbing II. 2. Dr Jaharuddin, MS selaku Ketua Program Studi Matematika Terapan. 3. Seluruh dosen dan staf pegawai tata usaha Departemen Matematika. 4. Direktorat Jenderal Pendidikan Tinggi (DIKTI) sebagai sponsor Beasiswa Unggulan. 5. Ayahanda dan Ibunda tercinta, Bapak Usman Wungguli dan Ibu Hadidjah Luther, Adik Rahmad Wungguli dan Rini Wahyuni Mohamad serta seluruh keluarga yang selalu memberikan dorongan dan mendoakan untuk keberhasilan studi bagi penulis. 6. Seluruh mahasiswa Departemen Matematika khususnya teman-teman angkatan tahun 2012 di program studi S2 Matematika Terapan. 7. Seluruh rekan–rekan mahasiswa Asrama Gorontalo di Bogor. 8. Sahabat-sahabat yang tak dapat disebutkan satu persatu yang telah banyak membantu penulis dalam penyelesaian tesis ini. Semoga segala bantuan, bimbingan, dan motivasi yang telah diberikan kepada penulis senantiasa mendapat balasan dari Allah Subhanahu wa ta’ala. Akhirnya, semoga penulisan tesis ini dapat memperkaya pengalaman belajar serta wawasan kita semua.
Bogor, Februari 2015 Djihad Wungguli
11
DAFTAR ISI DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
1 PENDAHULUAN Latar Belakang Tujuan Penelitian
1 1 2
2 TINJAUAN PUSTAKA Ruang Vektor Matriks Ortogonalitas Pengoptimuman Matematik Turunan Parsial Turunan Berarah Vektor Gradien dan Matriks Hesse Minimum Global dan Minimum Lokal Fungsi Kuadratik di Kedefinitan Matriks Kekonveksan Fungsi Tingkat Konvergensi Deret Taylor Ketaksamaan Kantorovich Iterasi dan Running Time
3 3 4 5 6 6 6 7 8 8 8 9 9 10 10 10
3 METODE PENELITIAN
11
4 HASIL DAN PEMBAHASAN Metode Steepest Descent Exact Line Search Kekonvergenan Metode Steepest Descent Metode Barzilai dan Borwein Metode Alternatif Minimisasi Metode Yuan Modifikasi Metode Steepest Descent dengan Ukuran Langkah Baru Hasil Numerik
11 11 14 17 19 20 22 25 26
5 SIMPULAN
31
DAFTAR PUSTAKA
31
LAMPIRAN
32
RIWAYAT HIDUP
42
12
DAFTAR TABEL 1 2
Rata-rata jumlah iterasi dari metode steepest descent Rata-rata running time dari metode steepest descent
27 28
DAFTAR GAMBAR 1 2 3 4 5 6 7
Pencarian arah d gradien terhadap vektor gradien Ilustrasi steepest descent dalam plot kontur Ilustrasi perbandingan metode Alternatif Minimisasi dan steepest descent Perbandingan rata-rata iterasi dan running time dari metode descent untuk λn = 10 Perbandingan rata-rata iterasi dan running time dari metode descent untuk λn = 100 Perbandingan rata-rata iterasi dan running time dari metode descent untuk λn = 1000 Kekonvergenan dari metode steepest descent
12 13 metode 21 steepest 29 steepest 29 steepest 29 30
DAFTAR LAMPIRAN 1 2
Sintaks dari setiap metode steepest descent Hasil pengujian dari setiap metode steepest descent
32 38
1 PENDAHULUAN Latar Belakang Dalam aktivitas sehari-hari sering dijumpai kegiatan yang menyangkut pengoptimuman. Kegiatan pengoptimuman ini bertujuan untuk memaksimumkan atau meminimumkan. Hal ini biasanya dijumpai dalam bidang industri, teknik, ekonomi, pertanian dan banyak sektor bidang lainnya. Pengoptimuman dapat didefinisikan sebagai proses untuk mendapatkan keputusan terbaik yang memberikan nilai maksimum atau minimum dari suatu fungsi dengan cara penentuan solusi yang tepat. Dari segi fungsinya pengoptimuman dapat dibedakan menjadi pengoptimuman linear dan pengoptimuman nonlinear. Sedangkan dari bentuknya pengoptimuman dikelompokkan menjadi pengoptimuman berkendala dan pengoptimuman nirkendala. Pengoptimuman berkendala adalah pengoptimuman suatu fungsi dengan syarat-syarat tertentu yang membatasinya. Sebaliknya pengoptimuman nirkendala adalah pengoptimuman tanpa adanya syarat-syarat tertentu yang membatasinya (Griva et al. 2009). Kegiatan Pengoptimuman selalu identik dengan nilai maksimum atau nilai minimum yang terbaik. Padahal, pengoptimuman yang baik seharusnya mempertimbangkan juga metode yang akan digunakan serta pemrograman yang tepat dalam aspek komputasi. Komputasi dapat diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritme dalam menyelesaikan suatu masalah. Dalam aspek komputasi hal yang diperhatikan adalah kompleksitas ruang dan kompleksitas waktu. Hal ini dapat dilihat dari tingkat kerumitan serta waktu yang dibutuhkan dari suatu algoritme dalam menyelesaikan suatu fungsi. Suatu algoritme dikatakan baik jika tingkat kerumitannya semakin kecil dan prosesnya membutuhkan waktu yang kecil. Namun pada kenyataannya banyak metode pengoptimuman yang bentuknya sederhana akan tetapi membutuhkan waktu yang lama dalam proses komputasinya. Oleh karenanya sangat diperlukan suatu perbaikan dari motode pengoptimuman baik dari segi kompleksitas ruang maupun dari segi kompleksitas waktunya. Metode pengoptimuman umumnya dapat dilakukan secara analitik maupun secara numerik. Namun untuk kasus pengoptimuman nirkendala dengan fungsi nonlinear multivariabel, terdapat persoalan yang tidak bisa diselesaikan dengan metode analitik. Sehingga diperlukan metode numerik untuk menyelesaikan permasalahan tersebut. Metode numerik yang digunakan dalam masalah pengoptimuman biasanya bersifat iteratif. Salah satu metode iteratif yang digunakan adalah metode line search steepest descent. Metode steepest descent (SD) merupakan prosedur paling mendasar untuk meminimumkan fungsi terdiferensialkan beberapa variabel yang diperkenalkan oleh Cauchy pada tahun 1847 (Bazaraa et al. 2006). Metode ini adalah metode ( ) (turunan parsial orde gradien sederhana yang menggunakan vektor gradien pertama dari fungsi f ) untuk menentukan arah pencarian disetiap iterasi dan dari arah tersebut akan ditentukan besar ukuran langkahnya ( ). Pada beberapa kasus, metode SD ini memeliki kekonvergenan yang lambat ketika menuju ke solusi optimum, hal ini terjadi karena langkahnya yang berbentuk zig-zag. Secara
2 intuitif arah yang digunakan dalam metode SD adalah arah dengan penurunan yang tercepat, akan tetapi secara umum tidak berarti menuju titik minimum lokal yang tercepat. Sehingga dalam beberapa tahun terakhir ini menjadi lebih jelas bahwa pimilihan ukuran langkah menjadi masalah penting dalam metode steepest descent. Penentuan ukuran langkah ini dapat mempengaruhi cepat atau lambatnya kekonvergenan ke solusi optimum. Sebuah hasil yang mengejutkan diberikan oleh Barzilai dan Borwein (1988) yang berusaha menyempurnakan metode ini dengan memodifikasi algoritme dan hasilnya berjalan cukup baik untuk masalah dengan dimensi yang besar. Metode ini kemudian dikenal dengan metode BarzilaiBorwein (BB) Hasil metode BB (1988) telah memicu banyak penelitian pada metode steepest descent. Penelitian-penelitian yang dilakukan untuk mendapatkan algoritme pencarian ukuran langkah yang memungkinkan konvergensi cepat dan monoton. Diantaranya penelitian yang dilakukan oleh Dai dan Yuan (2003) yang dinamakan Alternatif Minimisasi (AM) dengan ide penggabungan ukuran langkah yang bergantian antara meminimumkan nilai fungsi dan norm gradien disepanjang garis steepest descent. Penelitian lainnya dilakukan oleh Yuan (2006), dengan algoritme ukuran langkah baru pada iterasi genap dan exact line search pada iterasi ganjil. Metode Yuan ini sangat efisien untuk masalah dengan dimensi kecil. Berdasarkan penelitian-penelitian yang telah dilakukan, maka dalam penelitian ini akan dimodifikasi ukuran langkah pada metode SD dengan ukuran langkah baru untuk memperoleh kekonvergenan yang lebih cepat dari metodemetode yang telah dilakukan sebelumnya. Modifikasi ukuran langkah yang dilakukan diharapkan dapat memperkecil kompleksitas ruang maupun kompleksitas waktu yang dibutuhkan dari algoritme.
Tujuan Penelitian a. Merekonstruksi algoritme steepest descent, Barzilai-Borwein, Alternatif Minimisasi, dan metode Yuan. b. Memodifikasi algoritme steepest descent dengan ukuran langkah baru. c. Membandingkan secara eksperimental hasil output dari modifikasi algoritme dengan metode steepest descent, Barzilai-Borwein, Alternatif Minimisasi, dan metode Yuan untuk kasus fungsi kuadratik ditinjau dari proses iterasi dan running time.
3
2 TINJAUAN PUSTAKA Ruang Vektor Definisi 2.1 (Ruang Vektor) Misalkan V adalah himpunan dengan pendefinisian operasi penjumlahan dan operasi perkalian dengan skalar. Setiap pasangan elemen dan di dalam V terdapat suatu elemen yang tunggal juga berada di dalam V serta setiap elemen di dalam V dan setiap skalar terdapat yang tunggal juga berada di dalam V. Himpunan V dengan operasi penjumlahan dan operasi perkalian dengan skalar ini dinamakan ruang vektor jika memenuhi aksioma berikut. 1. . ) ( ) 2. ( . 3. sehingga . ( ) terdapat ( ) sehingga . 4. ) 5. ( dan skalar . ) 6. ( dengan skalar dan skalar . dengan skalar dan skalar . 7. ( ) 8. . Elemen dalam V adalah vektor sedangkan symbol 0 menyatakan vektor nol. (Leon 1998) Definisi 2.2 (Ruang Bagian) Jika S adalah himpunan bagian takkosong dari suatu ruang vektor V dan S memenuhi syarat-syarat berikut 1. jika untuk sembarang skalar 2. jika dan , maka S disebut ruang bagian dari V. (Leon 1998) Definisi 2.3 (Kombinasi Linear) Misalkan adalah vektor-vektor dalam suatu ruang vektor V. Jumlah vektor-vektor yang berbentuk dengan skalar-skalar disebut kombinasi linear dari . (Leon 1998) Definisi 2.4 (Merentang) Misalkan adalah vektor-vektor dalam suatu ruang vektor V. Himpunan vektor dikatakan merentang suatu vektor V jika setiap vektor pada V selalu dapat dinyatakan sebagai kombinasi linear dari vektor . (Leon 1998) Definisi 2.5 (Bebas Linear) Vektor-vektor dalam ruang vektor V disebut bebas linear jika mengakibatkan semua skalar-skalar harus sama dengan nol. (Leon 1998)
4 Definisi 2.6 (Bergantung Linear) Vektor-vektor linear jika terdapat skalar-skalar sehingga Definisi 2.7 (Basis) Vektor-vektor dan hanya jika
dalam ruang vektor V disebut bergantung yang tidak semuanya nol . (Leon 1998)
membentuk basis untuk ruang vektor V jika bebas linear dan merentang V . (Leon 1998)
Definisi 2.8 (Dimensi) Misalkan V adalah ruang vektor. Jika V memiliki basis yang terdiri atas n vektor, maka V dikatakan memiliki dimensi n . (Leon 1998)
Matriks Definisi 2.9 (Matriks Identitas) Matriks identitas adalah matriks
(
) yang berukuran
, dengan
{ (Leon 1998) Definisi 2.10 (Invers dari Suatu Matriks) Suatu matriks yang berukuran dikatakan taksingular jika terdapat matriks B sehingga . Matriks B dikatakan invers multiplikatif dari matriks . Invers multiplikatif dari matriks taksingular secara sederhana disebut . juga sebagai invers dari matriks dan dinotasikan dengan (Leon 1998) Definisi 2.11 (Traspose dari Suatu Matriks) Transpos dari suatu matriks adalah ( ) yang berukuran matriks yang didefinisikan oleh untuk ( ) yang berukuran setiap dan . Transpos dari dinotasikan oleh . (Leon 1998) Definisi 2.12 (Matriks Simetris) Suatu matriks berukuran disebut matriks simetris jika (Leon 1998) Definisi 2.13 (Matriks Diagonal) Matriks diagonal adalah matriks berukuran yang semua unsur selain diagonal utama ialah nol. Matriks diagonal berukuran dapat ditulis sebagai [
]
dengan disebut unsur diagonal utama. Matriks diagonal D memiliki invers yang dapat dinyatakan sebagai
5
D 1
1
d1 0
0
1
d2
0
0
0 0 1 d n
Dengan semua unsur diagonal utama adalah taknol sehingga . Matriks dapat dikatakan matriks simetris karena . (Anton & Rorres 2005)
Ortogonalitas Definisi 2.14 (Hasil Kali Skalar) Misalkan dengan , maka hasil kali skalar dari adalah
- dan
,
( ) (Leon 1998)
Definisi 2.15 (Norm) Suatu pemetaan ‖ ‖ disebut norm jika dan hanya jika memenuhi sifat berikut: ‖ ‖ (i) ‖ ‖ ‖ ‖ | |‖ ‖ (ii) ‖ ‖ ‖ ‖ ‖ (iii)‖ Untuk , maka dari didefinisikan sebagai: ⁄
‖ ‖
(∑| | )
Dalam prakteknya, hanya tiga
(
)
yang digunakan yaitu: ⁄
‖ ‖
∑| | ‖ ‖
(∑| | )
‖ ‖
| |
Norm vektor lainnya yang sering digunakan adalah norm ellipsoid yang didefinisikan sebagai ‖ ‖ ( ) ⁄ ( ) Misalkan adalah
,
dengan ‖ ‖
√
- , maka norm dari vektor √
di (
)
(Sun dan Yuan 2006) Definisi 2.16 (Ortogonal) Vektor – vektor dan
disebut ortogonal jika
. (Leon 1998)
6 Pengoptimuman Matematik Definisi 2.17 Pengoptimuman matematik adalah suatu proses formulasi masalah dan penentuan solusi dari suatu masalah pengoptimuman berkendala dengan bentuk umum: , ( ) (2.16) ( ) ( ) ( ) adalah fungsi dari x. dimana ( ) ( ) , - dinamakan variabel Komponen-komponen dari ( ) menyatakan fungsi kendala keputusan, ( ) adalah fungsi objektif, pertaksamaan, ( ) adalah fungsi-fungsi kendala persamaan. Vektor optimum yang menjadi solusi dari masalah dinyatakan dengan dan nilai optimumnya adalah ( ). Jika tidak ada kendala maka masalah dinamakan masalah pengoptimuman nirkendala. (Snyman 2005) dengan kendala
Turunan Parsial Definisi 2.18 Andaikan bahwa f adalah suatu fungsi dua variabel x dan y. Jika y di jaga agar tetap konstan, katakanlah , maka ( ) adalah fungsi satu variabel x. Turunannya di x = x0 disebut turunan parsial f terhadap x di ( ) dan dinyatakan oleh ( ). Jadi ( ) ( ) ( ) ( ) Dengan cara serupa, turunan parsial f terhadap y di ( ( ) dan diberikan oleh ( ) ( ( )
) dinyatakan oleh )
(
)
Misalkan f suatu fungsi tiga variabel x, y, dan z. Turunan parsial f terhadap x di (x,y,z) dinyatakan oleh ( ) dan didefenisikan oleh ( ) ( ) ( ) ( ) Turunan parsial terhadap y dan z didefenisikan secara serupa. (Varberg et al. 2007) Turunan Berarah Definisi 2.19 Untuk tiap vektor u, misalkan ( )
(
)
( )
jika limit ini ada, disebut turunan berarah f di p pada arah u
(
)
7 Untuk menghitung turunan berarah dari suatu fungsi, biasanya digunakan teorema berikut: Teorema 2.1 Misalkan f terdiferensialkan di p, maka f mempunyai turunan berarah di p dalam arah vektor satuan u = (a, b) dan ( )
( )
(
)
yaitu (
)
(
)
(
)
( ) (Varberg et al. 2007)
Vektor Gradien dan Matriks Hesse Definisi 2.20 (Vektor Gradien) Untuk fungsi ( ) yang terdapat di setiap titik yang merupakan vektor dari turunan parsial orde pertama disebut vektor gradien yaitu: ( ) ( )
( )
(
( )
( )
(
)
)
Definisi 2.21 (Matriks Hesse) Jika fungsi f terdiferensialkan secara kontinu dua kali maka di titik terdapat matriks turunan parsial kedua yang disebut matriks Hesse: ( )
,
( ) -
( )
( )
( )
( )
( )
( )
( ) (
( ) ( dimana
( ) adalah matriks simetrik
( )
)
( ) )
. (Snyman 2005)
8 Minimum Global dan Minimum Lokal Definisi 2.22 Titik adalah minimum global dari f pada D jika ( ) ( ) Titik adalah minimum lokal jika terdapat sehingga ( ) ( ) ‖ * |‖ + dengan ‖ ‖ menyatakan norm Euclid. Syarat perlu dan syarat cukup untuk minimum lokal teorema berikut:
dinyatakan dalam
Teorema 2.2 (Syarat perlu) Misalkan adalah fungsi yang mempunyai turunan parsial ( ) kedua di . Jika adalah minimum lokal, maka , (syarat orde pertama) dan matriks Hesse ( ) semidefinit positif (syarat orde kedua). ( ) Titik sehingga dinamakan titik kritis atau titik stasioner fungsi f. Teorema 2.3 (Syarat cukup) Misalkan adalah fungsi yang mempunyai turunan parsial ( ) kedua di . Jika dan matriks Hesse ( ) definit positif, maka adalah minimum lokal dari . (Snyman 2005)
Fungsi Kuadratik di Definisi 2.23 Suatu fungsi dinamakan fungsi kuadratik dalam n variabel jika dapat dituliskan sebagai ( )
(
)
Dengan Jika
, b vektor real berukuran n, dan A matriks real berukuran . maka ( ) (2.26) ( ) Sehingga matriks adalah matriks simetrik. (Snyman 2005)
Kedefinitan Matriks Teorema 2.4 Misalkan matriks berukuran dan misalkan adalah minor utama ke-k dari matriks untuk maka 1. definit positif jika dan hanya jika , untuk k = 1,2,…,n, 2. definit negatif jika dan hanya jika ( ) , untuk k = 1,2,…,n.
9 Teorema 2.5 Jika suatu matriks simetrik, maka matriks adalah 1. definit positif jika dan hanya jika semua nilai eigen dari adalah positif, 2. definit negatif jika dan hanya jika semua nilai eigen dari adalah negatif, 3. takdefinit jika dan hanya jika mempunyai paling sedikit satu nilai eigen positif dan paling sedikit satu nilai eigen negatif. (Peressini et al. 1988)
Kekonveksan Fungsi Definisi 2.24 (Ruas Garis) dan
Misalkan adalah
dan
dua titik di
* |
, maka ruas garis yang menghubungkan
(
)
+
(2.27)
Definisi 2.25 (Himpunan Konveks) Himpunan dikatakan himpunan konveks jika dan hanya jika untuk setiap dan di C, maka ruas garis yang menghubungkan dan juga terletak di C. Definisi 2.26 (Fungsi Konveks) Misalkan , 1. fungsi f dikatakan konveks pada himpunan konveks C jika ( ( ) ) ( ) ( ) ( ) ( ) untuk setiap , di C dan untuk setiap dengan 2. fungsi f dikatakan konveks sempurna pada himpunan konveks C jika ( ( ) ) ( ) ( ) ( ) ( ) untuk setiap , di C dengan dan untuk setiap dengan Misalkan ( ) mempunyai turunan parsial kedua yang kontinu pada suatu himpunan C di . Jika matriks Hesse ( ) dari f adalah definit positif pada C, maka ( ) adalah fungsi konveks sempurna pada C. (Snyman 2005)
Tingkat Konvergensi Defenisi 2.27 Misalkan diberikan barisan iterasi * + yang dihasilkan oleh suatu algoritme konvergen ke pada sejumlah norm yaitu, ‖ ‖ ( ) Jika terdapat bilangan real terhadap iterasi k, sehingga
dan ‖ ‖
bilangan konstan positif yang bebas ‖ ‖
(
)
10 maka dapat dikatakan * + memiliki -order tingkat konvergensi yang dapat dibagi menjadi tiga bagian: ( ) maka barisan * + konvergen Q-Linear 1. jika dan 2. jika dan atau, dan maka barisan * + konvergen Q-Superlinear 3. jika maka barisan * + konvergen Q-Kuadrat (Sun dan Yuan 2006)
Deret Taylor Definisi 2.28 Deret Taylor dari fungsi real ( ) yang terturunkan untuk semua tingkatan disekitar titik dapat ditulis sebagai berikut: ( )
( )
( ) (
dimana ( ) adalah gradien
) pada
( )(
)
(
)
(
)
dan
( ) adalah matriks Hessian. (Varberg et al. 2007)
Ketaksamaan Kantorovich Teorema 2.6 Diberikan matriks simetrik . Maka untuk setiap ( ) ((
))((
definit positif dengan nilai eigen berlaku Ketaksamaan: ))
(
)
(
)
(Sun dan Yuan 2006)
Iterasi dan Running Time Definisi 2.29 (Iterasi) Iterasi adalah sifat tertentu dari algoritme atau program komputer dimana suatu urutan atau lebih dari langkah algoritmik yang dilakukan pada loop program. Iterasi merupakan proses yang dilakukan secara berulang dalam menyelesaikan permasalahan matematik. (Chapman 2008) Definisi 2.30 (Running Time) Running time dari suatu algoritme didefenisikan sebagai ukuran operasi primitif atau tahapan proses yang dieksekusi. (Cormen et al. 2001)
3 METODE PENELITIAN Penelitian ini disusun melalui tiga tahap, pertama dilakukan telaah pustaka (buku dan jurnal terkait) mengenai metode steepest descent. Pada tahap pertama ini akan merekonstruksi empat metode gradien steepest descent yaitu metode steepest descent klasik, metode Barzilai-Borwein, metode Alternatif Minimisasi dan metode Yuan. Selanjutnya pada tahap kedua, memodifikasi ukuran langkah pada metode steepest descent dengan ukuran langkah yang baru. Kemudian pada tahap ketiga, mengimplementasikan metode kedalam bahasa pemrograman dengan menggunakan perangkat lunak. Setelah itu, dilakukan pengujian untuk kasus fungsi kuadratik yang dibangkitkan secara acak. Rata-rata dari hasil pengujian akan dibandingkan untuk melihat metode yang terbaik dalam menemukan solusi nilai minimum dengan iterasi dan running time yang terkecil.
4 HASIL DAN PEMBAHASAN Metode Steepest Descent Seperti yang telah dijelaskan dalam pendahuluan bahwa metode steepest descent adalah metode gradien sederhana untuk pengoptimuman nirkendala. Metode ini digunakan untuk meminimumkan fungsi terdiferensialkan beberapa ( ) (turunan parsial orde pertama variabel yang menggunakan vektor gradien dari fungsi f ) untuk menentukan arah pencarian disetiap iterasi. Metode ini diperkenalkan pertama kali oleh Cauchy pada tahun 1847 dengan bentuk permasalah pengoptimuman: ( ) ( ) dimana ( ) adalah fungsi terdiferensialkan secara kontinu di . Secara umum ( ) dapat berupa fungsi nonlinear. Metode steepest descent merupakan metode iteratif untuk memperoleh solusi pendekatan dari problem awal. Dalam pembahasan metode iteratif ini, vektor yang diperoleh pada iterasi ke-k dinyatakan dengan . Misalkan ( ). diberikan suatu titik awal kemudian akan dicari , sehingga ( ) Pergerakan pada setiap iterasi haruslah memenuhi ( ) ( ) (4.2) Misalkan f adalah fungsi yang terdefinisi di yang mempunyai turunan parsial pertama yang kontinu. Arah descent ditentukan dengan menggunakan turunan berarah di . Misalkan ( ) ( ) dan . Dengan menggunakan aturan rantai diperoleh ( )
(
)
(4.3)
sehingga ( )
(
)
(
)
(4.4)
12 menyatakan laju perubahan ( ) di pada arah , yang disebut juga dengan turunan berarah dari ( ) di pada arah (Gambar 1).
xk
dk
Gambar 1 Pencarian arah d gradien terhadap vektor gradien Perhatikan bahwa ( ) ‖ ( )‖‖ ‖ ‖ ( )‖ (4.5) ( ) dengan . Karena dimana adalah sudut antara maka ‖ ( )‖ ‖ ( )‖ ‖ ( )‖ (4.6) Di titik dicari vektor satuan sehingga turunan berarah mempunyai nilai terkecil relatif terhadap semua kemungkinan vektor satuan di . Nilai terkecil dari turunan berarah tersebut adalah ‖ ( )‖ pada saat , yaitu ( ) dengan pada saat sudut antara adalah , yang berarti sudut antara ( ) dengan adalah 0. Jadi vektor arah berimpit dengan vektor ( ). Ini berarti arah sehingga turunan berarah fungsi di sekecil mungkin ( ). adalah Secara umum metode steepest descent memiliki bentuk sebagai berikut: ( ) (4.7) atau
(4.8) ( ) adalah vektor gradien dari ( ) di dimana dan dan > 0 adalah ukuran langkah. Ukuran langkah dapat diperoleh dengan pencarian exact line search yaitu: * ( )+ (4.9) Jika ingin menemukan nilai minimum dari ( ) ( ) maka dapat dilakukan dengan mencari ( ) sehingga diperoleh ( ) ( ) ( ) (4.10) ini berarti gradien dari titik saat ini dan gradien dari titik selanjutnya saling tegak lurus (ortogonal). Untuk batas keturunan nilai fungsi untuk setiap iterasi dalam exact line search diberikan oleh, ( ) 〈 ( )〉 ( ) ‖ ‖‖ ( )‖ ( )〉 menunjukkan sudut antara ( ). Lebih dimana 〈 dan jelasnya teori kekonvergenan exact line search dijelaskan pada subbab selanjutnya.
13 Metode steepest descent selalu konvergen. Artinya, secara teori metode ini tidak akan berhenti atau akan terus melakukan iterasi sampai titik stasionernya ditemukan. Adapun algoritme stespest descent dituliskan dalam tahap-tahap sebagai berikut: Algoritme 4.1 Steepest Descent Step 0. Diberikan titik awal dan batas toleransi Tetapkan . Step 1. Tentukan . Jika ‖ ‖ , berhenti. Jika tidak tentukan . Step 2. Tentukan yang meminimumkan ( ) ( ) Step 3. Hitung Step 4. Beri nilai
.
, dan pergi ke Step 1.
Pada algoritme metode steepest descent ini memerlukan sembarang nilai awal atau titik awal . Pemberian nilai awal ini merupakan kriteria dari suatu metode iteratif. Selanjutntya dalam metode ini membutuhkan batas toleransi ( ) yang digunakan untuk pemberhentian dari proses iteratif. Batas toleransi ini digunakan untuk membatasi nilai ‖ ‖. Pembatasan ini dilakukan untuk menentukan tingkat ketelitian dari solusi. Semakin kecil batas toleransi yang diberikan maka solusi dari permasalahan akan semakin mendekati ke nilai yang sebenarnya. Pada dasarnya dalam metode steepest descent terdapat beberapa kriteria untuk pembatasan proses iterasi atau disebut uji konvergensi diantaranya yaitu norm dari selisih dua nilai terakhir yang disimbolkan dengan ‖ ‖. Selain itu dapat juga menggunakan selisih dari dua nilai fungsi terakhir yaitu | ( ) ( )|. Untuk kriteria pembatasan proses iterasi ini dapat digunakan secara bersamaan sehingga proses iterasi akan berhenti ketika salah satu kreteria terpenuhi. Selanjutnya langkah terpenting dalam metode steepest descent yaitu dan menentukan ukuran langkah . Vektor menentukan vektor gradien ( ) gradien digunakan untuk menentukan arah dimana suatu kurva pada titik mengalami penurunan yang tercuram sedangkan ukuran langkah digunakan untuk menentukan seberapa besar ukuran atau langkah pada arah penurunan tercuram tersebut. Sehingga akan didapatkan titik yang baru. Proses ini akan terus berlangsung sampai kriteria pemberhentian terpenuhi. d1 d3 d5
d2 d4
d6
Gambar 2 Ilustrasi steepest descent dalam plot kontur (Snyman 2005).
14 Meskipun titik optimum lokal ditemukan dengan arah yang tercuram metode steepest descent sering berkinerja buruk mengikuti jalan zig-zag. Hal ini menyebabkan konvergensi lambat dan menjadi ekstrim ketika masalah dengan skala yang besar yaitu ketika bentuk kontur yang sangat panjang. Kinerja yang buruk ini disebabkan oleh fakta bahwa metode steepest descent memberlakukan secara berturut arah pencarian yang ortogonal (4.10) seperti yang ditunjukkan pada Gambar 2. Meskipun dari sudut pandang teoritis metode ini dapat terbukti menjadi konvergen, tetapi dalam prakteknya metode ini tidak dapat secara efektif konvergen dalam jumlah langkah terbatas. Hal ini tergantung pada titik awal yang diberikan, bahkan konvergensi buruk ini juga terjadi ketika menerapkan metode steepest descent walaupun untuk fungsi kuadratik yang definit positif.
Exact Line Search Line search adalah pencarian satu dimensi yang mengacu pada prosedur pengoptimuman untuk fungsi dengan variabel tunggal. Line search ini merupakan dasar dari pengoptimuman multivariabel (4.8) untuk mencari Nilai dapat dicari dengan meminimumkan fungsi tujuan pada arah dan dapat dituliskan sebagai berikut: ( ) ( ) (4.12)
atau (
( )
)
Line search biasanya dinamakan exact line search karena berdasarkan (4.12) dapat ditemukan titik minimum yang tepat dan titik stasioner dari fungsi. Untuk lebih jelasnya akan dibuktikan kekonvergenan dari exact line search. Teorema 4.1 (Teori Kekonvergenan untuk Exact Line Search) Misal diberikan yang merupakan solusi dari (4.12). Dimisalkan pula ‖ ( ) ‖ , dimana M adalah bilangan positif, maka (
)
(
)
‖
(
)‖
〈
(
)〉
(
)
(
)
(
)
(
)
Bukti. Dari ekspansi deret Taylor diperoleh: (
)
dari asumsi ‖
(
(
) ) (
)
(
(
‖
( dimisalkan ̅ (
)
)
‖
‖
, sehingga (
)
)⁄( ‖
)
(
)
‖
‖
‖ ) sehingga dari (4.15) dan (4.11) diperoleh
(
)
(
̅
(
)
(
(
))
‖
‖
̅
)
̅
‖
‖
15 (
( ‖
(
‖
(
)‖
‖
‖ ‖
)‖
)) (
)‖
〈
(
)〉
Teorema 4.2 (Teori Kekonvergenan untuk Exact Line Search) Misalkan ( ) adalah fungsi kontinu terdiferensialkan pada himpunan ) ( ) terbuka , diasumsikan barisan dari (4.12) memenuhi ( dan ( ) . Misalkan ̅ merupakan titik akumulasi dari * + dan * | merupakan indeks dengan ̅+. Diasumsikan juga terdapat ̅ sehingga ‖ ‖ . Jika adalah titik akumulasi dari * + maka (4.16) ( ̅) ̅ Selanjutnya, jika ( ) terdiferensialkan dua kali pada maka ̅ ( ̅) ̅ (4.17) Bukti Misalkan merupakan indeks dengan ̅ . Jika ̅ maka (4.16) memiliki solusi trivial. Jika tidak maka dipertimbangkan dua kasus berikut. ̅ (i) Terdapat indeks sehingga . Karena ( ) merupakan ukuran langkah yang tepat, maka . Karena ‖ ‖ merupakan terbatas seragam dan , maka diambil hasil limit ( ̅) ̅ (ii) Untuk ̅ . Misalkan adalah indeks dari dengan ̅⁄ . Andaikan bahwa (4.16) tidak benar maka ( ̅) ̅ Jadi terdapat lingkungan ( ̅) dari ̅ dan indeks sehingga ( ̅) dan , ⁄ ( ) Misal ̂ adalah bilangan positif terkecil, sehingga untuk ̂ dan ( ̅). Pilih , ( ̅ ⁄ ̂), maka dari exact line search dan ekspansi Taylor diperoleh ( ̅)
(
)
∑, (
)
∑, (
)
∑, (
(
)-
(
)
)-
(
)-
16
∑
(
)
∑
( )
dimana . Kontradiksi di atas menunjukkan bahwa (4.16) juga berlaku untuk kasus (ii). Untuk pembuktian (4.17) sama halnya dengan pembuktian (4.16) yaitu secara kontradiksi hanya berbeda pada ekspansi deret Taylor orde kedua dan ⁄ memisalkan ̅ ( ̅) ̅ . ( ̅)
(
)
∑, (
)
∑, (
)
∑ *
(
(
)
∑
∑ [
(
) (
)(
)
)(
(
( )] (
)
(
)
+
)
)
Hal ini kontradiksi dengan (4.17). Dalam kasus pengoptimuman dengan fungsi kuadratik (2.25) pencarian dengan exact line search dapat diubah dalam bentuk sederhana. Misalnya secara ( ) dengan arah descent umum akan diminimumkan ( ) . Karena masalah pengoptimuman berbentuk fungsi kuadratik (2.25) sehingga fungsi ( ) menjadi ( )
(
)
(
)
(
)
(
)
Jika ( ) diminimumkan maka turunan (4.18) ke nol yaitu ( )
,
(4.19)
dari (4.19) diperoleh (
berdasarkan (2.26) dan gradien
)
(
)
maka didapatkan (
)
Jadi untuk proses pencarian ukuran langkah pada metode steepest descent untuk kasus fungsi kuadratik dapat digunakan rumus (4.20), dimana adalah matriks simetrik dan definit positif.
17 Kekonvergenan Metode Steepest Descent Teorema 4.3 (Konvergensi Global Metode Steepest Descent) Misalkan . Untuk setiap titik akumulasi dari barisan iterasi * + yang dihasilkan dari Algoritme 4.1 dengan exact line search adalah titik stasioner. Bukti Misalkan ̅ merupakan titik akumulasi dari * + dan adalah indeks terbatas sedemikian hingga ̅. Tetapkan ( ). Karena + terbatas seragam dan ‖ ‖ ‖ ( )‖. Karena maka barisan * | asumsi Teorema 4.2 terpenuhi, maka ‖ ( ̅)‖ ini berarti bahwa ( ̅) . Teorema 4.4 (Konvergensi Global Metode Steepest Descent) Misalkan ( ) terdiferensialkan dua kali pada dan ‖ ( )‖ untuk konstanta positif. Diberikan nilai awal dan . Maka untuk barisan yang dihasilkan dari Algoritme 4.1 terbatas dibanyak iterasi, atau ( ) atau ( ) Bukti Perhatikan kasus yang tak terbatas, dari Algoritme 4.1 dan Teorema 4.1 diperoleh )
(
)
(
)
∑, ( )
‖
(
)‖
sehingga ( Dengan
)
(
mengambil limit ‖ ( )‖ .
maka
(
)-
(
∑‖ (
dihasilkan
)‖ )
atau
Teorema 4.5 (Laju Konvergensi Dari Metode Steepest Descent Untuk Kasus Fungsi Kuadratik) Perhatikan masalah minimasi nirkendala berikut ( )
(
)
dimana adalah matriks simetris dan definit positif. Misalkan dan masing-masing adalah nilai eigen terbesar dan terkecil dari . Misalkan merupakan solusi dari masalah (4.21), maka barisan * + yang dihasilkan oleh metode steepest descent konvergen ke , dengan tingkat konvergen linear dan berlaku batas-batas berikut: (
) (
)
‖ ‖ ‖ ‖ dimana
⁄
.
( (
) )
( (
‖ ‖ ‖ ‖
) )
( ( (
√
) ) )
√
(
)
(
)
(
)
(
)
18 Bukti Diketahui bentuk metode steepest descent (4.7) yaitu Karena masalah pengoptimuman (4.21) berbentuk kuadratik maka dituliskan dalam bentuk
dengan
dapat
, sehingga
(
)
( ( )
(
)
)
(
)
(
( (
)
(
)
) )(
)
Dengan menggunakan ketaksamaan Kantorovich (2.33) maka diperoleh (
) (
)
[
[
(
)
(
)(
(
)
) ]
]
(
(
)
)
terbukti untuk (4.22). Selanjutnya akan dibuktikan untuk (4.23) dan (4.24). Misalkan . Perhatikan bahwa merupakan matriks simetrik dan definit positif, sehingga (4.26) jika maka ‖ ‖ ( ) (4.27) dari (4.26) diperoleh ‖ ‖ ‖ ‖ ( ) (4.28) sehingga dari (4.25), (4.27) dan (4.28) diperoleh ‖ ‖
‖ ‖
‖ ‖
‖ ‖
(
)
terbukti untuk (4.23) dan (4.24). Teorema diatas berlaku juga untuk fungsi kuadratik dengan bentuk ( ) dimana
adalah matriks simetris
( definit positif dan
.
)
19 Metode Barzilai dan Borwein Metode Barzilai dan Borwein atau disebut metode BB merupakan metode pengembangan dari metode steepest descent dengan mengganti ukuran langkah . Ide utama dari pendekatan metode BB adalah menggunakan informasi dalam iterasi sebelumnya untuk menentukan ukuran langkah dalam iterasi selanjutnya. Ukuran langkah metode BB diturunkan dari dua titik pendekatan ke garis potong persamaan yang didasari oleh metode Quasi-Newton. Adapun metode QuasiNewton yaitu sebagai berikut: (4.30) dimana dan adalah matriks identitas. Misalnya diberikan ekspansi deret Taylor (2.32) dari fungsi real ( ) untuk pendekatan kuadratik yang terturunkan untuk semua tingkatan di sekitar titik yaitu ( )
(
)
(
)
( ) dan dimana (4.31) diturunkan terhadap maka ( ) Kemudian dimisalkan sehingga diperoleh
( (
)
(
) (
). Misalnya
(
(
)
), jika
) dan (4.32)
atau (4.33) Pertama akan dibahas masalah (4.32). Jika masalah (4.32) diselesaikan dengan menggunakan least-squares (kuadrat terkecil) maka akan diperoleh: ‖ kemudian disederhanakan menjadi 〈
〉
‖ 〈
〉
〈
〉
Dari syarat perlu minimum lokal (Teorema 2.2) didapatkan 〈 〉 〈 〉 sehingga 〈 〉 〈 〉 Karena maka (
)
Jadi telah didapatkan ukuran langkah pertama (4.34) dari metode BB. Untuk masalah (4.33) akan dicari nilai ‖ ‖ dengan cara penyelesaian yang sama pada masalah (4.32) maka diperoleh ukuran langkah yang kedua (
)
20 Dari penyelesaian (4.32) dan (4.33) telah didapatkan dua ukuran langkah yang baru yaitu (4.34) dan (4.35). Kedua ukuran langkah ini merupakan ukuran langkah dari metode Barzilai dan Borwein yang memiliki langkah Q-super linear konvergensi pada tiga langkah berturut-turut (Dai 2003). Lebih jelasnya algoritme dari metode Barzilai dan Borwein dituliskan sebagai berikut: Algoritme 4.2 Barzilai dan Borwein (BB) Step 0. Diberikan titik awal dan batas toleransi . Tetapkan . Step 1. Tentukan . Jika ‖ ‖ , berhenti. Jika tidak tentukan . Step 2. Jika k = 0 maka tentukan dengan exact line search. Jika tidak dengan Tentukan
dimana
Step 3. Hitung Step 4. Beri nilai
dan , dan pergi ke Step 1.
Metode Alternatif Minimisasi Dalam beberapa pengertian, prinsipnya bahwa meminimumkan suatu fungsi ( ) yang kontinu dan terdiferensialkan dua kali (fungsi smooth) adalah setara dengan meminimumkan norm gradien ‖ ( )‖. Hal ini merupakan ide dasar dari metode gradien Alternatif Minimisasi (Dai dan Yuan 2003). Metode Alternatif Minimisasi (AM) adalah modifikasi metode steepest descent dengan ukuran langkah yang bergantian antara meminimumkan nilai fungsi dan norm gradien disepanjang garis steepest descent. Lebih tepatnya untuk dipilih ukuran langkah sehingga *‖ ( )‖+ ( ) dan * ( )+ ( ) Dapat dilihat bahwa gradien dari ‖ ( )‖ dan ( ) masing-masing adalah ( )⁄‖ ( )‖ dan ( ), sehingga dari (4.36) dan (4.37) diperoleh (4.38) dan (4.39) Dari hubungan di atas dapat simpulkan bahwa saling konjugat dengan , sedangkan dan saling ortogonal. Berdasarkan (4.7) dan didapatkan Kemudian dari (4.38) dan (4.39) diperoleh
21
(
)
{ Dari ketaksamaan Cauchy dan asumsi bahwa positif, diperoleh
matriks simetrik definit
* + Hal ini menunjukkan bahwa ukuran langkah metode AM pada setiap iterasi ganjil lebih kecil atau sama dengan ukuran langkah dari metode SD, yaitu (4.41) Untuk ukuran langkah pada iterasi genap jelas terlihat bahwa (4.42) Dari hubungan (4.41) dan (4.42) menunjukkan bahwa metode AM melakukan langkah SD penuh setelah langkah SD yang diperpendek. Sebagai contoh diilustrasikan dalam Gambar 3 dengan persamaan ( )
.
/
.
/
Dari Gambar 3 dapat dilihat dan merupakan iterasi yang dihasilkan oleh metode SD yang dimulai dari titik , sedangkan dan ) merupakan iterasi dari metode AM. Dapat dilihat bahwa ( ( ) ( ) yang berarti bahwa metode AM adalah monoton. Terlihat ) ( ) tetapi ( ) ( ). Meskipun dari Gambar 3 bahwa ( ( ) ( ) tidak selalu berlaku untuk kasus fungsi konveks kuadratik.
𝐱
𝑘
𝑺𝑫 𝐱𝟐𝒌 𝑨𝑴 𝐱𝟐𝒌
𝟏 𝑨𝑴 𝐱𝟐𝒌 𝟏
𝑺𝑫 𝐱𝟐𝒌
Gambar 3 Ilustrasi perbandingan metode Alternatif Minimisasi dan metode steepest descent
22 Algoritme 4.3 Alternatif Minimisasi (AM) Step 0. Diberikan titik awal Tetapkan . dan . Jika ‖ ‖ Step 1. Tentukan Step 2. Jika k ganjil maka tentukan
dan batas toleransi
.
, berhenti.
jika tidak tentukan
Step 3. Hitung Step 4. Beri nilai
, dan pergi ke Step 1.
Metode Yuan Metode Yuan (Yuan 2006) menggunakan ukuran langkah yang bergantian seperti yang dilakukan pada metode AM. Akan tetapi metode Yuan menggunakan ukuran langkah yang baru. Untuk analisis pada metode Yuan, diasumsikan bahwa fungsi objektif adalah sebagai berikut: ( )
dimana dan simetris dan definit positif. Metode baru yang digunakan akan memberikan nilai minimum dari ( ) dengan melakukan iterasi. Dapat dilihat bahwa pencarian exact line harus dilakukan pada iterasi terakhir sebelum algoritme berhasil menemukan solusinya. Diasumsikan bahwa digunakan pencarian exact line pada iterasi pertama untuk mendapatkan keberuntungan apabila ada kasus dimana algoritme dapat menemukan solusi pada iterasi pertama. Oleh karena itu, dibuatlah algoritme sebagai berikut:
dimana dan didapat dari pencarian exact line dan adalah solusi. Perlu dicari formula untuk sehingga akan menjadi nilai minimum dari fungsi objektif. Metode steepest descent adalah invarian dengan transformasi ortogonal. Untuk mempermudah analisis, dipelajari kasus dimana dan adalah dua buah sumbu. Sesuai dengan pencarian exact line pada iterasi pertama, gradien dan adalah ortogonal. Oleh karena itu untuk semua vektor dapat dituliskan sebagai kombinasi linear dari dan . Misalkan diberikan fungsi: (
‖
‖
‖
. / (
‖
)
(‖ ‖) . / ⁄‖ ‖ ⁄‖ ‖‖ ‖
⁄‖ ‖‖ ‖ ). / ⁄‖ ‖
23 Berdasarkan pencarian exact line (4.20) pada iterasi pertama dan kedua, diperoleh ‖ ‖ ‖ ‖ ‖ ‖ , dan sehingga (
‖
‖
‖ . / (
‖
(‖ ‖) . /
)
⁄ ‖⁄
‖
‖ ‖
‖⁄ ⁄
‖
‖
‖
). /
Dari persamaan di atas, dapat diketahui nilai minimum dari fungsi objektifnya dengan ⁄ dan ⁄ , sehingga diperoleh masing-masing: ‖
‖
‖
‖
(4.43)
dan ‖
‖
‖
‖
‖
‖‖
‖
(4.44)
Jika dilakukan eliminasi terhadap (4.43) dan (4.44) diperoleh ‖
‖ ‖ ‖ ‖ ‖ ⁄ ‖ ‖ ⁄
‖
‖ ‖‖ ‖ ‖ ⁄ ‖ ‖ ⁄
dan
Disederhanakan menjadi ‖
. /
‖
‖
Untuk mendapatkan gradien
‖‖
‖ ‖
‖
‖ ( ‖
‖
‖
‖
, perlu diketahui bahwa arah
‖
sejajar terhadap vektor residual . /
‖ ) ‖
. Untuk itu, diperlukan dua arah
(
‖
‖)
dan (‖
‖)
(
‖
⁄ ‖⁄
‖ ‖
‖⁄ ⁄
‖
‖
‖ )(
‖
‖)
yang merupakan dua arah yang sejajar. Dua arah tersebut masing-masing sejajar terhadap .
‖
‖ (
‖
‖ ‖ ‖ ‖
‖
‖
‖
‖
) ‖
‖
) ‖
/ ‖
dan (
‖
)
Diasumsikan bahwa . ‖
‖
‖ (
‖ ‖ ‖ ‖
‖
/
(
‖
‖
‖
‖
)
(
)
24 untuk ‖
‖
. Berdasarkan baris pertama persamaan (4.45) didapatkan . Kemudian nilai λ tersebut disubtitusikan ke baris kedua pada
persamaan (4.45) sehingga diperoleh ‖
(
‖ ) ‖ ‖
Persamaan ini ekuivalen dengan ‖
(
Karena
(
‖ )( ‖ ‖)
)
(
)
(
)
definit positif, diketahui bahwa ‖ (
‖ ‖ ‖)
Dari persamaan (4.46) diperoleh dua solusi positif untuk ( ⁄
⁄
)
√( ⁄
⁄
yaitu :
)
Dari dua solusi tersebut dipilih nilai yang lebih kecil dan dapat dituliskan sebagai berikut: √( ⁄
⁄
‖
)
‖ ⁄‖ ‖
⁄
(
⁄
)
inilah yang disebut ukuran langkah baru dan dengan . kemudian akan diaplikasikan ke dalam metode hasil modifikasi steepest descent. Untuk fungsi konveks kuadratik di n ( > 2) dimensi, berdasarkan (4.47) dapat dituliskan √( ⁄
⁄
Secara umum ukuran langkah
‖
)
‖ ⁄‖
‖
⁄
⁄
Algoritme 4.4 Yuan Step 0. Diberikan titik awal dan batas toleransi Step 1. Tentukan dan . Jika ‖ ‖ , berhenti. Tetapkan Step 2. Tentukan . Kemudian hitung , berhenti dan
√( ⁄
⁄
‖
(
)
. .
. Tentukan )
‖
‖ ⁄‖
Hitung Step 5. Jika ‖ Step 6. Beri nilai
)
dari metode Yuan adalah ,
Step 3. Jika ‖ ‖ Step 4. Tentukan
(
, berhenti , dan pergi ke Step 2.
‖
⁄
⁄
25 Modifikasi Metode Steepest Descent dengan Ukuran Langkah Baru Telah dibahas pada sub-bab sebelumnya bahwa metode gradien Yuan menggunakan ukuran langkah dengan exact line search pada iterasi ganjil dan kemudian menggunakan ukuran langkah (4.48) pada iterasi genap yang secara umum dituliskan seperti pada (4.49). Berdasarkan metode Yuan ini maka akan dilakukan modifikasi ukuran langkah dengan dua ukuran langkah yang baru. Untuk ukuran langkah yang pertama akan dibentuk suatu algoritme dengan ide langkah sebagai berikut:
(4.50) dimana dan merupakan ukuran langkah dengan proses pencarian menggunakan exact line search, sedangkan untuk dan menggunakan ukuran langkah Yuan (4.48). Algoritme (4.50) ini merupakan bentuk awal dari proses iterasi, sehingga untuk proses iterasi (4.50) selanjutnya akan terus berlanjut sampai solusi nilai ditemukan. Secara umum ukuran langkah dari bentuk (4.50) dapat dituliskan sebagai berikut: ( (
,
) )
(
Algoritme 4.5 Ukuran Langkah Baru (a) Step 0. Diberikan titik awal dan batas toleransi Tetapkan . dan . Jika ‖ ‖ , berhenti. Step 1. Tentukan Step 2. Jika mod(k,4) = 0 atau 1 maka tentukan
jika tidak tentukan √( ⁄
Step 3. Hitung Step 4. Beri nilai
)
.
dan ⁄
)
‖
‖ ⁄‖
‖
⁄
⁄
, dan pergi ke Step 1.
Untuk ukuran langkah baru yang kedua dapat dibuat algoritme dengan ide langkah sebagai berikut:
(4.52) dimana dan merupakan ukuran langkah dengan proses pencarian menggunakan exact line search, sedangkan untuk dan menggunakan ukuran langkah Yuan. Sama halnya proses iterasi pada (4.50) proses iterasi pada
26 (4.52) pula akan terus berlanjut sampai solusi nilai ditemukan. Secara umum ukuran langkah dari bentuk (4.52) dapat dituliskan sebagai berikut: ( (
,
) )
(
Algoritme 4.6 Ukuran Langkah Baru (b) Step 0. Diberikan titik awal dan batas toleransi Tetapkan . Step 1. Tentukan dan . Jika ‖ ‖ , berhenti. Step 2. Jika mod(k,4) = 1 atau 2 maka tentukan
)
.
dan
Jika tidak tentukan √( ⁄
⁄
Step 3. Hitung Step 4. Beri nilai
)
‖
‖ ⁄‖
‖
⁄
⁄
, dan pergi ke Step 1.
Hasil Numerik Pada sub-bab ini dilakukan perbandingan hasil numerik dari setiap metode gradien yang telah dijelaskan pada sub-bab sebelumnya, yaitu SD, BB, AM, Yuan, Algoritme 4.5 dan Algoritme 4.6. Sintaks dari setiap metode dapat dilihat pada Lampiran 1. Ukuran langkah untuk metode SD menggunakan (4.20) yang merupakan penyederhanaan dari exact line search. Untuk metode BB dibagi menjadi dua bagian, yaitu BB1 menggunakan ukuran langkah (4.34) dan BB2 menggunakan ukuran langkah (4.35). Perbandingan dilakukan untuk kasus fungsi nonlinear dengan bentuk kuadratik. Fungsi kuadratik yang digunakan dalam penelitian ini dibangkitkan secara acak dalam bentuk ( )
(
)
(
)(
)
menyatakan dimensi dari fungsi kuadratik dengan ) merupakaan bilangan acak integer pada . vektor ( -. Selanjutnya interval , dan merupakan kondisi dari matriks Hesse dari fungsi. Kemudian ( ) adalah bilangan acak -. Untuk semua dimensi dan integer pada interval , diberikan titik awal ) dan kriteria penghentian adalah ‖ ‖ vektor nol ( . Percobaan dilakukan sebanyak 5 kali untuk setiap dimensi dan setiap dari setiap metode. Sehingga percobaan yang dilakukan untuk satu dimensi sebanyak 105 kali dan total percobaan untuk semua dimensi sebanyak 1260 kali (Lampiran 2). Rata-rata jumlah iterasi dan running time dari percobaan disajikan pada tabel.
27 Tabel 1 Rata-rata jumlah iterasi dari metode steepest descent n
2
3
10
20
30
40
50
60
70
80
90
100
λn 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000
SD 15.8 17.6 18.0 58.0 446.0 ** 71.2 572.2 ** 69.8 611.8 ** 74.4 618.0 ** 71.0 619.8 ** 70.4 568.4 ** 73.0 541.8 ** 72.0 588.3 ** 73.4 597.8 ** 73.6 671.2 ** 73.2 566.6 **
** Lebih dari 2000 iterasi
BB1 9.4 10.2 9.6 16.0 19.4 25.2 28.8 73.4 84.4 28.8 66.2 129.0 29.2 81.8 161.2 31.4 85.8 158.8 30.4 83.0 169.6 32.0 83.6 153.0 30.0 98.2 174.8 32.6 86.0 151.6 32.2 94.4 160.0 32.6 85.2 170.6
Rata-rata jumlah iterasi BB2 AM Yuan 8.8 7.8 3.0 9.4 8.0 3.0 8.2 6.6 3.0 15.4 21.6 15.0 15.0 41.2 9.4 14.8 63.2 7.0 28.4 36.2 34.0 59.0 82.8 77.2 62.4 177.6 215.8 31.4 39.2 33.4 63.6 87.6 92.6 102.0 250.4 256.6 30.8 38.4 32.2 84.0 94.8 119.6 90.4 214.0 372.2 31.4 40.2 30.8 81.0 95.6 124.6 121.4 234.0 559.0 29.8 40.4 33.6 81.4 92.6 105.8 127.2 256.0 741.4 30.6 38.0 32.8 79.6 91.6 107.8 125.0 209.2 431.4 29.8 38.8 32.2 84.2 103.2 114.6 122.0 321.0 514.2 30.2 39.4 32.8 90.2 110.0 114.2 133.4 236.6 631.0 31.4 39.4 32.8 87.8 105.0 127.8 147.0 249.6 676.8 30.8 39.2 34.2 80.2 93.6 113.6 146.8 261.8 540.2
(4.5) 4.0 4.0 4.0 12.4 9.2 8.0 26.6 55.4 66.4 27.2 53.2 90.0 27.4 67.2 117.6 29.2 72.8 138.4 28.8 69.6 115.2 30.6 69.8 126.8 28.4 77.4 127.8 28.2 77.6 132.2 28.2 79.8 128.0 29.2 77.0 139.4
(4.6) 5.0 5.0 5.0 14.8 11.4 10.6 26.6 50.8 49.8 28.8 63.0 101.2 29.8 78.4 96.2 27.8 72.4 116.0 26.0 73.0 123.6 25.6 69.6 120.2 28.0 81.8 129.2 27.0 78.2 126.6 25.4 80.6 133.0 26.8 74.8 137.8
28 Tabel 2 Rata-rata running time dari metode steepest descent n
λn
10 2 100 1000 10 3 100 1000 10 10 100 1000 10 20 100 1000 10 30 100 1000 10 40 100 1000 10 50 100 1000 10 60 100 1000 10 70 100 1000 10 80 100 1000 10 90 100 1000 10 100 100 1000
SD 1.2158 1.3592 1.2957 4.1901 38.2374 ** 9.1579 178.4230 ** 13.9018 161.2717 ** 19.8876 257.1545 ** 24.1604 298.8377 ** 25.9427 306.8892 ** 36.3882 363.0106 ** 40.2148 499.9960 ** 45.6855 560.9794 ** 51.3049 686.0457 ** 55.3843 603.5062 **
** Lebih dari 1800 sekon
BB1 0.7921 0.8915 0.7972 1.5578 1.6251 2.3408 4.0018 9.9522 10.0730 5.9759 13.5476 27.3802 8.0823 23.5515 50.7939 11.1630 32.5804 63.8277 11.7516 34.1412 83.3517 16.5356 43.4831 85.6454 17.4249 58.9287 118.4859 21.2567 59.3693 113.1994 22.9283 73.2183 138.6705 25.3197 70.9071 160.4586
Rata-rata running time (s) BB2 AM Yuan (4.5) (4.6) 0.7430 0.6681 0.3445 0.4234 0.4813 0.7654 0.7447 0.3729 0.4249 0.5298 0.6808 0.5900 0.3510 0.4351 0.4789 1.2570 1.7168 1.2100 1.0527 1.1979 1.1804 3.0742 0.8563 0.8072 0.9336 1.2184 4.7670 0.6885 0.8337 0.9288 3.8183 4.6807 4.4170 3.5215 3.4583 8.0304 10.7603 9.9536 7.0518 6.6856 7.4047 20.6736 29.8327 7.4251 5.5743 6.5152 7.8569 6.7487 5.5918 5.7751 13.0366 17.3494 18.5229 10.4792 12.3972 20.9280 53.2933 61.3703 17.6327 20.4013 8.4538 10.5365 8.8325 7.4604 8.1181 24.0258 27.0576 34.6199 18.6904 21.7436 26.3331 64.7710 133.1709 33.0935 26.9119 11.0736 14.0317 10.7476 10.1022 9.8407 30.0823 32.6756 42.8027 30.0220 25.4911 46.8107 89.4547 282.7427 51.3329 41.6764 11.5382 15.2466 12.7024 11.0449 10.1426 33.8299 36.8299 42.0616 27.4626 28.6959 60.3106 121.2303 472.8374 49.5199 53.4718 15.6462 19.2288 16.4662 15.3770 12.7958 41.6120 46.6732 54.9497 34.7719 34.9854 67.6937 112.0454 271.2039 66.8134 60.9172 17.2778 21.9776 18.3037 16.1753 16.0799 50.5146 58.8435 65.3898 43.6303 46.0443 78.4548 140.2313 410.2627 75.4451 75.3167 19.5432 24.9432 20.5602 17.8875 17.1437 62.4149 72.1113 74.9126 49.6631 50.0332 96.2621 229.8008 517.2911 88.1097 84.3816 22.1720 28.2006 23.4393 20.4438 18.3391 67.1283 77.4596 95.3471 57.6106 58.3811 124.9331 206.0923 699.7920 98.0156 100.0168 24.0521 30.0698 25.9653 22.5381 20.8658 66.3028 74.8516 91.7633 61.3530 59.6863 133.0056 236.0443 603.7740 114.6884 116.0814
29
(a)
(b)
Gambar 4 Perbandingan rata-rata jumlah iterasi (a) dan running time (b) dari metode steepest descent untuk = 10
(a)
(b)
Gambar 5 Perbandingan rata-rata jumlah iterasi (a) dan running time (b) = 100 dari metode steepest descent untuk
(a)
(b)
Gambar 6 Perbandingan rata-rata jumlah iterasi (a) dan running time (b) dari metode steepest descent untuk = 1000
30
Gambar 7 Kekonvergenan dari metode steepest descent Berdasarkan hasil percobaan yang dilakukan secara umum dapat dilihat hubungan antara dimensi dan dengan iterasi dan running time. Untuk kasus dimensi kecil (n = 2 & 3) dapat dilihat bahwa besarnya tidak berpengaruh terhadap iterasi dan running time. Artinya semakin besar tidak menjamin bahwa iterasi dan running time akan semakin besar pula (Tabel 1 dan 2). Untuk kasus dimensi besar (n = 10, 20, 100) terlihat bahwa semakin besar maka semakin besar pula iterasi dan running timenya (Gambar 4 – 6). Selanjutnya dapat dilihat bahwa semakin besar dimensi tidak menyebabkan semakin besar iterasinya (Gambar 4a – 6a). Berbeda halnya dengan running time, semakin besar dimensi maka semakin besar pula running timenya (Gambar 4b – 6b). Pada masalah fungsi kuadratik dengan dimensi yang kecil untuk semua (10,100,1000), dapat dilihat bahwa metode Yuan mampu menemukan solusi nilai minimum dengan iterasi dan running time yang terkecil. Meskipun demikian bahwa Algoritme (4.5) dan (4.6) mampu menyeimbangi kecepatan metode Yuan untuk dimensi yang kecil. Untuk kasus dengan dimensi besar, metode Yuan memberikan hasil yang buruk khususnya pada dan . Berbeda dengan Algoritme (4.5) dan (4.6), untuk kasus dimensi besar dengan semua ukuran , Algoritme (4.5) dan (4.6) lebih dominan menemukan solusi nilai minimum fungsi dengan iterasi dan running time yang terkecil dibandingkan dari metode BB, AM, dan Yuan (Gambar 4 – 6). Hal ini terjadi karena Algoritme (4.5) dan (4.6) memiliki tingkat konvergensi yang lebih cepat dibandingkan dengan metode gradien lainnya, sebagai contoh ditunjukkan pada Gambar 7 dengan n = 100 dan = 100. Meskipun demikian pada dimensi dan tertentu metode BB dapat mengungguli Algoritme (4.5) dan (4.6).
5 SIMPULAN Metode Yuan merupakan metode gradien yang mampu memberikan iterasi dan running time yang kecil untuk kasus fungsi kuadratik dengan dimensi yang kecil. Akan tetapi metode Yuan memberikan kinerja yang buruk untuk kasus dengan dimensi dan yang lebih besar. Dalam penelitian ini dilakukan modifikasi ukuran langkah metode steepest descent dengan modifikasi ukuran langkah pada metode Yuan. Berbeda dengan metode Yuan, modifikasi ukuran langkah baru ini memberikan kinerja yang lebih baik untuk kasus fungsi kuadratik dengan dimensi dan yang besar. Bahkan modifikasi ukuran langkah baru ini lebih dominan mampu mengungguli kinerja dari metode Barzilai dan Borwein dan metode Alternatif Minimisasi. Hal ini terlihat dari rata-rata iterasi dan running time hasil percobaan yang dilakukan dengan fungsi kuadratik yang dibangkitkan secara acak. Modifikasi ukuran langkah baru ini mempunyai tingkat konvergensi yang cepat dibandingkan metode gradien yang lainnya.
DAFTAR PUSTAKA Anton H, Rorres C. 2005. Elementary Linear Algebra 9th ed. New Jersey (USA): John Wiley and Sons. Barzilai J, Borwein JM. 1988. Two point step size gradient methods. IMA Journal of Numerical Analysis, 8: 141-148. Bazara MS, Sherali HD, Shetty CM. 2006. Nonlinear Programming. Theory and Algorithms. New Jersey (USA): Wiley-Interescience. Cauchy A. 1847. General method for solving simultaneous equations Systems, Comp. Rend. Sci. Paris, 25: 46-89 Chapman SJ. 2008. Matlab Programming for Engineers. 4th ed. Ontario (CA): Thomson Learning. Cormen TH, Leiserson CE, Rivest RL, Stein C. 2001. Introduction to Algorithms 2th ed. Cambridge (USA): Massachusetts Institute of Technology Press. Dai YH. 2001. Alternate step gradient method. Academy of mathematics and Systems Sciences, Chinese Academy os sciences. Repor AMSS-2001-041. Dai YH, Yuan Y. 2003. Alternate minimization gradient method. IMA Journal of Numerical Analysis, 23: 377-393. Dai YH. 2013. A New Analysis on the Barzilai-Borwein Gradient Method. Operations Research Society of China, Periodicals Agency of Shanghai University and Spinger –Verlag Berlin Heidelberg. Griva I, Nash SG, Sofer A. 2009. Linear and Nonlinear Optimization. Philadelphia (USA): Society for Industrial and Applied Mathematics. Leon SJ. 1998. Linear Algebra with Applications. 5th ed. New Jersey (USA): Prentice Hall. Peressini AL, Sullivan FE, Uhl JJ Jr. 1988. The Mathematics of Nonlinear Programming. New York (USA): Springer-Verlag.
32 Snyman JA. 2005. Practical Mathematical Optimization. An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. New York (USA): Spinger. Sun Wenyu, Yuan Y. 2006. Optimization Theory and Methods. Nonlinear Programming. New York (USA): Spinger Science, Business Media. Verberg D, Purcell J.E, Rigdon S.E. 2007. Calculus Ninth Edition. New Jersey (USA): Prentice Hall, Inc. Yuan Y. 2006. A new stepsize for the steepest descent method. Journal of Computational Mathematics, 24: 149-156. Lampiran 1 Sintaks dari setiap metode steepest descent Sintaks untuk membangkitkan fungsi kuadratik clear; clc; n = 100;%dimensi(n=2,3,10,20,30,40,50,60,70,80,90,100) Lamda_n= 100; % Lamda_n = 10,100,1000 %Membangkitkan sebanyak n variabel X = sym('x',[n,1]) %Membangkitakan matriks diagonal if n==2 a = randi(Lamda_n,[1,n]); A = diag(a) else w = randi(Lamda_n,[1,n-2]); a = [1 w Lamda_n]; A = diag(a) end %membentuk Persamaan kuadratik m = randi([-5,5],[n,1]) f = expand(0.5*(X-m).'*A*(X-m))
Sintaks untuk metode steepest descent klasik clearvars -except A n X f m; clc; tic; y = zeros(1,n) tol = 10^(-8) gradien = jacobian(f,X) g = single(subs(gradien,X,y)) norm_g = [norm(g)] k=1 while norm(g)>tol L = g*g'/(g*A*g') y1 = single(y(end,:)-L*g) y = [y; y1] g = single(subs(gradien,X,y(end,:))) norm_g = [norm_g;norm(g)] k = k+1; end toc; F = single(subs(f,X,y(end,:))) iterasi=k-1 figure(1) semilogy(1:length(norm_g),norm_g(:,1),'b')
33 Sintaks untuk metode BB1 clearvars -except A n X f m; clc; tic; y = zeros(1,n) tol = 10^(-8) gradien = jacobian(f,X) g = single(subs(gradien,X,y)) set_g = [g] norm_g = [norm(g)] k=1 while norm(g)>tol if k==1 L = g*g'/(g*A*g') y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) set_g = [set_g;g] norm_g = [norm_g;norm(g)] else sk = y(end,:)-y(end-1,:) yk = set_g(end,:)-set_g(end-1,:) h = sk*yk' if h==0 break end L = sk*sk'/h y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) set_g = [set_g;g] norm_g = [norm_g;norm(g)] end k = k+1 end toc; F = single(subs(f,X,y(end,:))) iterasi=k figure(1) semilogy(1:length(norm_g),norm_g(:,1),'g')
Sintaks untuk metode BB2 clearvars clc; tic; y = tol = gradien = g = set_g = norm_g =
-except A n X f m; zeros(1,n) 10^(-8) jacobian(f,X) single(subs(gradien,X,y)) [g] [norm(g)]
34 k=1 while norm(g)>tol if k==1 L = g*g'/(g*A*g') y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) set_g = [set_g;g] norm_g = [norm_g;norm(g)] else sk = y(end,:)-y(end-1,:) yk = set_g(end,:)-set_g(end-1,:) h = sk*yk' if h==0 break end L = sk*sk'/h y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) set_g = [set_g;g] norm_g = [norm_g;norm(g)] end k = k+1 end toc; F = single(subs(f,X,y(end,:))) iterasi=k figure(1) semilogy(1:length(norm_g),norm_g(:,1),'g')
Sintaks untuk metode Alternatif Minimisasi (AM) clearvars -except A n X f m; clc; tic; y = zeros(1,n) tol = 10^(-8) gradien = jacobian(f,X) g = single(subs(gradien,X,y)) norm_g = [norm(g)] k=1 while norm(g)>tol if (mod(k,2)==1) L = g*A*g'/(g*A^2*g') y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) norm_g = [norm_g;norm(g)]
35 else L y1 y g norm_g end k=k+1
= = = = =
g*g'/(g*A*g') y(end,:)-L*g [y; y1] single(subs(gradien,X,y(end,:))) [norm_g;norm(g)]
end toc; F = single(subs(f,X,y(end,:))) iterasi=k-1 figure(1) semilogy(1:length(norm_g),norm_g(:,1),'k')
Sintaks untuk metode Yuan clearvars -except A n X f m; clc; tic; y = zeros(1,n) tol = 10^(-8) gradien = jacobian(f,X) g = single(subs(gradien,X,y)) norm_g = [norm(g)] Set_alpha =[]; k=1 while norm(g)>tol if mod(k,2)==1 L = (g*g')/(g*A*g') y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) Set_alpha= [Set_alpha ;single(L)] norm_g = [norm_g;norm(g)] else L = (g*g')/(g*A*g') Set_alpha= [Set_alpha ;single(L)] s = y(end,:)- y(end-1,:) if s==0 break end a1 = 1/Set_alpha(end-1) a2 = 1/Set_alpha(end) L1 = sqrt((a1-a2).^2+ 4*(g*g')/(s*s'))+a1+a2 LS = single(2/L1) y1 = y(end,:)-LS*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) norm_g = [norm_g;norm(g)] end k = k+1; end toc; F = single(subs(f,X,y(end,:))) iterasi=k-1 figure(1) semilogy(1:length(norm_g),norm_g(:,1),'m')
36 Sintaks untuk Algoritme (4.5) clearvars -except A n X f m; clc; tic; y = zeros(1,n) tol = 10^(-8) gradien = jacobian(f,X) g = single(subs(gradien,X,y)) norm_g = [norm(g)] Set_alpha =[]; k=1 while norm(g)>tol if mod(k,4)==0||mod(k,4)==1 L = (g*g')/(g*A*g') y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) Set_alpha= [Set_alpha ;single(L)] norm_g = [norm_g;norm(g)] else L = (g*g')/(g*A*g') Set_alpha= [Set_alpha ;single(L)] s = y(end,:)- y(end-1,:) if s==0 break end a1 = 1/Set_alpha(end-1) a2 = 1/Set_alpha(end) L1 = sqrt((a1-a2).^2+ 4*(g*g')/(s*s'))+a1+a2 LS = single(2/L1) y1 = y(end,:)-LS*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) norm_g = [norm_g;norm(g)] end k = k+1; end toc; F = single(subs(f,X,y(end,:))) iterasi=k-1 figure(1) semilogy(1:length(norm_g),norm_g(:,1),'r')
Sintaks untuk Algoritme (4.6) clearvars clc; tic; y = tol = gradien = g = norm_g = Set_alpha
-except A n X f m; zeros(1,n) 10^(-8) jacobian(f,X) single(subs(gradien,X,y)) [norm(g)] =[];
37 k=1 while norm(g)>tol if mod(k,4)==1||mod(k,4)==2 L = (g*g')/(g*A*g') y1 = y(end,:)-L*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) Set_alpha= [Set_alpha ;single(L)] norm_g = [norm_g;norm(g)] else L = (g*g')/(g*A*g') Set_alpha= [Set_alpha ;single(L)] s = y(end,:)- y(end-1,:) if s==0 break end a1 = 1/Set_alpha(end-1) a2 = 1/Set_alpha(end) L1 = sqrt((a1-a2).^2+ 4*(g*g')/(s*s'))+a1+a2 LS = single(2/L1) y1 = y(end,:)-LS*g y = [y; y1] g = single(subs(gradien,X,y(end,:))) norm_g = [norm_g;norm(g)] end k = k+1; end toc; F = single(subs(f,X,y(end,:))) iterasi=k-1 figure(1) semilogy(1:length(norm_g),norm_g(:,1),'y')
38 Lampiran 2 Hasil pengujian dari setiap metode steepest descent Hasil pengujian untuk jumlah iterasi n 2
λn 10 12 14 100 11 22 1000 12 30 3 10 65 69 100 337 358 1000 ** ** 10 10 73 71 100 617 647 1000 ** ** 20 10 69 75 100 518 622 1000 ** ** 30 10 76 79 100 566 644 1000 ** ** 40 10 72 71 100 645 342 1000 ** ** 50 10 70 71 100 638 335 1000 ** ** 60 10 72 74 100 582 232 1000 ** ** 70 10 72 70 100 433 683 1000 ** ** 80 10 75 71 100 547 590 1000 ** ** 90 10 74 72 100 598 663 1000 ** ** 100 10 71 76 100 318 638 1000 ** ** ** Lebih dari 2000 iterasi
SD 14 14 16 50 530 ** 70 505 ** 73 642 ** 73 642 ** 73 642 ** 69 619 ** 71 679 ** 71 596 ** 72 665 ** 75 783 ** 68 588 **
15 15 12 72 576 ** 73 628 ** 66 628 ** 75 622 ** 62 649 ** 66 616 ** 75 618 ** 72 601 ** 76 616 ** 75 650 ** 75 651 **
24 26 20 34 429 ** 69 464 ** 66 649 ** 69 616 ** 77 821 ** 76 634 ** 73 598 ** 75 628 ** 73 571 ** 72 662 ** 76 638 **
9 9 10 16 15 23 27 69 105 30 81 98 30 88 208 32 79 156 32 88 128 31 79 108 29 93 225 33 83 199 33 98 122 34 60 174
7 9 11 17 19 41 31 86 82 26 44 143 30 87 148 30 88 168 29 64 180 32 65 196 29 104 149 28 107 157 35 77 181 32 103 181
BB1 11 8 9 17 18 24 29 73 78 30 80 138 29 74 109 31 90 181 31 87 193 33 99 153 33 85 150 30 86 131 33 106 178 30 76 157
11 11 9 17 24 20 26 76 103 31 71 131 27 96 127 32 84 197 31 93 178 30 82 162 30 108 185 34 63 138 29 88 187 33 87 181
9 14 9 13 21 18 31 63 54 27 55 135 30 64 214 32 88 92 29 83 169 34 93 146 29 101 165 38 91 133 31 103 132 34 100 160
9 9 6 15 17 19 30 64 51 31 43 108 30 90 79 33 71 143 31 89 117 30 75 135 31 95 126 31 86 113 32 95 152 31 64 131
7 9 10 14 13 19 29 58 92 32 62 109 34 88 78 30 84 98 28 69 97 29 55 129 32 83 140 32 97 125 34 84 157 30 97 144
BB2 10 7 9 20 13 13 28 46 51 29 65 134 28 85 102 31 93 103 32 71 135 30 99 108 28 87 109 27 97 137 31 86 130 30 80 152
9 10 6 17 19 10 28 77 58 32 76 57 32 82 98 31 79 134 30 87 134 30 82 118 28 78 137 30 86 152 30 85 141 33 81 139
9 12 10 11 13 13 27 50 60 33 72 102 30 75 95 32 78 129 28 91 153 34 87 135 30 78 98 31 85 140 30 89 155 30 79 168
8 9 7 20 28 80 38 94 200 36 76 288 36 94 216 40 94 224 40 107 210 36 94 214 40 98 234 43 92 206 43 112 242 40 68 282
6 7 7 20 12 82 31 84 198 38 102 226 42 70 196 42 90 234 38 70 222 40 66 218 36 110 232 42 126 196 36 99 252 40 94 243
AM 9 7 7 26 54 16 38 76 248 40 78 204 36 102 200 37 96 240 40 88 314 40 96 138 42 108 206 36 106 284 38 108 248 40 94 316
8 8 6 22 86 96 32 86 166 36 94 286 40 112 216 42 96 282 40 98 190 40 116 218 36 100 230 36 112 253 40 116 210 36 110 296
8 9 6 20 26 42 42 74 76 46 88 248 38 96 242 40 102 190 44 100 344 34 86 258 40 100 703 40 114 244 40 90 296 40 102 172
39 Lanjutan n 2
3
10
20
30
40
50
60
70
80
90
100
λn 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000 10 100 1000
3 3 3 15 11 7 37 59 131 33 65 219 31 115 617 29 131 721 33 127 679 32 113 487 33 131 613 31 101 599 33 113 461 33 80 199
3 3 3 25 15 7 31 103 137 31 101 209 35 153 319 31 105 191 39 69 703 31 63 595 33 129 549 35 125 515 35 113 912 33 131 543
Yuan 3 3 3 9 7 7 43 65 613 33 131 163 35 115 167 31 117 581 31 111 667 35 109 539 31 121 131 29 109 665 31 157 747 35 99 611
3 3 3 15 7 7 28 82 141 37 107 161 31 114 147 29 133 525 34 115 827 33 119 323 33 105 575 32 117 677 32 139 599 37 131 615
3 3 3 11 7 7 31 77 57 33 59 531 29 101 611 34 137 777 31 107 831 33 135 213 31 87 703 37 119 699 33 117 665 33 127 733
4 4 4 12 8 8 24 64 72 28 28 96 30 60 124 32 72 140 29 72 112 28 64 102 28 88 104 28 68 104 25 80 128 28 53 148
Algoritme (4.5) 4 4 4 4 4 4 4 4 4 14 12 16 12 8 8 8 8 8 24 28 28 60 48 65 84 60 60 24 29 29 56 65 77 118 76 88 25 28 25 72 64 80 112 148 88 28 28 28 60 78 73 132 128 164 29 33 24 54 76 74 108 134 118 29 36 28 49 72 86 132 112 148 28 29 29 81 69 84 128 136 131 29 28 28 76 96 80 152 128 157 29 30 29 70 96 81 144 144 104 28 28 30 88 68 84 130 158 125
4 4 4 8 10 8 29 40 56 26 40 72 29 60 116 30 81 128 29 72 104 32 78 140 28 65 140 28 68 120 28 72 120 32 92 136
5 5 5 13 13 13 25 57 49 31 41 77 30 77 125 30 69 129 25 74 110 26 65 109 25 81 125 29 74 125 25 71 141 29 57 145
Algoritme (4.6) 5 5 5 5 5 5 5 5 5 13 17 18 9 9 13 11 9 9 26 27 29 57 41 62 41 53 53 30 25 33 57 87 69 109 89 69 29 29 32 69 79 93 65 97 101 29 25 26 69 69 77 109 137 92 26 29 25 61 73 78 137 129 133 26 25 26 53 77 79 129 105 125 27 33 26 89 83 81 157 119 147 26 29 25 82 77 73 129 113 169 25 27 25 85 74 87 149 129 125 25 26 29 93 73 78 133 113 141
5 5 5 13 13 11 26 37 53 25 61 162 29 74 93 29 78 113 25 79 109 25 74 133 29 75 98 26 85 97 25 86 121 25 73 157
40
Hasil pengujian untuk running time
n
λn
2
10
1.0166
0.9557
1.0193
1.3552
1.7324
0.7584
0.5982
0.9671
0.8600
0.7769
0.7302
0.6040
0.8012
0.7748
0.8047
0.6602
0.7020
0.7165
0.6215
0.6401
100
0.9255
1.7883
1.1718
1.1645
1.7460
1.0088
0.7149
0.6933
0.8580
1.1826
0.8208
0.7603
0.5778
0.8134
0.8547
0.7548
0.6881
0.6894
0.7930
0.7983
1000
0.9808
2.0206
1.1582
0.9588
1.3599
0.8533
0.9154
0.6961
0.7939
0.7274
0.5381
0.7640
0.7576
0.5454
0.7989
0.5674
0.6775
0.6451
0.5409
0.5193
10
4.6460
4.8915
3.5525
5.3289
2.5318
2.5700
1.2931
1.4581
1.3267
1.1409
1.2226
1.1666
1.6603
1.3337
0.9016
1.6262
1.5989
1.9550
1.7865
1.6176
100
26.3653
29.0768
45.2854
54.4283
36.0311
1.2355
1.5988
1.4089
1.9416
1.9408
1.3145
1.0113
1.1382
1.4690
0.9692
2.1226
0.9858
3.9466
6.5600
1.7558
1000
**
**
**
**
**
1.7818
2.8121
1.9333
1.5704
3.6063
1.6303
1.4274
1.0316
0.8590
1.1437
5.9586
6.2007
1.2329
7.0326
3.4104
10
9.3020
9.0300
9.1562
9.4942
8.8072
3.6399
4.3950
4.1783
3.7430
4.0529
4.2187
3.9398
3.7388
3.6243
3.5701
4.8678
4.0440
5.0701
3.9461
5.4758
100
104.9711
109.1245
505.0000
105.1285
67.8910
9.3907
11.6913
9.9719
10.4588
8.2482
8.6576
7.7925
6.2194
10.9643
6.5184
12.4329
10.8177
9.8291
11.5233
9.1984
1000
**
**
**
**
**
14.4541
8.6951
8.9926
11.0370
7.1864
6.5710
10.5268
5.6139
6.3274
7.9842
26.3027
21.0432
28.1778
18.0233
9.8211
10
14.9983
15.0082
14.0282
12.4485
13.0258
6.4697
5.4671
6.1228
6.0840
5.7360
6.6723
6.5849
6.2372
6.5147
6.5670
7.5638
7.4213
7.8934
7.2542
9.1516
100
130.8393
163.8114
169.1150
164.6901
177.9025
16.6760
9.5910
16.7671
14.1453
10.5585
8.8654
13.1314
13.4070
15.4976
14.2814
14.9279
21.4535
15.3260
18.1958
16.8439
3
10
20
30
40
50
60
70
80
90
100
SD
BB1
BB2
AM
1000
**
**
**
**
**
20.0261
32.4421
25.1100
29.0990
30.2237
22.5807
23.0847
25.5537
11.6025
21.8185
61.7235
48.8288
36.6316
62.7554
56.5274
10
19.9868
21.2838
19.8056
20.3536
18.0082
8.2178
8.2557
8.3382
7.5399
8.0601
8.1117
9.4877
7.9187
8.7388
8.0119
9.7020
11.7497
10.0623
10.9148
10.2539
100
226.3738
271.2644
272.9859
257.3105
257.8380
25.9488
24.9836
21.1440
27.3324
18.3488
25.6750
25.0692
24.2702
23.0972
22.0174
27.0463
19.4718
28.5372
31.8865
28.3462
1000
**
**
**
**
**
69.1510
45.8881
30.8589
37.8640
70.2076
22.8089
22.6836
29.6178
28.9992
27.5560
64.9122
60.2921
58.0164
67.4028
73.2313
10
24.4524
23.9175
26.0197
21.0397
25.3728
11.2364
10.7404
10.7847
11.9070
11.1466
11.4663
10.6816
10.7145
11.5610
10.9444
14.1103
14.9437
12.8915
14.8382
13.3747
100
305.5463
135.4500
300.8914
338.1937
414.1072
29.2218
32.3810
33.4480
34.9972
32.8540
26.2626
30.1886
34.6360
30.8698
28.4543
32.9280
31.6996
33.6248
36.6405
28.4854
1000
**
**
**
**
**
61.8863
65.4280
71.6272
84.9516
35.2453
55.4566
35.3448
38.0531
53.5253
51.6736
84.1760
87.7073
91.2005
112.0599
72.1298
10
25.3277
25.8956
25.1749
24.6160
28.6995
12.2269
11.5497
12.0197
11.8336
11.1283
11.7078
10.6848
12.5663
11.9244
10.8076
15.2747
14.5519
15.0169
15.0459
16.3435
100
347.7655
153.3712
328.0300
349.0194
356.2598
33.0197
25.7283
34.1898
41.4332
36.3350
35.6972
27.6657
27.8136
37.9629
40.0101
40.5440
26.8907
32.7191
41.8094
42.1861
1000
**
**
**
**
**
58.4089
89.9107
96.8450
88.7941
82.7998
53.6217
44.4415
67.0371
63.2329
73.2198
95.0613
100.7451
151.7772
86.8222
171.7458 17.4552
10
36.8573
36.1405
34.6853
37.3685
36.8892
15.7229
16.3549
16.9217
15.4572
18.2216
14.7272
14.8565
15.3680
15.2609
18.0183
18.9044
20.0015
19.6406
20.1421
100
382.8767
125.1753
481.7941
425.9131
399.2939
39.9885
33.4164
52.1047
42.7196
49.1861
38.2216
27.8877
52.4843
43.2996
46.1667
46.5593
33.3944
49.0173
61.1208
43.2742
1000
**
**
**
**
**
57.7030
112.9561
85.7352
91.1390
80.6939
73.2168
69.3170
56.4500
64.8583
74.6262
112.8671
117.1990
69.2345
117.0302
143.8963 22.5047
10
40.6625
39.3136
40.0021
40.4007
40.6951
17.2296
17.1182
18.8629
17.2522
16.6618
18.2491
18.6007
15.9562
16.2790
17.3043
22.8867
20.5853
23.5113
20.4002
100
433.2878
592.6118
454.5373
489.9995
529.5438
55.3958
63.9837
50.3719
65.1534
59.7384
56.8528
50.1263
52.5721
45.2953
47.7265
54.4079
63.4678
61.9622
56.0482
58.3312
1000
**
**
**
**
**
143.9118
100.3908
104.0924
130.1946
113.8402
70.9925
96.3183
70.6824
93.1411
61.1398
130.2491
151.3345
130.3440
149.1597
140.0692 25.4023
10
45.3454
44.5543
44.9364
47.6711
45.9203
20.8789
18.1232
19.4224
22.3209
25.5381
19.6540
20.5193
18.2967
19.0790
20.1672
26.6381
26.9898
22.9880
22.6980
100
460.8926
506.2006
622.7278
733.7763
481.2996
55.7116
74.6683
59.2212
42.4383
64.8071
58.9380
68.4459
67.9586
61.3907
55.3415
58.9939
82.1741
70.6293
74.1675
74.5917
1000
**
**
**
**
**
155.1314
117.7633
95.7214
101.0830
96.2979
81.2477
86.4152
99.3902
113.3531
100.9043
143.7946
434.5703
209.3964
185.6473
175.5954 29.4677
10
52.2490
49.2415
52.6288
50.9570
51.4486
24.2865
24.3399
22.4992
20.8044
22.7116
22.4441
23.5148
22.2041
20.9098
21.7871
30.7747
25.6149
26.8273
28.3186
100
592.0984
677.3882
795.4625
657.9431
707.3364
77.1263
57.2554
83.0487
68.5700
80.0914
72.7408
62.9595
64.2337
66.4871
69.2203
83.0255
71.1876
78.9047
87.9660
66.2142
1000
**
**
**
**
**
97.3980
163.4677
154.3824
169.8164
108.2883
125.3820
139.1657
113.5560
115.8458
130.7158
202.5465
203.7409
213.4551
164.2703
246.4487 30.3842
10
53.5535
61.4066
50.6193
55.2271
56.1150
26.9460
25.0321
23.4359
25.4217
25.7630
24.2141
23.7987
23.1318
24.9607
24.1552
31.0479
30.9082
31.0121
26.9967
100
281.0209
701.1226
624.6195
720.8160
689.9518
47.4109
87.4104
62.5671
72.1637
84.9833
51.2027
82.9385
66.4683
67.2658
63.6386
52.9807
75.7093
75.3106
89.1775
81.0798
1000
**
**
**
**
**
161.3058
171.2941
141.9661
166.5772
161.1500
115.7313
126.7120
135.1673
120.6856
166.7319
252.6555
212.4247
296.6748
267.8943
150.5721
** Lebih dari 1800 sekon
41 Lanjutan n
λn
2
10
0.4018
0.3128
0.3067
0.3058
0.3954
0.4994
0.4223
0.4133
0.3773
0.4046
0.4648
0.4393
0.5278
0.4781
0.4964
100
0.3401
0.3610
0.3716
0.3900
0.4017
0.4628
0.3803
0.3964
0.4979
0.3873
0.5217
0.5389
0.5839
0.5034
0.5009
1000
0.3473
0.3377
0.3445
0.4109
0.3144
0.4553
0.4505
0.4277
0.4388
0.4031
0.5279
0.4958
0.4535
0.4723
0.4448
10
1.2659
1.8955
0.7847
1.2207
0.8833
1.0516
1.1143
1.1315
1.2366
0.7292
1.1498
1.2096
1.3467
1.1837
1.0996
100
0.8893
1.2469
0.6508
0.7861
0.7084
0.7044
0.9451
0.7591
0.6787
0.9487
1.0532
0.7840
0.7575
1.0929
0.9804
1000
0.7731
0.6801
0.7027
0.6787
0.6079
0.8563
0.9466
0.7428
0.8071
0.8154
1.1759
0.9142
0.8196
0.7182
1.0162
10
4.7865
3.9569
5.5721
3.7210
4.0482
3.2005
3.2865
3.6758
3.6750
3.7698
3.3556
3.2811
3.6285
3.6022
3.4240
100
7.5673
13.4750
8.1456
10.8389
9.7411
8.2813
7.5503
6.0257
8.5083
4.8934
7.4841
7.3260
5.4536
8.2716
4.8927
1000
17.3743
14.6543
95.1599
14.9023
7.0729
9.2877
8.1346
6.4042
5.9005
7.3985
6.1556
4.0977
5.5578
5.3069
6.7537
10
6.8067
6.1971
6.7213
7.3007
6.7174
6.1004
5.1218
5.7037
5.7139
5.3190
6.5163
5.9513
4.9901
6.2975
5.1202
100
12.9021
20.2482
26.2742
21.7442
11.4460
5.6184
11.3835
12.5163
14.9756
7.9023
8.3390
11.1633
16.9864
13.6159
11.8815
1000
46.9814
44.6851
29.5825
34.1651
151.4372
19.3293
23.3807
13.0794
17.8568
14.5173
14.9347
21.9970
15.5876
14.5115
34.9759
10
8.5591
9.3534
9.7800
8.6733
7.7967
7.9691
6.7075
8.0687
6.9620
7.5946
7.9282
7.8898
8.3176
8.8081
7.6469
100
33.1662
44.6359
33.6729
31.6134
30.0109
16.9428
19.9391
17.7529
22.3121
16.5051
21.8784
19.2972
21.9480
25.1347
20.4597
1000
237.1319
101.4407
47.9555
42.9321
236.3944
35.6161
31.3192
41.4394
25.1391
31.9539
35.1095
17.5368
26.6586
29.1845
26.0702
10
9.8331
10.5118
11.0456
10.6261
11.7214
11.0710
9.6092
10.0348
9.7582
10.0378
10.7586
10.3615
8.9272
9.1091
10.0469
100
47.6031
36.6535
41.4094
50.9848
37.3629
26.5554
21.0458
26.6054
27.0956
48.8079
23.4848
24.2037
23.5921
28.0588
28.1162
1000
368.0806
69.9544
278.2801
269.5580
427.8407
49.6034
47.5930
45.1283
67.9491
46.3904
46.2193
37.7431
49.1067
33.3619
41.9511
10
12.2130
14.7438
12.1165
13.1085
11.3304
11.0995
10.8584
12.7140
9.5313
11.0214
9.7449
10.0525
11.1905
9.9785
9.7468
100
48.8935
25.9737
41.5861
48.6415
45.2134
26.9816
20.6435
27.6607
31.1866
30.8408
27.7217
23.2740
26.1694
33.2471
33.0671
1000
413.3548
440.5416
413.3255
549.1006
547.8647
47.0932
45.7412
58.8840
51.6344
44.2467
46.0388
60.0506
56.4719
58.3286
46.4691
10
16.1836
14.8918
17.4908
16.1060
17.6589
14.1926
14.5200
18.2073
13.8566
16.1084
12.7381
12.7593
12.6750
12.9024
12.9043
100
55.5707
31.2625
55.5269
62.1122
70.2763
31.2923
24.4142
35.8622
43.9988
38.2918
31.9801
26.5149
38.8184
40.4117
37.2019
1000
308.5391
400.5936
346.7743
184.9845
115.1278
62.4560
67.0096
54.9024
76.7273
72.9718
55.3120
65.2413
52.0200
63.9200
68.0927
10
18.6996
19.2952
17.6505
18.3789
17.4944
16.0423
16.1100
16.7672
16.2186
15.7382
14.7886
15.7473
18.3746
15.0596
16.4295
100
74.0615
75.2897
69.9027
58.2883
49.4069
48.9456
45.6963
39.1985
47.4743
36.8368
44.8651
50.8941
47.2014
44.6392
42.6220
1000
450.3409
435.0219
79.8840
472.6357
613.4309
53.6434
76.9640
82.1801
79.5177
84.9205
64.2422
96.1737
70.3688
89.3930
56.4058
10
19.4580
21.8556
18.5010
19.7456
23.2405
17.2467
18.6879
17.9802
17.9236
17.5992
18.0504
16.7173
18.2578
16.0100
16.6831
100
64.2451
81.6518
71.9688
77.1872
79.5101
42.9539
46.3886
63.2271
52.5417
43.2040
47.0091
52.4540
49.2677
46.2371
55.1981
1000
534.7503
133.5704
616.1952
642.0326
659.9069
67.2657
99.7763
87.2644
107.1419
79.1002
82.1605
84.8441
74.5300
116.9902
63.3832
10
23.5579
24.9138
22.2361
22.0468
24.4420
18.3590
20.6667
21.6576
20.4688
21.0672
18.3887
17.4250
19.8520
17.8210
18.2089
100
82.8576
81.0235
118.4480
107.4171
86.9895
57.9235
50.2417
68.6724
59.0479
52.1677
51.7716
60.9833
52.6342
64.0054
62.5111
1000
439.6127
912.4624
841.6269
604.9776
700.2805
96.3971
109.8936
116.7914
77.3546
89.6413
105.6796
112.4298
97.1076
94.9440
89.9232
10
25.7746
25.4105
26.2920
27.7288
24.6207
21.9542
21.9820
21.6991
22.8131
24.2422
22.4762
19.7608
20.7104
22.1190
19.2626
100
63.0025
106.6636
80.2509
106.4492
102.4502
41.7834
70.1901
54.3361
67.1600
73.2953
44.9121
74.4301
58.1660
62.9414
57.9818
1000
169.7577
576.0615
666.4231
670.3187
936.3088
122.9867
104.7736
131.4067
100.1438
114.1312
118.8578
126.1176
91.3768
114.8316
129.2232
3
10
20
30
40
50
60
70
80
90
100
Yuan
Algoritme (4.5)
Algoritme (4.6)
42
RIWAYAT HIDUP Penulis dilahirkan di Kecamatan Telaga Kabupaten Gorontalo pada tanggal 12 Juni 1989, sebagai anak pertama dari 2 bersaudara, dari pasangan Usman Wungguli dan Hadidjah Luther. Pendidikan sarjana ditempuh di Program Studi Pendidikan Matematika, Fakultas MIPA Universitas Negeri Gorontalo, lulus pada tahun 2011. Kesempatan untuk melanjutkan ke program magister pada Program Studi Matematika Terapan IPB diperoleh pada tahun 2012 dengan sponsor beasiswa pascasarjana dari Direktorat Jenderal Pendidikan Tinggi (DIKTI) melalui program Beasiswa Unggulan. Selama mengikuti perkuliahan, penulis juga aktif dalam berbagai kegiatan akademik maupun nonakademik, diantaranya: peserta Seminar Nasional Sains V dengan tema “Sains sebagai Landasan Inovasi dalam Bidang Energi, Lingkungan dan Pertanian Berkelanjutan” yang diselenggarakan oleh Fakultas MIPA Institut Pertanian Bogor pada tanggal 10 November 2012; peserta Seminar Nasional Matematika IPB Mathematics Challenge 2013 “Life is Meaningless without Mathematics” yang diselenggarakan oleh Gumatika FMIPA IPB pada tanggal 5-6 Oktober 2013; peserta International Seminar on Sciences 2013 (ISS 2013) dengan tema “Perspectives on Innovative Sciences” yang diselenggarakan oleh Fakultas MIPA Institut Pertanian Bogor pada tanggal 15-17 November 2013. Sebuah artikel akan diterbitkan pada bulan Juli 2015 dengann judul Metode Steepest Descent dengan Ukuran Langkah Baru utuk Pengoptimuman Nirkendala pada Journal of Mathematical Application (JMA). Artikel tersebut merupakan bagian dari tesis penulis.
