METODE STEEPEST DESCENT DALAM PENGOPTIMUMAN FUNGSI DAN PENERAPANNYA MENGGUNAKAN APLIKASI ANDROID
ALFI AINI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2016
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Metode Steepest Descent dalam Pengoptimuman Fungsi dan Penerapannya Menggunakan Aplikasi Android 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 2016 Alfi Aini NIM G54110067
ABSTRAK ALFI AINI. Metode Steepest Descent dalam Pengoptimuman Fungsi dan Penerapannya Menggunakan Aplikasi Android. Dibimbing oleh BIB PARUHUM SILALAHI dan SISWANDI. Pengoptimuman bertujuan mencari nilai minimum atau maksimum dari suatu fungsi bernilai real. Dari segi fungsinya, pengoptimuman dapat dibedakan menjadi pengoptimuman linear dan pengoptimuman nonlinear. Sedangkan dari segi bentuknya, pengoptimuman dikelompokkan menjadi pengoptimuman berkendala dan pengoptimuman tak berkendala. Untuk menyelesaikan permasalahan pengoptimuman tak berkendala, khususnya untuk fungsi nonlinear, dapat digunakan metode steepest descent. Metode ini adalah metode iteratif untuk memperoleh solusi pendekatan dari masalah awal. Karya ilmiah ini mengkaji metode steepest descent dan kemudian menerapkannya dalam aplikasi Android Studio 1.0.1 dengan mencari titik minimum dari fungsi kuadratik dengan konstanta tertentu. Dalam karya ilmiah ini diperoleh kesimpulan bahwa hasil iterasi tidak hanya dipengaruhi oleh banyaknya variabel yang digunakan dan besarnya toleransi, namun juga dipengaruhi oleh nilai fungsi. Kata kunci: Android studio, Metode steepest descent, Pengoptimuman
ABSTRACT ALFI AINI. Steepest Descent Method in Function Optimization and Its Implementation Using Android. Supervised by BIB PARUHUM SILALAHI and SISWANDI . Optimization is performed for searching the minimum or maximum value of a real function. Based on its function type, optimization can be distinguished into linear and nonlinear optimizations. While based on its formulation, it can be classified as constrained and unconstrained optimizations. To solve unconstrained optimization problem, especially for nonlinear function, steepest descent method can be used. This method is an iterative method which determines the approximate solution from the initial problem. On this work, steepest descent method is studied and implemented on Android Studio 1.0.1 by determining the minimum point of a quadratic function with particular constant. It is concluded that the iteration result does not only depend on the amount of variables and the range of tolerable error used, but also the value of the function. Keywords: Android studio, Optimization, Steepest descent method
METODE STEEPEST DESCENT DALAM PENGOPTIMUMAN FUNGSI DAN PENERAPANNYA MENGGUNAKAN APLIKASI ANDROID
ALFI AINI
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 2016
Judul Skripsi : Metode Steepest Descent dalam Pengoptimuman Fungsi dan Penerapannya Menggunakan Aplikasi Android Nama : Alfi Aini NIM : G54110067
Disetujui oleh
Dr Ir Bib Paruhum Silalahi, MKom Pembimbing I
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
Drs Siswandi, MSi Pembimbing II
PRAKATA Puji dan syukur saya panjatkan kepada Allah subhanahu wa ta’ala atas segala nikmat, rahmat, karunia, dan pertolongan-Nya sehingga karya ilmiah ini berhasil diselesaikan. Judul karya ilmiah ini adalah Metode Steepest Descent dalam Pengoptimuman Fungsi dan Penerapannya Menggunakan Aplikasi Android. Terima kasih saya ucapkan kepada keluarga tercinta Ibunda Masruroh dan Ayah Maroni, serta kakak saya Nadia Nur Rahmah atas segala doa, dukungan, dan kasih sayangnya selama menulis karya ilmiah ini. Ungkapan terima kasih juga saya ucapkan kepada Bapak Dr Ir Bib Paruhum Silalahi, MKom dan Bapak Drs Siswandi, MSi selaku dosen pembimbing yang telah banyak memberi saran, kesabaran, dan ilmu, serta Bapak Drs Prapto Tri Supriyo, MKom selaku dosen penguji yang telah banyak memberi saran, serta kepada seluruh staf Departemen Matematika. Tidak lupa saya mengucapkan terima kasih untuk para sahabat Intan Fitria Sari, Riefdah Imro’atul Azizah, Imam Shalahuddin, Hasannudin, Resty Bangun Pratiwi, Sifa Lusiana, Andini Qashrina Darmanagari, Riski Okfiana, Hanna Rifatika, Lidya Yolanda, Atikah Nurbaiti, teman-teman seperjuangan Matematika 48, kakak-kakak Matematika 47, adik-adik Matematika 49, serta teman-teman sekalian di luar Departemen Matematika baik di dalam maupun di luar IPB atas kritik, saran, dan doanya selama pembuatan karya ilmiah ini. Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya Matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.
Bogor, Januari 2016 Alfi Aini
DAFTAR ISI DAFTAR TABEL
viii
DAFTAR GAMBAR
viii
DAFTAR LAMPIRAN
viii
PENDAHULUAN
1
Latar Belakang
1
Tujuan Penelitian
1
LANDASAN TEORI
2
Fungsi
2
Pengoptimuman
2
Android Studio
2
HASIL DAN PEMBAHASAN
3
Hasil Numerik
6
Contoh Penghitungan Metode Steepest Descent
8
SIMPULAN
12
DAFTAR PUSTAKA
12
LAMPIRAN
13
RIWAYAT HIDUP
15
DAFTAR TABEL 1 Analisis perbedaan banyak iterasi dan besar toleransi metode steepest descent untuk fungsi variabel
8
DAFTAR GAMBAR 1 2 3 4 5
Grafik hasil untuk fungsi dua variabel Grafik hasil untuk fungsi tiga variabel Grafik hasil untuk fungsi empat variabel Grafik hasil untuk fungsi lima variabel Hasil metode steepest descent
6 7 7 7 11
DAFTAR LAMPIRAN 1 Sintaks metode steepest descent untuk fungsi dua variabel 2 Tampilan Android hasil untuk fungsi dua variabel metode steepest descent dengan toleransi 0.1
13 14
PENDAHULUAN Latar Belakang Teknologi merupakan salah satu hal yang tidak mudah dilepaskan dari kehidupan manusia. Tanpa adanya teknologi, manusia tentunya akan sulit untuk melakukan komunikasi dan menyampaikan informasi. Salah satu teknologi yang saat ini sedang berkembang pesat di dunia adalah Android. Android merupakan suatu sistem operasi yang berbasis mobile untuk telepon seluler (handphone). Permasalahan mengenai pengoptimuman adalah mencari penyelesaian terbaik dari suatu masalah. Dari segi fungsinya, pengoptimuman dapat dibedakan menjadi pengoptimuman linear dan pengoptimuman nonlinear. Sedangkan dari segi bentuknya, pengoptimuman dikelompokkan menjadi pengoptimuman berkendala dan pengoptimuman tak berkendala. Pengoptimuman berkendala adalah pengoptimuman suatu fungsi dengan syarat-syarat tertentu yang membatasinya. Sebaliknya, pengoptimuman tak berkendala adalah pengoptimuman tanpa adanya syarat-syarat tertentu yang membatasinya (Griva et al. 2009). Pada umumnya, metode pengoptimuman dapat dilakukan secara analitik maupun secara numerik. Namun, untuk kasus pengoptimuman tak berkendala dengan fungsi nonlinear multivariabel terdapat persoalan yang sulit diselesaikan dengan metode analitik, sehingga diperlukan metode numerik untuk mempermudah menyelesaikan permasalahan tersebut. Metode pengoptimuman secara numerik umumnya bersifat iteratif, yaitu dimulai dari titik awal yang sudah ditentukan kemudian bergerak ke titik hingga titik , yaitu titik yang mendekati nilai optimal. Salah satu klasifikasi metode numerik adalah metode dengan menggunakan gradien. Untuk metode dengan menggunakan gradien ini diperlukan syarat fungsi terturunkan. Contoh metode dengan menggunakan gradien, yaitu metode steepest descent, metode conjugate gradien, dan metode Newton (Klerk et al. 2005). 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. Metode ini merupakan prosedur paling mendasar untuk meminimumkan fungsi terdiferensialkan beberapa variabel (Sun dan Yuan 2006). Pembahasan karya ilmiah ini difokuskan pada salah satu bentuk persamaan nonlinear tak berkendala khususnya untuk menyelesaikan fungsi kuadratik dengan metode steepest descent dan penerapannya menggunakan aplikasi android.
Tujuan Penelitian Tujuan dari karya ilmiah ini adalah mengkaji metode steepest descent yang akan diterapkan dalam aplikasi Android Studio 1.0.1 dengan mencari titik minimum dari persamaan kuadratik dengan konstanta tertentu. Selanjutnya model diimplementasikan dengan menggunakan smartphone.
2
LANDASAN TEORI Fungsi Definisi 1 (Fungsi) Fungsi adalah aturan yang memadankan setiap secara tepat satu elemen yang disebut , di mana dan adalah himpunan bilangan real (Bartle dan Sherbert 1982). Definisi 2 (Fungsi Kuadratik) Suatu fungsi dikatakan fungsi kuadratik dalam dituliskan sebagai
dengan , vektor real berukuran , dengan elemen matriks berukuran Yinyu 2008).
variabel jika dapat
matriks real berukuran , dan . (Luenberger dan Ye
Definisi 3 (Fungsi Linear) Suatu fungsi dengan variabel adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan konstanta , dapat ditulis sebagai ( ) (Winston 2004). Sebagai contoh, ( ) merupakan fungsi linear, sementara ( ) bukan fungsi linear. Pengoptimuman Pengoptimuman adalah proses untuk mendapatkan keputusan terbaik yang memberikan nilai maksimum atau minimum dari suatu fungsi dengan cara penentuan solusi yang tepat. Secara umum, ada dua jenis pengoptimuman yang sering dihadapi, yaitu pengoptimuman linear dan pengoptimuman nonlinear. Kegiatan pengoptimuman selalu identik dengan nilai maksimum atau minimum yang terbaik. Pengoptimuman yang baik seharusnya mempertimbangkan juga metode yang akan digunakan serta pemrograman yang tepat dalam aspek komputasi (Wungguli 2015). Android Studio Android Studio adalah suatu sistem dari pengembangan aplikasi di Android. Ini tersedia untuk didownload pada Windows, Mac OS X, dan Linux. Android Studio saat ini masih dalam tahap awal pengembangan. Beberapa fitur belum lengkap atau belum dibuat. Namun, dalam keadaan ini sudah mampu untuk membuat sebuah aplikasi berbasis Android yang berjalan dengan sempurna pada perangkat Android.
3
HASIL DAN PEMBAHASAN Metode line search descent (metode iteratif) yang menggunakan vektor gradien (turunan parsial orde pertama dari fungsi ) untuk menentukan arah pencarian di setiap iterasi, dinamakan metode line search descent orde pertama. Salah satu contoh metode ini adalah metode steepest descent. Metode steepest descent merupakan salah satu dari yang paling sederhana dan metode peminimuman yang paling mendasar untuk pengoptimuman tak berkendala (sering disebut sebagai metode gradien). Metode ini bergerak dengan langkah-langkah yang saling tegak lurus. Tepatnya, jika adalah barisan steepest descent untuk fungsi , maka untuk setiap bilangan asli , vektor dengan adalah tegak lurus dengan vektor yang yang menghubungkan menghubungkan dengan . 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 Yinyu 2008). Metode steepest descent adalah metode gradien sederhana untuk pengoptimuman tak berkendala: di mana adalah fungsi terdiferensialkan secara kontinu di dapat berupa fungsi nonlinear. Masalah model kuadrat dinyatakan sebagai berikut:
dengan adalah symmetric positive definite (SPD) dan ini setara dengan memecahkan sistem linear:
. Secara umum
. Masalah
Karena diandaikan adalah matriks simetrik yang definit positif, masalah tersebut 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:
4 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. Arah pencarian dalam metode ini berbanding terbalik dengan arah gradien, yaitu dengan arah menurun tercuram (steepest descent), sehingga metode ini diberi nama steepest descent. Arah curam menurun yang diterapkan dalam metode ini merupakan arah terbaik dalam artian metode ini dapat mengurangi fungsi objektif sebanyak mungkin. Stepsize dapat diperoleh dengan pencarian exact line, yaitu: Untuk mencari minimum dari
diperoleh: (
(
)
)
Ini berarti gradien dari titik awal menuju titik selanjutnya saling tegak lurus (ortogonal) pada metode steepest descent. Dari persamaan di atas, didapat sebagai berikut: pilihan stepsize optimal
(1) di mana di dan
dan adalah vektor gradien dari adalah stepsize (ukuran langkah).
(
)
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). Berikut ini algoritme metode steepest descent: Step 1. Batas toleransi . Diberikan titik awal , dengan . Step 2. Arah pencarian . Step 3. Tentukan stepsize yang meminimumkan , sehingga . Step 4. Tentukan . Step 5. Jika ‖ ‖ , stop. Jika ‖ ‖ , maka selanjutnya , kembali ke step 2. (Sun dan Yuan 2006).
5
Lema 1 (Fungsi Error) Error adalah selisih nilai dari solusi numerik dan analitik. Semakin kecil error, maka semakin teliti solusi numerik yang didapatkan. Untuk menentukan besarnya error dalam metode steepest descent salah satunya adalah dengan menggunakan rumus sebagai berikut: {
}
dengan adalah error pada iterasi ke- , definit positif dan berukuran , dan adalah optimum. Bukti: Perhatikan bahwa
Dari fungsi
dan bentuk , kemudian dapat dibuktikan sebagai
, dimana berikut:
sehingga
di mana
dan
adalah matriks simetrik yang , dengan dan
.
6 Secara eksplisit, gradien fungsi dapat diperoleh dari . Metode steepest descent dapat diekspresikan seperti pada persamaan (1), dimana dan meminimumkan . Namun, dalam kasus khusus ini kita dapat menentukan nilai secara eksplisit. Kita peroleh dari definisi yang dapat diperoleh dari pendiferensialan , dimana
minimal pada
maka bentuk eksplisit metode steepest descent diperoleh ( di mana Dengan
)
. , didapatkan
Hasil Numerik Fungsi yang digunakan adalah fungsi kuadratik sempurna, yaitu fungsi yang dibangkitkan secara acak dengan ketentuan sebagai berikut: dengan dan adalah matriks diagonal di mana nilai diagonalnya diperoleh secara acak dengan interval [1,20]. Banyak variabel yang digunakan adalah 2, 3, 4, dan 5. Vektor adalah random integer dengan batas [-5,5]. Dimulai dari titik awal
* + dan setiap
variabel diberikan toleransi
.
Iterasi
Untuk fungsi dengan dua variabel didapatkan nilai numerik sebagai berikut: ( ) 25 20 15 10 5 0
Toleransi
7 Gambar 1 Grafik hasil untuk fungsi dua variabel
Untuk fungsi dengan tiga variabel didapatkan nilai numerik sebagai berikut: ( ) 50 Iterasi
40 30 20 10 0
Toleransi
Gambar 2 Grafik hasil untuk fungsi tiga variabel
Iterasi
Untuk fungsi dengan empat variabel didapatkan nilai numerik sebagai berikut: ( ) 120 100 80 60 40 20 0
Toleransi
Gambar 3 Grafik hasil untuk fungsi empat variabel Untuk fungsi dengan lima variabel didapatkan nilai numerik sebagai berikut: ( )
200 Iterasi
150 100 50 0
Toleransi
8 Gambar 4 Grafik hasil untuk fungsi lima variabel
Tabel 1 Analisis perbedaan banyak iterasi dan besar toleransi metode steepest descent untuk fungsi n variabel Toleransi
Banyak Iterasi untuk n Variabel 3 4
2
5
1E-10 2.5E-09 0.00001 0.000025 0.1 0.25
22 19 12 11 4 3
41 36 23 21 8 7
100 87 55 51 18 15
152 132 83 77 28 22
Titik Minimum
(-2.9999999999, 0.9999999999)
(-2.9999999999, 1, 2)
(-2.9999999999, 0.9999999999, 2, 2.9999999999)
(-2.9999999999, 0.9999999999, 2, 3, -3.9999999999)
Contoh Penghitungan Metode Steepest Descent Diketahui: (
)
* +
Penyelesaian: Gradien dari ⁄ ]
[ ⁄ [
]
Matriks Hesse * Cek kedefinitan
[ ] *
Karena Iterasi 1:
dan *
, maka
+ * (* +
+
+ *
+)
+ definit positif.
9
* +
Jadi,
* ]
[ ‖
‖ Jadi,
+
*
*
+ +
√ belum memenuhi kriteria penghentian.
Iterasi 2: *
+ +
(*
*
+)
Jadi, * * [ ‖ Jadi,
+
*
+
+ ]
*
‖ √ belum memenuhi kriteria penghentian.
+
10 Iterasi 3: *
+
(*
+
*
+)
Jadi, *
+
*
+
*
[ ‖ Jadi,
]
*
+
+
‖ √ belum memenuhi kriteria penghentian.
Iterasi 4: * (*
+ +
*
+)
11
Jadi, *
+
*
+
[
*
]
+
*
+
‖ ‖ √ Jadi, memenuhi kriteria penghentian. STOP. *
+
Gambar 5 Hasil metode steepest descent Gambar 5 menunjukkan bahwa dalam menuju solusi optimal, metode steepest descent mengambil arah tegak lurus (ortogonal) seperti yang telah dijelaskan pada subbab metode steepest descent.
12
SIMPULAN Metode steepest descent merupakan metode yang paling mendasar untuk pengoptimuman tak berkendala dan metode iteratif untuk memperoleh solusi pendekatan dari masalah awal. Hasil percobaan menunjukkan bahwa hasil iterasi tidak hanya dipengaruhi oleh banyaknya variabel yang digunakan dan besarnya toleransi, namun juga dipengaruhi oleh nilai fungsi. Karena pada setiap iterasi terdapat penurunan nilai fungsi objektif.
DAFTAR PUSTAKA Bartle RG, Sherbert DR. 1982. Introduction to Real Analysis. Second Edition. New York (US): John Wiley and Sons. Griva I, Nash SG, Sofer A. 2009. Linear and Nonlinear Optimization. Philadelphia (USA): Society for Industrial and Applied Mathematics. Klerk E, Roos C, Terlaky T. 2005. Optimization. Netherland: Delft University of Technology. 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. Varberg, Purcell, Rigdon. 2010. Kalkulus. Ed ke-9. Jakarta (IN): Erlangga. Terjemahan dari: Calculus Ninth Edition. Winston WL. 2004. Operations Research Applications and Algorithms. Ed ke-4. New York (US): Duxbury. Wungguli D. 2015. Metode Steepest Descent dengan Ukuran Langkah Baru untuk Pengoptimuman Nirkendala [tesis]. Bogor (ID): Institut Pertanian Bogor.
13 Lampiran 1 Sintaks metode steepest descent untuk fungsi dua variabel
14 Lampiran 2 Tampilan Android hasil untuk fungsi dua variabel metode steepest descent dengan toleransi 0.1
15
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 28 Mei 1993 sebagai anak kedua dari dua bersaudara, dari pasangan Maroni dan Masruroh. Tahun 2011 penulis lulus dari SMAN 82 Jakarta dan pada tahun yang sama penulis lulus seleksi masuk Institut Pertanian Bogor (IPB) melalui jalur Ujian Talenta Masuk (UTM) IPB dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama masa perkuliahan, penulis aktif pada lembaga kemahasiswaan, yaitu staf Departemen Infokom Gumatika IPB periode 2012/2013 dan periode 2013/2014, dan beberapa kegiatan kepanitiaan, antara lain bendahara kegiatan MPD Matematika IPB tahun 2013, staf Divisi Acara kegiatan SPIRIT FMIPA IPB tahun 2013, staf Divisi Pubmaslo kegiatan IPB Mathematics Challenge tahun 2013, staf Divisi DDD kegiatan Math Camp tahun 2013, staf Divisi DDD kegiatan Matematika Ria tahun 2014, dan staf Divisi Medis kegiatan MPD Matematika IPB tahun 2014.
