Optimasi UAS [PDF]

Citation preview

Dasar Matematika Dari Algoritma Yang Terinspirasi Alam (Xin-She Yang & Xing-She He)



Bab I Pengantar Optimasi Optimalisasi adalah bagian dari beberapa program universitas karena kekurangannya dalam banyak disiplin ilmu dan aplikasi seperti desain teknik, perencanaan bisnis, ilmu komputer, data pertambangan, pengerjaan mesin, kecerdasan buatan dan industri. Teknik-teknik dan algoritma untuk optimalisasi cukup beragam, mulai dari algoritma berbasis gradien tradisional hingga algoritma berbasis kecerdasan kelompok. Bab ini memperkenalkan dasar-dasar optimasi dan beberapa teknik optimalisasi tradisional.



1.1. Pengantar Optimalisasi ada di mana-mana, walaupun ini dapat berarti hal yang berbeda dari perspektif yang berbeda. Dari kalkulus dasar, optimisasi dapat dengan mudah menemukan maksimum atau minimum dari suatu fungsi f(x) seperti f(x) = x4 + 2x2 + 1 dalam domain nyata x ϵ R. Dalam hal ini, kita dapat menggunakan metode berbasis gradien atau hanya melihat jawaban karena x4 dan r2 selalu non-negatif; nilai minimum x4 dan x2 adalah nol; dengan demikian, f(x) = X4 + 2x2 +1 bernilai minimum, fmin = 1 pada x = 0. Ini dapat dikonfirmasi dengan mudah dengan mengambil turunan pertama dari f(x) sehubungan dengan x, yang kita miliki.



yang hanya memiliki satu solusi nyata x = 0 karena x2 + 1 tidak boleh nol untuk bilangan nyata x. Kondisi f(x) = 0 tampaknya cukup untuk menentukan solusi optimal dalam kasus ini. Bahkan, fungsi ini cembung dengan hanya satu minimum di seluruh domain nyata. Namun, beberapa hal menjadi lebih rumit ketika f(x) sangat tidak linier dengan banyak optimal. Sebagai contoh, jika kita mencoba mencari nilai maksimum f (x) = sinc (x) =sin(x)/x dalam domain sebenarnya, kita dapat menggunakan :



yang memiliki jumlah solusi tak terbatas untuk x ≠ 0. Tidak ada rumus sederhana untuk solusi ini; dengan demikian, metode numerik harus digunakan untuk menghitung jawaban ini. Selain itu, bahkan dengan semua upaya untuk menemukan solusi ini, kehati-hatian harus diambil karena maksimum umumnya aktual .fmax = 1 terjadi pada x* = 0. Namun, jawaban ini hanya dapat ditemukan dengan mengambil batas x → 0, dan itu bukan bagian dari jawaban dari kondisi f(x) di atas = 0. Disini menyoroti potensi kesulitan untuk masalah nonlinear dengan beberapa optima atau multi-modalitas. Lebih lanjut, tidak semua fungsi berjalan lancar. Misalnya, jika kita mencoba menggunakan f(x) = 0 untuk mencari minimum dari



1   



kita akan menyadari bahwa f(x) tidak dapat dibedakan pada x = 0, meskipun minimum umumnya fmin = 0 terjadi pada x* = 0. dalam kasus ini teknik optimasi yang membutuhkan perhitungan derivatif tidak akan berfungsi. Masalah menjadi lebih menantang di ruang dimensi yang lebih tinggi. Misalnya, fungsi nonlinier



Dimana -10 ≤ xi ≤ 10 (untuk I = 1, 2, …… n), memiliki nilai umum minimum fmin = -1 pada x* = (0,0, ……,0) tapi fungsi ini tidak dapat dibedakan pada x*. Oleh karena itu, teknik pengoptimalan harus beragam untuk menggunakan informasi gradien pada saat yang tepat, dan tidak menggunakannya pada saat tidak ditentukan atau tidak mudah dihitung. Meskipun masalah optimasi nonlinier di atas dapat diselesaikan, kendala pada domain pencarian dan variabel independen tertentu dapat membuat domain pencarian jauh lebih rumit, yang akibatnya dapat membuat masalah semakin sulit untuk dipecahkan. Selain itu, kadangkadang, kita harus mengoptimalkan beberapa fungsi objektif, bukan hanya satu fungsi, yang pada gilirannya akan memunculkan masalah yang lebih sulit untuk dipecahkan.



1.2. Inti dari Algoritma Algoritma adalah prosedur komputasi dan iteratif. Sebagai contoh, metode Newton untuk menemukan akar polinomial p(x) = 0 dapat ditulis ulang sebagai



di mana xi adalah perkiraan pada iterasi t, dan p'(x) adalah turunan pertama dari p(x). Prosedur ini biasanya dimulai dengan tebakan awal x0 pada t = 0. Dalam kebanyakan kasus, karena p' ≠ 0 dan x0 tidak terlalu jauh dari jawaban target, algoritma ini dapat bekerja dengan sangat baik. Seperti kita tidak tahu target solusinya



terlebih dahulu, tebakan awal bisa berupa tebakan hasil pemikiran atau tebakan acak belaka. Namun, jika tebakan awal terlalu jauh, algoritma mungkin tidak pernah mencapai solusi akhir atau gagal total. Sebagai contoh, untuk p(x) = x2 + 9x – 10 = (x – 1) (x + 10) kita tahu akarnya x* = 1 dan x* = -10 kita juga punya p’(x) = 2x + 9 dan



Jika kita memulai dari x0 = 10, kita dapat dengan mudah mencapai x* = 1 dalam rentang kurang dari lima iterasi. Jika kita gunakan x0 = 100, kemungkinan dapat menggunakan sekitar delapan iterasi, tergantung tingkat akurasi yang kita inginkan. Jika kita memulai nilai apa pun x0 > 0, kita



2   



hanya dapat mencapai x* = 1 dan kita tidak akan pernah mencapai nilai akar lain x* = -10. Jika kita memulai dengan x0 = -5, kita dapat mencapai x* = -10 sekitar tujuh iterasi dengan sebuah akurasi dari 10-9. bagamanapun kita dapat mencapai x* = -4,5 algoritma hanya akan gagal karena p’(x0) = 2x0 + 9 = 0 Disini dengan jelas menunjukkan bahwa solusi akhir biasanya akan bergantung pada di mana titik awal-awalnya. Metode ini dapat dimodifikasi untuk menyelesaikan masalah optimisasi. Sebagai contoh, untuk tujuan obyektif tunggal f(x), nilai minimal dan maksimal harus muncul pada titik stasioner f’(x) = 0, yang menjadi masalah pencarian akar untuk f(x). Itulah, maksimum atau minimum f(x) dapat ditemukan dengan memodifikasi metode Newton sebagai rumus berulang berikut :



Sebagai contoh, kita tahu bahwa solusi optimal f(x) = x2 + 2x + 1 adalah fmin = 0 pada x* = -1 setelah f’(x) = 2x + 2 dan f’’(x) = 2, kita memiliki



yang berarti bahwa metode ini dapat mencapai solusi optimal x* = -1 dalam satu langkah, mulai dari titik awal mana pun xt = a ϵ R. Ini adalah kasus khusus karena f(x) adalah kuadrat (fungsi cembung), yang termasuk dalam kelas optimasi cembung. Dalam hal ini, metode Newton adalah algoritma yang sangat efisien. Secara umum f(x) sangat nonlinier dan tentu saja tidak cembung; dengan demikian, algoritma mungkin tidak efisien dan masalah seperti itu dapat menjadi tantangan untuk dipecahkan. Untuk sebuah masalah D-dimensional dengan sebuah objek f(x) dengan variable independen x= (x1, x2, ……. XD) rumus iterasi di atas dapat digeneralisasi ke bentuk vector



di mana kita telah menggunakan konvensi notasi x' untuk menunjukkan vektor solusi saat ini pada iterasi t (jangan dikacaukan dengan eksponen). Kedua notasi xt dan xt umumnya digunakan dalam literatur dan di banyak buku teks populer. Kami juga akan menggunakan kedua notasi tersebut secara bergantian dalam buku ini jika tidak ada kebingungan. Secara umum, algoritma A dapat ditulis sebagai



yang mewakili fakta bahwa vektor solusi baru adalah fungsi dari vektor solusi xt yang ada, beberapa solusi terbaik secara historis h* selama sejarah iterasi dan sekumpulan parameter yang bergantung pada algoritma (p1, p2, ..., pk). Bentuk fungsi yang tepat akan tergantung pada algoritma, dan algoritma yang berbeda hanya berbeda dalam hal bentuk fungsi, jumlah parameter dan cara menggunakan data historis.



3   



1.3. Optimasi Tidak Terbatas Masalah optimisasi disebut tidak dibatasi jika memiliki tujuan untuk dioptimalkan, tanpa kendala. Jika kondisi tambahan dikenakan pada nilai yang diizinkan dari variabel independen atau keputusan, masalah tersebut menjadi masalah optimisasi yang terbatas. Mari kita lihat masalah optimasi fungsi yang tidak dibatasi.



1.3.1. Fungsi Univariat Masalah optimisasi paling sederhana tanpa kendala mungkin adalah pencarian untuk maksimal atau minimum dari fungsi univariat f(x) untuk



(atau atau di seluruh domain



nyata R) kami hanya menulis



Atau lebih sederhana



Sebuah masalah optimalisasi tanpa ada kendala pada variable keputusan x sering disebut masalah optimalisasi tidak dibatasi. Untuk masalah optimasi yang tidak dibatasi, optimalitas sering terjadi pada titik-titik kritis yang diberikan oleh kondisi stasioner f’(x) = 0. Namun, kondisi stasioner ini hanya kondisi yang diperlukan, tetapi itu bukan kondisi yang memadai. Jika f’(x*) = 0 dan f’’(x*) > 0, ini adalah minimum lokal. Sebaliknya, jika f’(x) = 0 dan f’’(x*) < 0, maka itu adalah maksimum lokal. Bagaimanapun, jika f’(x*) = 0 tapi f’’(x) tidak pasti (baik positif maupun negatif) ketika, x → x*, kemudian x* sesuai dengan titik kedudukan. Sebagai contoh f(x) = x3 memiliki titik kedudukan x* = 0 karena f’(x) = 0 tapi f” mengubah tanda dari f”(0+) > 0 ke f” (0-) < 0. Secara umum, fungsi dapat memiliki beberapa titik stasioner. Untuk menemukan global maksimum atau minimum, kita mungkin harus melalui setiap titik stasioner, kecuali fungsi objektifnya cembung. Perlu ditunjukkan bahwa notasi argmin atau argmax digunakan dalam beberapa buku teks; dengan demikian, optimasi di atas dapat ditulis sebagai



Atau



Notasi ini menekankan pada argumen x sehingga tugas optimisasi adalah menemukan titik (atau titik) dalam domain f(x) yang memaksimalkan (atau meminimalkan) nilai fungsi. Di sisi lain, notasi yang kami gunakan dalam (1.12) menekankan nilai maksimum atau minimum dari fungsi objektif. Kedua jenis notasi digunakan dalam literatur. Untuk



kondisi stasioner atau opsional adalah



4   



yang tampaknya tidak mudah diselesaikan secara analitis. Namun, Kami dapat menulis ulang sebagai



Jadi, ada tiga solusi x* = -2, +2 dan +5. Derivatif kedua adalah



Pada x = 2, kita memiliki f(2) = 672 dan f”(2) = -144; dengan demikian, titik ini adalah maksimum lokal. Pada x = 5, kita memiliki f(5) = 375 dan f”(5) = 252, yang berarti bahwa titik ini adalah minimum lokal. Di sisi lain, pada x = -2, kita memiliki f”(-2) = 336 dan f(-2) = 32; dengan demikian, ini adalah titik lokal minimum, Membandingkan dua minimum pada x* = -2 dan x* = 5, kita dapat menyimpulkan bahwa secara umum minimum terjadi pada x* = -2 dengan f min = 32. Karena ada satu maksimum lokal pada x* = 2, dapatkah kita menyimpulkan bahwa umum maksimum adalah f max = 672? Jawabannya adalah tidak. Jika kita melihat poin lain seperti x = 7 atau x = -5, kita memiliki f(7) = 1247 dan f(-5) = 2975 yang jauh lebih besar dari 672: dengan demikian, 672 tidak bisa menjadi maksimum global. Bahkan, fungsi ini tidak terikat dan dengan demikian maksimumnya adalah +oo. Fungsi semacam ini sering disebut sebagai multimodal. Namun, jika kita memaksakan interval sederhana seperti itu x ϵ [-3, 7] Kemudian, kita dapat menyimpulkan bahwa global maksimum terjadi pada x = 7 (batas kanan) dengan f(7) = 1247. Namun, dalam hal ini, maksimum tidak terjadi pada titik stasioner. Contoh ini jelas menunjukkan bahwa perbaikan harus dilakukan ketika berhadapan dengan fungsi multimoda. Maksimalisasi suatu fungsi f(x) dapat dikonversi menjadi minimalisasi dari A – f(x), di mana A biasanya angka positif (sampai A = 0 akan dihitung). Sebagai contoh, kita tahu bahwa maksimum f(x) = e –x2, untuk x ϵ (-oo, oo), adalah 1 pada x* = 0. Masalah ini dapat dikonversi ke masalah minimisasi -f(x). Untuk alasan ini, masalah optimalisasi dapat dinyatakan sebagai minimalisasi atau maksimalisasi, tergantung pada konteks dan kenyamanan formulasi. Untuk masalah optimasi fungsi sederhana dengan satu variabel independen, prinsip matematika mungkin mudah dipahami, dan optimalitas terjadi baik pada f'(x) = 0 (titik stasioner) atau pada batas (batas interval sederhana). Namun, mungkin tidak begitu mudah untuk menemukan solusi optimal yang sebenarnya, bahkan untuk sambungan yang tampaknya sederhana seperti sinc(x) = sin (x)/x. Untuk



ia memiliki jumlah minimum lokal minimum dan maksimum dengan global



maksimum fmax = 1 terjadi pada x = 0 seperti yang terlihat pada Gambar 1.1. Namun, metode analitik mungkin tidak mudah. Kami mengetahui



5   



Gambar 1.1. Contoh fungsi multimoda yang sangat nonlinier Yang mengarah ke



Tetapi tidak ada formula eksplisit untuk jawaban, kecuali untuk beberapa perkiraan. Bahkan kita dapat menyelesaikannya secara numerik untuk menemukan beberapa akar, tetapi kita tidak dapat menemukan semua akar (jumlah banyak sekali). Selain itu, akar ini tidak memberikan indikasi yang jelas bahwa x = 0 sesuai dengan maksimum global. Bahkan, maksimum pada x = 0 hanya dapat diperoleh dengan metode lain seperti mengambil batas dari bentuk alternatif atau dengan beberapa integral kompleks. Seperti yang telah kita lihat dari contoh ini, metode numerik harus digunakan untuk menemukan titik optimal yang sebenarnya. Disini melihat masalah utama. Sekalipun kita mengetahui teori dasar pengoptimalan, mungkin tidak secara langsung banyak membantu dalam menyelesaikan kelas masalah tertentu seperti masalah pengoptimalan multimodal yang sangat nonlinier. Faktanya, metode analitis hanya dapat menyelesaikan sejumlah kecil masalah. Untuk sebagian besar masalah, algoritma numerik yang akan menjadi penting.



1.3.2. Fungsi Multivarian Untuk fungsi multivarian f(x) dengan variabel n dimana x = (x1, …..Xn), pengoptimalannya dapat dinyatakan dengan cara yang mirip dengan masalah pengoptimalan univariat.



Di sini kita telah menggunakan notasi Rn untuk menyatakan bahwa vektor x berada dalam ruang dimensi n di mana setiap komponen xi adalah bilangan real. Itu adalah untuk i = 1, 2, ….., n. Untuk



sebuah



fungsi



f(x),



kita



dapat



mengembangkannya



secara



lokal



(dengan



kebingungan/gangguan I ϵ I 0, I ϵ I > 0 akan mengarah ke I Δf I = I f(x*) I > 0. Dengan kata lain, f(x) akan meningkat sebagai I ϵ I meningkat. Sebaliknya jika λj < 0, f(x) akan berkurang sebagai I ϵ I > 0 meningkat. Jelas, dalam kasus khusus λj = 0, fungsi f(x) akan tetap konstan di sepanjang arah yang sesuai v j. Mari kita lihat sebuah contoh. Kita tahu fungsinya



memiliki titik kedudukan di (0,0). Itu meningkat sepanjang x = y arah dan penurunan sepanjang x = -y. dari analisis diatas, kita mengetahui bahwa x* = (x*, y*)T = (0,0)T dan f(x*, y*) = 0. Sekarang kita memiliki



Dimana



7   



Masalah nilai eigen adalah sederhana



Atau



Solusinya



Untuk λj = 1, vektor eigen yang sesuai adalah



Demikian pula. Untuk λ2 = -1, vektor eigen adalah



Karena A adalah simetris, v1 dan v2 adalah ortonormal karena



Sehingga kita dapat



Sebagai λj = I adalah positif, f meningkat sepanjang arah v1 = (1, 1)T yang mana memang sepanjang garis x = y. Demikian pula. Untuk λ2 = -1, f akan menurun sepanjang v2 = (1, -1)T yang persis di sepanjang garis x = -y. Karena tidak ada nilai eigen nol, fungsi tidak akan tetap konstan di wilayah sekitar (0, 0). Ini jelas menunjukkan bahwa sifat-sifat matriks Hessian lokal dapat menunjukkan bagaimana fungsi dapat bervariasi di lingkungan itu, dan dengan demikian harus memberikan informasi yang cukup tentang optimalitas lokalnya.



1.4. Optimasi Secara umum, masalah optimisasi dengan n variabel keputusan dapat dirumuskan sebagai masalah optimisasi terbatas berikut ini :



Bergantung atas



8   



di mana hi dan gj adalah kendala kesetaraan dan kendala ketidaksetaraan, masing-masing. Dalam kebanyakan kasus, fungsi masalah f {x), hi {x) dan gj (x) semuanya nonlinier, dan masalah optimisasi nonlinier semacam itu bisa sulit untuk dipecahkan. Dalam hal semua fungsi masalah linear, itu menjadi masalah pemrograman linier. Selain itu, jika hi dan gj linier, membentuk domain cembung, dan tujuan f adalah cembung, ini menjadi masalah optimisasi cembung. Program linier dan optimisasi cembung dapat memiliki algoritma yang efisien untuk diselesaikan [18, 28, 121]. Bahkan untuk program linier, jika semua variabel hanya mengambil nilai integer, masalah seperti itu menjadi masalah pemrograman integer, yang bisa jauh lebih sulit untuk dipecahkan. Jika beberapa variabel diskrit atau bilangan bulat, sementara nilai lainnya kontinu, itu menjadi masalah pemrograman integer campuran (MIP) yang juga bisa menjadi tantangan untuk dipecahkan. Dalam kasus-kasus ekstrim seperti masalah penjualan perjalanan, tidak ada algoritma yang efisien untuk menangani masalah seperti itu. Ada berbagai kelas teknik optimasi, termasuk pemrograman linier, pemrograman kuadratik, optimasi cembung, metode titik interior, metode wilayah kepercayaan, gradien konjugat dan banyak lainnya [18, 98, 113, 121]. Secara umum, masalah optimasi adalah sangat nonlinear dan multimodal; Algoritma tradisional ini sering berjuang untuk mengatasi masalah nonlinear, solusi apa pun yang ditemukan cenderung merupakan solusi optimal lokal. Tidak ada metode yang efektif untuk menemukan solusi optimal global untuk masalah yang sangat nonlinier dengan kendala yang kompleks. Dalam kasus seperti itu, algoritma optimisasi yang diilhami sifat yang canggih cenderung menjadi alternatif yang menjanjikan dalam praktiknya. Ada berbagai kelas teknik optimasi, termasuk pemrograman linier, pemrograman kuadratik, optimasi cembung, metode titik interior, metode wilayah kepercayaan, gradien konjugat (berkumpul) dan banyak lainnya [18, 98, 113, 121]. Secara umum, masalah optimasi adalah sangat nonlinear dan multimodal; Algoritma tradisional ini sering berjuang untuk mengatasi masalah nonlinear, solusi apa pun yang ditemukan cenderung merupakan solusi optimal lokal. Tidak ada metode yang efektif untuk menemukan solusi optimal umum untuk masalah yang sangat nonlinier dengan kendala yang kompleks. Dalam kasus seperti itu, algoritma optimisasi yang diilhami sifat alam yang canggih cenderung menjadi alternatif praktis yang menjanjikan. Sebelum kami memperkenalkan algoritma yang diilhami sifat alam kemudian, kami fokus pada beberapa algoritma tradisional.



1.5. Metode Berbasis Gradien Metode berbasis gradien adalah teknik berulang yang secara ekstensif menggunakan informasi gradien dari fungsi tujuan selama iterasi. Untuk meminimalkan fungsi f(x), esensi dari metode ini adalah



9   



di mana α adalah ukuran langkah yang dapat bervariasi selama iterasi, dan k adalah penghitung iterasi. Sebagai tambahan



adalah fungsi dari gradient



saat ini x(k) dan arah pencarian biasanya di sepanjang arah gradien negatif



dan lokasi   untuk



masalah minimisasi. Metode yang berbeda menggunakan berbagai bentuk



1.5.1. Metode Newton Metode Newton adalah algoritma pencarian akar. tetapi dapat dimodifikasi untuk memecahkan masalah optimasi. Ini karena optimasi setara dengan menemukan akar turunan pertama f'(x) berdasarkan pada kondisi stasioner begitu fungsi objektif f(x) diberikan. Untuk fungsi yang terus-menerus dapat didiferensiasi f(x), kita memiliki ekspansi Taylor dalam tenns of Δx = x - xk tentang titik tetap xk.



istilah ketiga yang merupakan bentuk kuadratik. Karenanya f (x) diminimalkan jika Δx adalah solusi dari persamaan linear berikut (setelah mengambil turunan pertama sehubungan dengan vektor kenaikan Δx = x - xk)



Yang mana diberikan



Ini dapat dituliskan kembali sebagai



Dimana H-1 (xk) adalah kebalikan dari matrik Hessian H =



yang dijelaskan sebagai



Matriks ini simetris karena kenyataan tersebut



Karena setiap langkah adalah perkiraan. solusi berikutnya xk+1 adalah sekitar



atau dalam notasi yang berbeda sebagai



Jika prosedur iterasi dimulai dari vektor awal x(0), biasanya suatu titik tebakan di wilayah layak. kemudian formuia Newton untuk iterasi k menjadi 10   



Perlu ditunjukkan bahwa jika f(x) adalah kuadratik, maka solusinya dapat ditemukan tepat dalam satu langkah. Untuk mempercepat konvergensi, kita dapat menggunakan ukuran langkah yang lebih kecil  dan kami memiliki metode Newton yang dimodifikasi



Terkadang, mungkin perlu waktu untuk menghitung matriks Hessian untuk turunan kedua, terutama ketika dimensinya tinggi. Alternatif yang baik adalah dengan menggunakan matriks identitas n x n identitas matrix 1 untuk mendekati H sehingga H-1 = 1 dan kami memiliki bentuk sederhana dari kelas metode quasi-Newton



yang biasanya disebut metode keturunan paling curam untuk masalah minimisasi. Di sini, ukuran langkah α juga disebut tingkat pembelajaran dalam literatur.



1.5.2. Metode Turunan Terjal Inti dari metode ini adalah untuk menemukan nilai serendah mungkin dari fungsi objektif f(x) dari titik saat ini x(k). Dari ekspansi Taylor dari f(x) tentang x(k), kita miliki



Dimana



  adalah vektor kenaikan. Karena kami mencoba untuk



menemukan pendekatan yang lebih rendah (lebih baik) untuk fungsi tujuan, itu mensyaratkan bahwa istilah kedua di sebelah kanan adalah negatif. Itu adalah,



Dari analisis vektor, kita tahu bahwa produk dalam



  dari dua vektor u dan v adalah



terbesar ketika mereka paralel (tetapi berlawanan arah jika negatif yang lebih besar dicari). Karena itu



 menjadi keturunan terbesar, ketika



di mana α > 0 adalah ukuran langkah. Ini adalah kasus ketika arah Δs adalah sepanjang penurunan paling curam dalam arah gradien negatif. Seperti yang telah kita lihat sebelumnya, metode ini adalah metode quasi-Newton. Pilihan ukuran langkah sangat tidak penting. Ukuran langkah yang sangat kecil berarti pergerakan lambat ke minimum lokal, sementara langkah besar mungkin melebihi batas dan selanjutnya membuatnya bergerak jauh dari minimum lokal. Oleh karena itu, ukuran langkah α =α



(k)



harus berbeda pada setiap langkah iterasi dan harus dipilih sehingga meminimalkan



fungsi tujuan



Di setiap iterasi, gradien dan ukuran langkah akan



dihitung. Sekali lagi, tebakan awal yang baik dari titik awal dan ukuran langkah sangat berguna. 11   



Mari kita meminimalkan fungsinya



Dimana



menggunakan metode penurunan curam dimulai dengan awal x(0) = (10, 15)T. Kami mengetahui gradiennya



Karena itu



Pada iterasi pertama, kita dapat



Ukuran langkah kita harus dipilih sedemikian rupa sehingga f(x(1)), adalah minimum, yang berarti itu



harus diminimalkan. Ini menjadi masalah optimisasi untuk variabel independen tunggal αo. Semua teknik untuk masalah optimisasi univariat seperti metode Newton dapat digunakan untuk menemukan αo. Kami juga dapat memperoleh solusi dengan menetapkan



Yang mana jawabannya adalah ≈ 0,04001 Pada tahap selanjutnya, kita mendapatkan



Mimimasi dari f(α1) diberikan α1 ≈ 0,066, dan lokasi baru turunan paling curam adalah



Pada iterasi ketiga, kita mendapatkan



Minimasi dari f(α2) mengarah ke α2 ≈ 0,040 dan kita mendapatkan



Kemudian, iterasi berlanjut sampai toleransi yang ditentukan terpenuhi. Dari kalkulus, kita mengetahui bahwa kita dapat menseting perhitungan pertama derivatif secara parsial. 12   



Dan kita mengetahui bahwa minimum terjadi tepat pada



Metode penurunan curam memberikan solusi yang hampir tepat setelah hanya tiga iterasi. Dalam menemukan ukuran langkah αk dalam metode penurunan curam di atas, kami telah menggunakan kondisi stasioner



Nah, Anda dapat mengatakan bahwa jika



kami menggunakan kondisi stasioner ini untuk f(α0), mengapa tidak menggunakan metode yang sama untuk mendapatkan poin minimum f(x) pada tempat pertama. Ada dua alasan di sini. Alasan pertama adalah tersebut disini adalah contoh sederhana untuk menunjukkan bagaimana metode penurunan paling curam bekerja. Alasan kedua adalah bahkan untuk beberapa variabel yang rumit f(x1,…..xn) (katakan n = 500), kemudian f(αk) pada setiap langkah k masih merupakan fungsi univariat, dan optimalisasi seperti itu f(αk) jauh lebih sederhana dibandingkan dengan masalah multivarian asli. Perlu ditunjukkan bahwa dalam banyak kasus, kita tidak perlu secara eksplisit menghitung ukuran langkah αk, dan sebaliknya kita dapat menggunakan nilai kecil yang memadai atau skema adaptif, yang dapat bekerja cukup baik dalam praktiknya. Bahkan, αk dapat dianggap sebagai parameter-hiper, yang dapat disetel atau disetel adaptif. Poin ini akan menjadi lebih jelas ketika kita membahas pencarian baris dan metode gradien stokastik nanti dalam bab ini. Dari contoh kita, kita tahu bahwa konvergensi dari iterasi kedua ke iterasi ketiga lambat. Bahkan, penurunan paling curam biasanya lambat begitu minimisasi lokal sudah dekat. Ini karena dekat nilai minimal lokal, gradiennya hampir nol, dan dengan demikian, tingkat turunan juga melambat. Jika akurasi tinggi diperlukan di dekat nilai minimum Iokal, metode pencarian lokal lainnya harus digunakan. Ada banyak variasi metode penurunan curam. Jika optimasi untuk menemukan angka maksimum, maka metode ini menjadi metode mendaki bukit karena tujuannya adalah untuk mendaki bukit (sepanjang arah gradien) ke puncak tertinggi.



1.5.3. Pencarian Baris Dalam metode penurunan curam, ada dua bagian penting: arah keturunan dan ukuran langkah (atau seberapa jauh untuk turun). Perhitungan ukuran langkah yang tepat mungkin sangat memakan waktu. Pada kenyataannya, kami bermaksud menemukan arah penurunan yang tepat. Maka jumlah keturunan yang masuk akal, belum tentu jumlah yang tepat, selama setiap iterasi biasanya akan cukup. Untuk ini, kami pada dasarnya menggunakan metode pencarian garis. Untuk menemukan minimum lokal dari fungsi objektif f (x), kami mencoba mencari sepanjang sk arah penurunan dengan ukuran langkah yang dapat disesuaikan sehingga.



13   



berkurang sebanyak mungkin, tergantung pada nilai αk. Secara longgar, ukuran langkah yang cukup benar harus memenuhi persyaratan Wolfe [18,98]:



Dan



Dimana 0 < γ1 < γ2 < 1 adalah parameter yang bergantung pada algoritma. Kondisi pertama adalah kondisi penurunan yang cukup untuk αk, sering disebut kondisi atau aturan Armijo, sedangkan ketidaksetaraan kedua sering disebut sebagai kondisi kelengkungan. Untuk sebagian besar fungsi, kita bisa menggunakan



  Kondisi



ini biasanya cukup untuk memastikan bahwa algoritma menyatu dalam banyak kasus; namun, kondisi yang lebih kuat mungkin diperlukan untuk beberapa fungsi yang sulit. Langkah-langkah dasar metode pencarian garis dapat diringkas dalam Algoritma 1.



1.5.4. Metode Gradien Konjugasi Metode gradien konjugasi memiliki kelas yang lebih luas dari apa yang disebut metode iterasi ruang bagian Krylov - Metode gradien konjugat dipelopori oleh Magnus Hestenes, Eduard Stiefel dan Cornelius Lanczos pada 1950-an [8,86]. Dinobatkan sebagai salah satu dari sepuluh algoritma abad ke-17. Metode gradien konjugat dapat digunakan untuk menyelesaikan sistem linear.



Tebakan pertama x0 pada k = 0 Sementara



menghitung



Mencari arah pendarian Sk = Penyelesaian untuk αk oleh penurunan



 secara signifikan



sambil memuaskan kondisi Wolfe; update jawaban oleh Akhir Algoritma 1 : Langkah Dasar Metoda Pencarian Garis dimana A sering merupakan matriks pasti positif simetris. sistem di atas setara dengan meminimalkan fungsi berikut f(u) :



dimana u adalah konstanta dan dapat dianggap nol. Dengan membedakan fungsi di atas terhadap u, kita dapat melihatnya



menuju ke Au = b.



14   



Secara umum, ukuran nilai A dapat sangat luas dan tersebar n > 100,000, tetapi tidak dibutuhkan bahwa A adalah benar pasti posisi simetris. Faktanya, kondisi utama adalah bahwa A akan menjadi matrik normal. A matrik kuadrat A disebut normal jika ATA = AAT. Oleh karena itu, matriks simetris adalah matriks normal, demikian juga matriks ortogonal karena matriks ortogonal Q yang memuaskan QQT = QTQ =1. Teori di balik metode berulang ini terkait erat dengan ruang bagian Krylov



ϗk, yang direntang



oleh a dan b seperti yang didefinisikan oleh



Dimana Ao = 1 Jika kita menggunakan prosedur berulang untuk mendapatkan solusi perkiraan uk ke Au = b pada iterasi k, sisa perhitungan diberikan oleh



yang pada dasarnya adalah gradien negatif



Vektor arah pencarian dalam metode



gradien konjugat kemudian ditentukan oleh



Solusinya sering dimulai dengan tebakan awal u0 pada k = 0, dan hasil secara iteratif. Langkahlangkah di atas dapat ditulis ulang sebagai



Dan



Dimana



Iterasi berhenti ketika akurasi yang ditentukan tercapai. Ini dapat dengan mudah diprogram dalam bahasa terprogram apa pun, terutama Matlab. perlu menunjukkan bahwa tebakan awal r0 dapat berupa tebakan terukur, Namun, d0 harus diambil sebagai d0 = r0, jika tidak, algoritma mungkin tidak muncul. Dalam kasus ketika A tidak simetris, Anda dapat menggunakan algoritma general residual minimal residual (GMRES) yang dikembangkan oleh Y. Saad dan M.H. Schultz pada tahun 1986. Untuk tinjauan literatur yang lebih komprehensif, pembaca dapat merujuk ke press et al. [86]



1.5.5. Keturunan Gradien Stochastic Dalam banyak masalah optimisasi, terutama dalam pembelajaran mendalam [11,62], fungsi tujuan atau fungsi risiko yang dapat diminimalisasi dapat ditulis dalam bentuk berikut:



15   



Dimana



Disini,



adalah vektor parameter seperti bobot dalam jaringan saraf.



Sebagai tambahan



adalah target m atau data nyata (titik data atau data).



sedangkan ui (xi) adalah nilai yang diprediksi berdasarkan input x1 oleh model seperti model yang didasarkan pada jaring saraf yang terlatih. Keturunan gradien standar untuk menemukan parameter bobot baru dalam hal rumus iteratif dapat ditulis sebagai berikut



Dimana 0 < ᵑ < 1 adalah tingkat belajar atau ukuran langkah. Di sini, gradient



sehubungan



dengan w. Ini membutuhkan perhitungan gradien m. Ketika m besar dan jumlah iterasi t besar, ini bisa sangat mahal. Untuk menyimpan perhitungan, gradien sebenarnya dapat didekati dengan gradien pada nilai tunggal pada fi bukan semua nilai m. adalah,



Dimana ᵑt adalah tingkat belajar, saat iterasi t, dimana dapat dilakukan variasi dengan iterasi. Tapi ini perkiraan kasar pada titik yang dipilih secara acak i pada iterasi t ke gradien sebenarnya, harga perhitungan telah berkurang secara dramatis oleh faktor 1/m. Karena sifat acak pemilihan sampel i (yang bisa sangat berbeda pada setiap iterasi), cara menghitung gradien ini disebut gradien stokastik. Metode yang didasarkan pada estimasi kasar gradien seperti ini disebut turunan gradien stokastik (SGD) untuk minimisasi atau kenaikan gradient stokastik (SGA) untuk maksimisasi. Tingkat pembelajaran ᵑt harus dikurangi secara bertahap. Misalnya, pengurangan tingkat pembelajaran yang umum digunakan adalah



Dimana β > 0 adalah hiperparameter. Bottou [17] menunjukkan bahwa SGD hampir pasti akan ketemu jika



Tingkat konvergensi terbaik adalah ᵑt ~ 1/t dengan rata-rata kesalahan residual berkurang dalam cara E ~ 1/t



16   



Patut ditunjukkan bahwa penurunan gradien stokastik bukanlah penurunan langsung dalam arti gradien yang sebenarnya, tetapi penurunannya adalah dalam rata-rata atau ekspektasi. Demikian. caranya masih bisa zig-zag. Kadang-kadang, mungkin menaikan gradien, tidak harus sepanjang jalan ke arah gradien, tetapi efisiensi komputasi keseluruhan biasanya jauh lebih tinggi daripada keturunan gradien yang benar untuk masalah skala besar. Oleh karena itu, banyak digunakan untuk masalah pembelajaran yang mendalam dan masalah skala besar.



1.5.6. Metode Subgradien Semua metode berbasis gradien di atas mengasumsikan secara implisit bahwa fungsinya terdiferensiasi. Dalam hal fungsi-fungsi yang tidak dapat dibedakan, kita harus menggunakan metode subgradien untuk fungsi-fungsi cembung non-diferensial atau lebih umum metode bebas-gradien untuk fungsi-fungsi nonlinear yang akan diperkenalkan kemudian dalam buku ini. Untuk fungsi cembung yang tidak dapat dibedakan, mungkin ada lebih dari satu vektor subgradien di titik mana pun, dan vektor subgradien vk dapat didefinisikan oleh



dan rumus iterasi Newton (1.37) dapat digantikan oleh



Dimana αk adalah ukuran langkah pada iterasi k. Sebagai subgradien iterasi dihitung pada iterasi k, metoda ini disebut metoda subgradien. Patut ditunjukkan bahwa karena banyak subgradien yang tidak wajar, maka subradien tersebut dihitung pada xk mungkin tidak ke arah yang diinginkan. Beberapa pilihan seperti memilih nilai yang lebih besar dari norma v dapat diharapkan. Selain itu, melalui ukuran langkah yang konstan αk = α dimana 0 < α < 1 dapat bekerja dengan baik dalam banyak kasus, dibutuhkan ukuran langkah αk harus bervariasi dan diskalakan jika perlu. Misalnya, skema yang umum digunakan untuk berbagai ukuran langkah adalah



Dan



Metode subgradien masih digunakan dalam praktiknya, dan ini bisa sangat efektif dalam kombinasi dengan metode gradien stokastik, yang mengarah ke kelas yang disebut metode subgradien stokastik. Konvergensi dapat dibuktikan dan pembaca yang tertarik dapat merujuk pada literatur yang lebih maju seperti Bertsbekas et al. [14]. Keterbatasan metode subgradien adalah dipakai untuk fungsi cembung. Dalam hal fungsi umum nonlinier, tidak dapat dibedakan, non-cembung, kita dapat menggunakan metode bebas gradien dan kami akan memperkenalkan beberapa metode ini pada bab berikutnya.



17