Metode Nelder-Mead

***'


'''Metode Nelder-Mead''', dikenal pula sebagai '''metode polihedron fleksibel''', '''metode amoeba''', atau '''metode ''downhill simplex***, adalah suatu metode numerik untuk menemukan nilai minimum atau maksimum dari sebuah fungsi objektif multivariabel. Metode ini termasuk metode telusur langsung (dengan membandingkan nilai fungsi) dan umum diterapkan pada masalah optimisasi nonlinear dengan turunan fungsi objektif yang mungkin tidak diketahui. Akan tetapi, metode Nelder-Mead juga merupakan metode telusur heuristik, yang dapat konvergen ke titik non-stasioner pada masalah yang bisa diselesaikan oleh metode-metode alternatif.

Metode Nelder-Mead diperkenalkan oleh John Nelder dan Roger Mead pada tahun 1965, sebagai pengembangan metode Spendley et al. Sebagai contoh penerapan, metode ini dapat dipakai untuk menghitung komposisi beton bertulang pada struktur beton bertulang, sehingga dapat diketahui komposisi struktur yang efisien apabila diketahui harga masing-masing komponen struktur beton bertulang.

## Gambaran umum
Metode Nelder-Mead menggunakan konsep simpleks, yakni suatu bentuk politop yang memiliki n+1 sisi dalam n dimensi. Contoh-contoh simpleks antara lain adalah: ruas garis dalam ruang satu dimensi, segitiga dalam ruang dua dimensi, tetrahedron dalam ruang tiga dimensi, dan seterusnya. Metode ini menentukan hampiran nilai optimal dari masalah dengan n variabel, yang fungsi objektifnya bersifat mulus dan unimodal. Penerapan metode yang umum adalan untuk mencari minimum fungsi; mencari maksimum fungsi f(\mathbf x) dilakukan dengan meminimumkan - f(\mathbf x).

Sebagai contoh, seorang insinyur jembatan gantung harus menentukan tebal setiap penyangga, kabel, dan tiang dari jembatan. Semua komponen tersebut saling bergantung, tetapi tidak mudah untuk memvisualisasikan dampak dari mengubah tebal dari suatu komponen. Simulasi struktur yang rumit seperti itu sering kali sangat mahal secara komputasi untuk dijalankan, mungkin membutuhkan waktu berjam-jam untuk setiap eksekusi. Metode Nelder-Mead membutuhkan, dalam varian aslinya, tidak lebih dari dua evaluasi per iterasi, kecuali untuk operasi *penyusutan* yang akan dijelaskan nanti. Hal tersebut yang membuat metode ini menarik, dibandingkan dengan beberapa metode optimasi penelusuran langsung lainnya. Tapi, metode ini mungkin memerlukan total iterasi yang besar untuk mencapai nilai optimal.

Nelder-Mead dalam n dimensi mencatat sebuah himpunan n+1 titik uji yang disusun sebagai sebuah simpleks. Metode ini lalu mengekstrapolasi perilaku fungsi objektif yang diukur pada setiap titik uji untuk menemukan titik uji baru, yang selanjutnya digunakan untuk menggantikan satu titik uji yang lama; lalu proses diulangi lagi. Cara penerapan termudah adalah mengganti titik uji terburuk dengan titik uji yang dihasilkan dari pencerminannya dengan sentroid (titik pusat) dari n titik uji yang lain. Jika titik baru ini lebih baik daripada titik uji terbaik saat ini, kita dapat mencoba merenggangkan titik uji ini dari sentroid. Tapi jika titik baru tidak lebih baik daripada sebelumnya, kita akan mengecilkan ukuran simpleks. Berikut penjelasan yang intuitif dari *Numerical Recipes*:Metode *downhill simplex* sekarang mengambil serangkaian langah, sebagian besar langkah hanyalah menggerakkan titik pada simpleks dengan nilai fungsi terbesar (titik tertinggi) melewati sisi simpleks yang menghadapnya, ke titik yang lebih rendah. Tahap ini disebut pencerminan, dan dilakukan dengan cara yang menjaga volume dari simpleks (untuk mempertahankan sifat non-degeneratifnya). Jika tahap tersebut bisa dilakukan, Metode akan memperbesar simpleks ke suatu arah tertentu untuk mengambil "langkah yang lebih besar". Ketika mencapai "dasar lembah", Metode akan menyempitkan ukuran dirinya dan mencoba mengalir menelurusi lembah. Jika ada situasi ketika metode mencoba "melewati lubang jarum", simpleks akan menyusut dari semua arah, menarik dirinya sendiri disekitar titik terendahnya (terbaik).Berbeda dengan metode-metode optimisasi modern, heuristik yang digunakan Nelder-Mead dapat konvergen ke titik non-stasioner, kecuali jika masalah memenuhi kondisi-kondisi kuat yang lebih banyak daripada yang diperlukan metode-metode modern. Perbaikan-perbaikan modern untuk heuristik Nelder-Mead telah ditemukan sejak tahun 1979.

Banyak variasi metode yang muncul bergantung dari sifat dari masalah yang ingin diselesaikan. Salah satu variasi yang umum menggunakan simpleks kecil berukuran tetap, yang bergerak mengikuti arah gradien (mirip metode penurunan gradien). Hal ini dapat dibayangkan sebagai sebuah segitiga mengelinding menuruni lembah menuju dasarnya. Metode ini juga dikenal dengan *metode polihedron fleksibel*. Tapi performa metode ini cenderung buruk ketimbang metode yang dijelaskan pada artikel ini, karena melakukan langkah-langkah kecil yang tidak diperlukan, pada daerah fungsi yang tidak diminati.

## Salah satu variasi metode Nelder-Mead
Variasi yang disajikan di bagian ini mirip dengan prosedur yang disajikan pada artikel asli Nelder-Mead. Dalam metode ini, kita ingin meminimumkan fungsi f(\mathbf x), dengan \mathbf x \in \mathbb{R}^n. Titik-titik uji saat ini adalah \mathbf x_1, \ldots, \mathbf x_{n+1}.

# *Pengurutan* dilakukan berdasarkan nilai dari setiap titik uji, f(\mathbf x_1) \leq f(\mathbf x_2) \leq \cdots \leq f(\mathbf x_{n+1}).Titik \mathbf{x}_{n+1} akan menjadi titik dengan nilai fungsi terburuk. Cek jika metode perlu dihentikan. Lihat bagian  (juga disebut dengan "kekonvergenan").
# Hitung \mathbf x_o, sentroid dari semua titik uji selain \mathbf x_{n+1}.
# *Pencerminan* Hitung titik hasil pencerminan \mathbf x_r = \mathbf x_o + \alpha (\mathbf x_o - \mathbf x_{n+1}) dengan \alpha > 0. Jika titik pencerminan lebih baik daripada titik kedua terburuk tetapi tidak daripada titik terbaik, dengan kata lain f(\mathbf x_1) \leq f(\mathbf x_r) , maka buat simpleks baru dengan menukar titik terburuk \mathbf x_{n+1} dengan titik pencerminan \mathbf x_r, dan kembali ke Tahap&nbsp;1.
# *Perluasan* terjadi jika titik pencerminan lebih baik daripada titik terbaik saat ini, f(\mathbf x_r) . Hal ini dilakukan dengan menghitung titik perluasan \mathbf x_e = \mathbf x_o + \gamma (\mathbf x_r - \mathbf x_o) dengan \gamma > 1. Jika titik perluasan lebih baik daripada titik pencerminan, f(\mathbf x_e) , maka buat simpleks baru dengan menukar titik terburuk \mathbf x_{n+1} dengan titik perluasan \mathbf x_e. Tapi jika tidak, simpleks baru dibuat dengan menukar titik terburuk dengan titik pencerminan \mathbf x_r, dan kembali ke Tahap&nbsp;1.
# *Penyempitan*. Pada tahap ini jelas titik pencerminan lebih buruk daripada titik kedua terburuk, f(\mathbf x_r) \geq f(\mathbf x_n). Selanjutnya:
#* Jika f(\mathbf x_r) , maka hitung titik penyempitan \mathbf x_c = \mathbf x_o + \rho(\mathbf x_{r} - \mathbf x_o) dengan 0 . Lalu, jika titik penyempitan lebih baik daripada titik pencerminan, f(\mathbf x_c) , buat simpleks baru dengan menukar titik terburuk \mathbf x_{n+1} dengan titik penyempitan \mathbf x_c, dan kembali ke Tahap&nbsp;1.
#* Tapi jika tidak, yakni f(\mathbf x_r) \geq f(\mathbf x_{n+1}),  titik penyempitan dihitung sebagai \mathbf x_c = \mathbf x_o + \rho(\mathbf x_{n+1} - \mathbf x_o) dengan 0 . Lalu, jika titik penyempitan lebih baik daripada titik terburuk f(\mathbf x_c) , buat simpleks baru dengan menukar titik terburuk \mathbf x_{n+1} dengan titik penyempitan \mathbf x_c, dan kembali ke Tahap&nbsp;1.
# *Penyusutan*. Tukar nilai setiap titik uji selain titik terbaik (\mathbf x_1) dengan \mathbf x_i = \mathbf x_1 + \sigma(\mathbf x_i - \mathbf x_1), lalu kembali ke Tahap&nbsp;1.

Pada prosedur metode di atas, simbol \alpha, \gamma, \rho dan \sigma secara berurutan menyatakan koefisien besar pencerminan, perluasan, penyempitan, dan penyusutan. Nilai yang umum digunakan adalah \alpha = 1, \gamma = 2, \rho = 1/2 dan \sigma = 1/2.

Beberapa tahap dapat dijelaskan secara intuitif sebagai berikut. Dalam tahap pencerminan, \mathbf x_{n+1} merupakan titik uji dengan nilai terbesar dibandingkan titik-titik uji lainnya. Kita dapat mengharapkan titik uji yang lebih baik (nilai fungsi yang lebih kecil) dengan mencerminkan titik ini ke sisi simpleks (dengan sentroid \mathbf x_o) yang menghadap dirinya. Lalu pada tahap perluasan, jika titik \mathbf x_r menjadi minimum terbaik saat ini, kita dapat mengharapkan ada nilai yang lebih baik di antara titik \mathbf x_o dan \mathbf x_r. Di tahap penyempitan, jika f(\mathbf x_r) > f(\mathbf x_n), kita dapat mengharapkan nilai yang lebih baik di dalam simpleks saat ini. Terakhir, tahap penyusutan mengurus kasus langka ketika titik penyempitan menghasilkan nilai fungsi yang lebih besar, yang menurut kutipan Nelder-Mead dijelaskan berikut:Proses penyempitan yang gagal jarang ditemui, tetapi dapat terjadi ketika pada lembah melengkung dan satu titik simpleks terletak sangat jauh dari dasar lembah daripada yang lain; penyempitan dapat menyebabkan titik pencerminan menjauhi dasar lembah dan bukannya menuju ke sana. Alhasil penyempitan-penyempitan berikutnya menjadi tidak berguna. Tindakan yang diusulkan akan menyusutkan simpleks ke arah titik uji terendah, yang pada akhirnya akan membawa semua titik ke dasar lembah.Akan tetapi, Nash menunjukkan implementasi pada aritmetika presisi-tetap dapat gagal untuk menyusutkan simpleks, sehingga sebuah uji tambahan untuk mengecek ukuran simpleks diperlukan.

### Penentuan simpleks awal
Hasil dari metode Nelder-Mead bergantung pada simpleks awal yang dipilih. Simpleks dengan ukuran yang kecil dapat membuat metode sering terjebak dalam penelurusan lokal, dan tidak menghasilkan minimum global. Nelder dan Mead menyarankan simpleks dibuat dari suatu titik \mathbf x_1, dan titik pada setiap dimensi lainnya berjarak konstan dari \mathbf x_1. Alhasil cara ini sensitif terhadap penskalaan dari variabel-variabel yang menyusun \mathbf x.

## Kriteria penghentian
Suatu kriteria diperlukan untuk menghentikan siklus iterasi. Nelder dan Mead menggunakan nilai standar deviasi sampel dari nilai-nilai fungsi dari simpleks terbaru. Jika nilai tersebut berada dibawah suatu batas toleransi, maka siklus dihentikan dan nilai fungsi terkecil dari simpleks dipilih sebagai nilai optimal. Kriteria ini dapat sensitif terhadap toleransi, khususnya pada fungsi yang "datar", nilai setiap titik uji dapat sangat mirip walau simpleks masih berukuran besar. Nash mengusulkan uji penyusutan sebagai alternatif kriteria penghentian.

## Referensi


## Bacaan lebih lanjut

* 
* 
* 
* 
* 

## Pranala luar

* Nelder–Mead (Downhill Simplex) explanation and visualization with the Rosenbrock banana function
* John Burkardt: Nelder–Mead code in Matlab - Variasi dari metode Nelder–Mead yang digunakan fungsi Matlab `fminsearch`.
* Nelder-Mead optimization in Python in the SciPy library.
* nelder-mead - Implementasi bahasa Python metode Nelder–Mead
* NelderMead() - Implementasi bahasa Go/Golang
* SOVA 1.0 (freeware) - Simplex Optimization for Various Application