Lihat sumber Metode Nelder-Mead

''''''

'''Metode Nelder-Mead''', dikenal pula sebagai '''metode polihedron fleksibel''', '''metode amoeba''', atau '''metode ''downhill simplex''''', adalah suatu [[Analisis numerik|metode numerik]] untuk menemukan nilai minimum atau maksimum dari sebuah [[Fungsi kerugian|fungsi objektif]] multivariabel. Metode ini termasuk metode [[Penelurusan pola (optimisasi)|telusur langsung]] (dengan membandingkan nilai fungsi) dan umum diterapkan pada [[Optimisasi|masalah optimisasi]] nonlinear dengan turunan fungsi objektif yang mungkin tidak diketahui. Akan tetapi, metode Nelder-Mead juga merupakan metode telusur [[Heuristika|heuristik]], yang dapat konvergen ke [[Titik stasioner|titik non-stasioner]]<ref>* Michael J. D. Powell. ''On Search Directions for Minimization Algorithms''. ''Mathematical Programming''. 1973. Vol. 4. hlm. 193–201. doi:10.1007/bf01584660. * K. I. M. McKinnon. ''Convergence of the Nelder–Mead simplex method to a non-stationary point''. ''SIAM Journal on Optimization''. 1999. Vol. 9. hlm. 148–158. doi:10.1137/S1052623496303482. (algorithm summary online).</ref> pada masalah yang bisa diselesaikan oleh metode-metode alternatif.<ref>* Yu, Wen Ci. 1979. "Positive basis and a class of direct search techniques". ''Scientia Sinica'' [''Zhongguo Kexue'']: 53—68. * Yu, Wen Ci. 1979. "The convergent property of the simplex evolutionary technique". ''Scientia Sinica'' [''Zhongguo Kexue'']: 69–77. * Tamara G. Kolda. ''Optimization by direct search: new perspectives on some classical and modern methods''. ''SIAM Rev''. 2003. Vol. 45 (3). hlm. 385–482. doi:10.1137/S003614450242889. * Robert Michael Lewis. ''Implementing generating set search methods for linearly constrained minimization''. ''SIAM J. Sci. Comput''. 2007. Vol. 29 (6). hlm. 2507–2530. doi:10.1137/050635432.</ref>

Metode Nelder-Mead diperkenalkan oleh [[John Nelder]] dan [[Roger Mead]] pada tahun 1965,<ref>John A. Nelder. ''A simplex method for function minimization''. ''Computer Journal''. 1965. Vol. 7 (4). hlm. 308–313. doi:10.1093/comjnl/7.4.308.</ref> sebagai pengembangan metode Spendley et al.<ref>W. Spendley. [https://archive.org/details/sim_technometrics_1962-11_4_4/page/441 Sequential Application of Simplex Designs in Optimisation and Evolutionary Operation]. ''Technometrics''. 1962. Vol. 4 (4). hlm. 441–461. doi:10.1080/00401706.1962.10490033.</ref> 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 <math>n+1</math> sisi dalam <math>n</math> 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 <math>n</math> variabel, yang fungsi objektifnya bersifat [[Fungsi mulus|mulus]] dan [[unimodal]]. Penerapan metode yang umum adalan untuk mencari minimum fungsi; mencari maksimum fungsi <math>f(\mathbf x)</math> dilakukan dengan meminimumkan <math>- f(\mathbf x)</math>.

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 <math>n</math> dimensi mencatat sebuah himpunan <math>n+1</math> 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 <math>n</math> 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'':<ref>W. H. Press. [http://apps.nrbook.com/empanel/index.html#pg=502 Numerical Recipes: The Art of Scientific Computing]. Cambridge University Press. 2007. ISBN 978-0-521-88068-8.</ref><blockquote>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).</blockquote>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.<ref>* Michael J. D. Powell. ''On Search Directions for Minimization Algorithms''. ''Mathematical Programming''. 1973. Vol. 4. hlm. 193–201. doi:10.1007/bf01584660. * K. I. M. McKinnon. ''Convergence of the Nelder–Mead simplex method to a non-stationary point''. ''SIAM Journal on Optimization''. 1999. Vol. 9. hlm. 148–158. doi:10.1137/S1052623496303482. (algorithm summary online).</ref> Perbaikan-perbaikan modern untuk heuristik Nelder-Mead telah ditemukan sejak tahun 1979.<ref>* Yu, Wen Ci. 1979. "Positive basis and a class of direct search techniques". ''Scientia Sinica'' [''Zhongguo Kexue'']: 53—68. * Yu, Wen Ci. 1979. "The convergent property of the simplex evolutionary technique". ''Scientia Sinica'' [''Zhongguo Kexue'']: 69–77. * Tamara G. Kolda. ''Optimization by direct search: new perspectives on some classical and modern methods''. ''SIAM Rev''. 2003. Vol. 45 (3). hlm. 385–482. doi:10.1137/S003614450242889. * Robert Michael Lewis. ''Implementing generating set search methods for linearly constrained minimization''. ''SIAM J. Sci. Comput''. 2007. Vol. 29 (6). hlm. 2507–2530. doi:10.1137/050635432.</ref>

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 <math>f(\mathbf x)</math>, dengan <math>\mathbf x \in \mathbb{R}^n</math>. Titik-titik uji saat ini adalah <math>\mathbf x_1, \ldots, \mathbf x_{n+1}</math>.

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

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

Beberapa tahap dapat dijelaskan secara intuitif sebagai berikut. Dalam tahap pencerminan, <math>\mathbf x_{n+1}</math> 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 <math>\mathbf x_o</math>) yang menghadap dirinya. Lalu pada tahap perluasan, jika titik <math>\mathbf x_r</math> menjadi minimum terbaik saat ini, kita dapat mengharapkan ada nilai yang lebih baik di antara titik <math>\mathbf x_o</math> dan <math>\mathbf x_r</math>. Di tahap penyempitan, jika <math>f(\mathbf x_r) > f(\mathbf x_n)</math>, 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:<blockquote>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.</blockquote>Akan tetapi, Nash menunjukkan implementasi pada aritmetika presisi-tetap dapat gagal untuk menyusutkan simpleks, sehingga sebuah uji tambahan untuk mengecek ukuran simpleks diperlukan.<ref>J. C. Nash. ''Compact Numerical Methods: Linear Algebra and Function Minimisation''. Adam Hilger. 1979. ISBN 978-0-85274-330-0.</ref>

=== 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 <math>\mathbf x_1,</math> dan titik pada setiap dimensi lainnya berjarak konstan dari <math>\mathbf x_1.</math> Alhasil cara ini sensitif terhadap penskalaan dari variabel-variabel yang menyusun <math>\mathbf x</math>.

== 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.<ref>J. C. Nash. ''Compact Numerical Methods: Linear Algebra and Function Minimisation''. Adam Hilger. 1979. ISBN 978-0-85274-330-0.</ref>

== Bacaan lebih lanjut ==
* 
* 
* 
* 
* 

== Pranala luar ==
* [http://www.brnt.eu/phd/node10.html#SECTION00622200000000000000 Nelder–Mead (Downhill Simplex) explanation and visualization with the Rosenbrock banana function]
* [http://people.sc.fsu.edu/~burkardt/m_src/asa047/nelmin.m John Burkardt: Nelder–Mead code in Matlab] - Variasi dari metode Nelder–Mead yang digunakan fungsi Matlab <code>fminsearch</code>.
* [https://docs.scipy.org/doc/scipy/reference/optimize.minimize-neldermead.html#optimize-minimize-neldermead Nelder-Mead optimization in Python in the SciPy library.]
* [https://github.com/fchollet/nelder-mead nelder-mead] - Implementasi bahasa Python metode Nelder–Mead
* [https://janert.me/blog/2023/nelder-mead-simplex-optimization/ NelderMead()] - Implementasi bahasa Go/Golang
* [http://people.fsv.cvut.cz/~svobodal/sova/ SOVA 1.0 (freeware)] - Simplex Optimization for Various Application

== Referensi ==
<references />

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Metode+Nelder-Mead&oldid=29570623 Wikipedia bahasa Indonesia], revisi 29570623 (2026-08-13T08:18:37Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

<!-- WIKI_UNISSULA_PRESENTATION_V4 -->