Optimisasi: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k +pic |
Fitur saranan suntingan: 2 pranala ditambahkan. |
||
| (37 revisi perantara oleh 23 pengguna tidak ditampilkan) | |||
Baris 1:
{{distinguish|Optimal}}
[[File:Max paraboloid.svg|right|thumb|Grafik yang dibentuk dari persamaan ''z'' = f(''x'', ''y'') = −(''x''² + ''y''²) + 4. Titik [[Maksimum dan minimum|maksimum]] global fungsi terletak pada (''x, y, z'') = (0, 0, 4), dtandai oleh titik berwarna biru.]]
[[File:Nelder-Mead Simionescu.gif|thumb|Visualisasi pencarian minimum [[Metode Nelder-Mead|Nelder-Mead]] untuk [[Fungsi untuk mengetes optimisasi|fungsi Siminescu]]. Verteks simplex diurutkan berdasarkan nilai mereka, dengan 1 menjadi nilai terkecil.|alt=]]
'''Optimisasi matematika''' (terkadang hanya ditulis sebagai '''optimisasi''') adalah proses memilih sebuah elemen terbaik, menurut suatu atau beberapa kriteria, dari suatu himpunan berisi alternatif elemen yang tersedia.<ref>"[http://glossary.computing.society.informs.org/index.php?page=nature.html The Nature of Mathematical Programming] {{webarchive|url=https://web.archive.org/web/20140305080324/http://glossary.computing.society.informs.org/index.php?page=nature.html |date=2014-03-05 }}," ''Mathematical Programming Glossary'', INFORMS Computing Society.</ref> Masalah optimisasi muncul dalam banyak bidang ilmu dari [[ilmu komputer]] dan [[Teknik|ilmu teknik]]<ref name="edo2021">{{Cite book|last1=Martins|first1=Joaquim R. R. A.|last2=Ning|first2=Andrew|date=2021-10-01|url=https://www.researchgate.net/publication/352413464_Engineering_Design_Optimization|title=Engineering Design Optimization|publisher=Cambridge University Press|isbn=978-1108833417|language=en}}</ref> sampai [[riset operasi]] dan [[ekonomi]], juga selama bertahun-tahun menarik perhatian [[matematika]] dalam mengembangkan metode menemukan solusi.<ref>{{cite book |last1=Du |first1=D. Z. |last2=Pardalos |first2=P. M. |last3=Wu |first3=W. |year=2008 |chapter=History of Optimization |editor-link=Christodoulos Floudas |editor-last=Floudas |editor-first=C. |editor2-last=Pardalos |editor2-first=P. |title=Encyclopedia of Optimization |publisher=Springer |location=Boston |pages=1538–1542 }}</ref>
Dalam kasus paling sederhana, sebuah [[masalah optimisasi]] berisi tentang cara [[Maksimum dan minimum|memaksimumkan atau meminimumkan]] nilai sebuah [[Fungsi (matematika)|fungsi real]], dengan secara sistematis memilih nilai [[Argumen sebuah fungsi|input]] dari suatu himpunan yang diperbolehkan. Perumuman dari teori-teori optimisasi dan teknik-teknik ke berbagai bentuk formulasi masalah menjadi bahan kajian sebagian besar bidang [[matematika terapan]].
== Masalah optimisasi ==
Sebuah masalah optimisasi dapat dinyatakan dalam bentuk sebagai berikut:
:''Diberikan:'' sebuah [[Fungsi (matematika)|fungsi]] <math>f: A\to \mathbb{R}</math> yang memetakan suatu [[Himpunan (matematika)|himpunan]] <math>A</math> ke [[Bilangan riil|bilangan real]]
:''Dicari:'' sebuah elemen <math>\mathbf{x}_0 \in A</math> yang memenuhi <math>f(\mathbf{x}_0) \leq f(\mathbf{x})</math> untuk setiap <math>\mathbf{x} \in A</math> (masalah minimisasi), atau yang memenuhi <math>f(\mathbf{x}_0) \geq f(\mathbf{x})</math> untuk setiap <math>\mathbf{x} \in A</math> (masalah maksimisasi)
Formulasi tersebut juga disebut dengan '''masalah pemrograman matematika'''. Terminologi ini yang tidak berhubungan langsung dengan [[Pemrograman Komputer|pemrograman komputer]], namun masih digunakan di beberapa hal seperti [[Program linear|pemrograman linear]]. Banyak masalah nyata (''real-world problem'') maupun masalah teoritis dapat dimodelkan dalam kerangka umum tersebut.
Perhatikan bahwa hubungan <math>f\left(\mathbf{x}_{0}\right)\geq f\left(\mathbf{x}\right) \Leftrightarrow \tilde{f}\left(\mathbf{x}_{0}\right)\leq \tilde{f}\left(\mathbf{x}\right)</math> terpenuhi jika kita mendefinisikan <math>\tilde{f}\left(\mathbf{x}\right) := - f\left(\mathbf{x}\right),\, \tilde{f}\, :\, A \rightarrow \mathbb{R}</math>. Hal ini yang mengartikan setiap masalah maksimisasi dapat diubah menjadi masalah minimisasi (dan sebaliknya). Dalam matematika, masalah optimisasi umumnya dinyatakan sebagai masalah minimisasi. Di bidang [[fisika]], formulasi seperti ini dapat merujuk pada teknik ''minimisasi [[energi]]'', dengan nilai fungsi <math>f</math> merepresentasikan energi dari [[sistem]] yang dimodelkan. Dalam [[pemelajaran mesin]], penting untuk mengevaluasi kualitas parameter data menggunakan [[Fungsi kerugian|fungsi biaya]], dengan nilai fungsi yang minimum mengimplikasikan kemungkinan parameter dengan nilai optimal (terkecil).
Umumnya <math>A</math> adalah [[Himpunan bagian|subset]] dari [[ruang Euklides]] <math>\mathbb{R}^n</math>, umum ditandai oleh sebuah himpunan [[Konstrain (matematika)|konstrain]], yakni kumpulan persamaan atau pertidaksamaan yang perlu dipenuhi oleh anggota <math>A</math>. Domain <math>A</math> dari fungsi <math>f</math> disebut dengan ''ruang pencarian'' atau ''ruang pilihan'', sedangkan elemen dari <math>A</math> disebut dengan ''kandidat solusi'' atau ''solusi feasibel'' (solusi yang mungkin).
Terdapat banyak nama bagi fungsi <math>f</math>, yang secara umum disebut dengan ''fungsi objektif''. Untuk masalah minimisasi, fungsi ini terkadang disebut dengan ''[[fungsi kerugian]]'' atau ''fungsi biaya'');<ref>W. Erwin Diewert (2008). "cost functions," ''The New Palgrave Dictionary of Economics'', 2nd Edition [http://www.dictionaryofeconomics.com/article?id=pde2008_C000390&edition=current&q= Contents].</ref> sedangkan masalah maksimisasi terkadang menggunakan terminologi ''fungsi kecocokan'' (fitness function) atau ''fungsi utilitas''. Pada beberapa bidang, fungsi ini juga disebut dengan ''fungsi energi''. Solusi feasibel yang meminimumkan (atau memaksimumkan jika itu tujuan akhirnya) nilai fungsi objektif dikenal sebagai ''solusi optimal''.
Sebuah [titik] ''minimum lokal'' <math>\mathbf{x}^*</math> didefinisikan sebagai elemen yang memiliki suatu <math>\delta > 0</math> dan untuk<math display="block">\forall\mathbf{x}\in A \; \text{dengan} \;\left\Vert\mathbf{x}-\mathbf{x}^{\ast}\right\Vert\leq\delta,\,</math>akan berlaku hubungan <math>f(\mathbf{x}^*) \leq f(\mathbf{x})</math>. Secara informal definisi ini mengatakan bahwa <math>\mathbf{x}^*</math> menghasilkan nilai fungsi yang terkecil, ketika dibandingkan tetangga-tetangga disekitarnya. [Titik] maksimum lokal didefinisikan dengan cara yang serupa. Jika titik minimum ''lokal'' memberikan solusi yang setidaknya sama baiknya dengan solusi disekitar titik tersebut, titik minimum ''global'' akan memberikan solusi yang setidaknya sama baiknya dengan semua solusi yang mungkin. Secara umum, kecuali fungsi objektif bersifat [[Fungsi konveks|konveks]], ada kemungkinan titik [minimum/maksimum] lokal, dan tidak semuanya juga merupakan titik [minimum/maksimum] global.
Banyak algoritma dikembangkan untuk menyelesaikan masalah non-konveks, namun sebagian besar tidak dapat membedakan solusi optimal lokal dengan solusi optimal global; mereka akan menganggap solusi optimal lokal sebagai solusi sebenarnya bagi masalah optimisasi. [[Optimisasi global]] adalah cabang [[matematika terapan]] dan [[analisis numerik]] yang mengkaji perkembangan algoritma [[Determinisme|deterministik]] dan memastikan konvergensi dalam waktu yang terbatas (''finite time''), untuk menemukan solusi optimal masalah non-konveks
== Notasi ==
Masalah optimisasi sering diekspresikan menggunakan notasi khusus. Berikut beberapa notasi yang digunakan berserta penjelasan singkatnya:
=== Nilai minimum dan maksimum sebuah fungsi ===
Perhatikan notasi berikut:<math display="block">\min_{x\in\mathbb R}\; \left(x^2 + 1\right)</math>Notasi ini menandakan nilai minimum dari fungsi objektif <math>x^2+1</math>, ketika <math>x</math> dipilih dari himpunan [[Bilangan riil|bilangan real]] <math>\mathbb{R}</math>. Nilai minimum dalam kasus ini adalah 1, dan terjadi ketika <math>x=0</math> .
Serupa dengan itu, notasi<math display="block">\max_{x\in\mathbb R}\; 2x</math>menandakan nilai maksimum dari fungsi objektif <math>2x</math>, dengan <math>x</math> dapat berupa sebarang bilangan real. Fungsi objektif ini tidak memiliki nilai maksimum, karena fungsi tidak terbatas (dari atas). Dalam kasus ini nilai maksimum adalah "[[tak hingga]]" atau "tidak terdefinisi", tergantung konteks pembicaraan.
=== Argumen input yang optimal ===
{{Main|Arg max}}
Notasi seperti<math display="block">\underset{x\in(-\infty,-1]}{\operatorname{arg\,min}} \; x^2 + 1,</math>atau secara ekuivalen juga dapat ditulis sebagai<math display="block">\underset{x}{\operatorname{arg\,min}} \; x^2 + 1, \; \text{dengan kendala:} \; x\in(-\infty,-1].</math>menandakan nilai (atau nilai-nilai jika ada lebih dari satu) [[Argumen sebuah fungsi|argumen]] <math>x</math> pada [[Selang (matematika)|selang]] <math>(-\infty, -1]</math> yang meminimumkan fungsi objektif <math>x^2+1</math>. Perlu diperhatikan notasi ini tidak merujuk pada nilai minimum dari fungsi, namun nilai argumen yang membuat nilai fungsi minimum. Dalam kasus ini, jawabannya adalah <math>x=-1</math>. Nilai <math>x=0</math> bukan solusi karena dia bukan anggota himpunan feasibel <math>x^2+1</math>.
Serupa dengan itu, notasi seperti
:<math>\underset{x\in[-5,5], \; y\in\mathbb R}{\operatorname{arg\,max}} \; x\cos y,</math>
atau juga dapat ditulis sebagai
:<math>\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos y, \; \text{dengan kendala:} \; x\in[-5,5], \; y\in\mathbb R,</math>
merepresentasikan semua himpunan berurut <math>\{x, y\}</math> yang memaksimumkan nilai fungsi objektif <math>x \cos y</math>, dengan batasan nilai <math>x</math> perlu terletak di selang <math>[-5,5]</math>. Dalam kasus ini, solusi dari notasi tersebut adalah semua himpunan berurut yang memiliki bentuk <math>\{5, 2k\pi\}</math> dan <math>\{-5, (2k+1)\pi\}</math>, dengan <math>k</math> merupakan [[bilangan bulat]].
Operators <math>\arg \min</math> dan <math>\arg \max</math> terkadang juga ditulis sebagai <math>\text{argmin}</math> dan <math>\text{argmax}</math>; secara berurutan memiliki arti "argumen dari minimum" dan "argumen dari maksimum".
== Sejarah ==
[[Pierre de Fermat|Fermat]] dan [[Joseph Louis Lagrange|Lagrange]] menemukan formula untuk mengidentifikasi nilai optimal, yang berdasar pada [[kalkulus]]. Sementara itu, [[Isaac Newton|Newton]] dan [[Carl Friedrich Gauss|Gauss]] mengusulkan metode iteratif yang mengubah nilai feasibel ke arah nilai optimal. [[George Dantzig|George B. Dantzig]] mencetuskan istilah "[[program linear|pemrograman linear]]" untuk menyelesaikan beberapa kasus optimisasi,walau sebagian teori sudah diperkenalkan oleh [[Leonid Kantorovich]] pada tahun 1939. Kata "pemrograman" dalam konteks ini tidak merujuk pada "[[Pemrograman|pemrogramam komputer]]", namun merujuk pada penggunaan ''program'' oleh pihak militer [[Amerika Serikat]] untuk menyebut proposal pelatihan dan jadwal; masalah-masalah yang dipelajari oleh Dantzig pada waktu itu. Pada tahun 1947, Dantzig mempublikasikan [[algoritma simplex]], sedangkan [[John von Neumann]] mengembangkan teori [[program linear|dualitas]].{{citation needed|date=January 2020}} Beberapa peneliti lain yang terkenal dalam bidang optimisasi adalah:{{Div col|colwidth=20em}}
* [[Richard Bellman]]
* [[Roger Fletcher (mathematician)|Roger Fletcher]]
* [[Ronald A. Howard]]
* [[Fritz John]]
* [[Narendra Karmarkar]]
* [[William Karush]]
* [[Leonid Khachiyan]]
* [[Bernard Koopman]]
* [[Harold Kuhn]]
* [[László Lovász]]
* [[Arkadi Nemirovski]]
* [[Yurii Nesterov]]
* [[Lev Pontryagin]]
* [[R. Tyrrell Rockafellar]]
* [[Naum Z. Shor]]
* [[Albert W. Tucker|Albert Tucker]]
{{div col end}}
== Referensi ==
{{Reflist}}
==Bacaan lebih lanjut==
* {{cite book |last1=Boyd |first1=Stephen P. |author-link=Stephen P. Boyd |first2=Lieven |last2=Vandenberghe |title=Convex Optimization |location=Cambridge |publisher=Cambridge University Press |year=2004 |isbn=0-521-83378-7 |url=https://web.stanford.edu/~boyd/cvxbook/ |ref=none}}
* {{cite book |first1=P. E. |last1=Gill |first2=W. |last2=Murray |first3=M. H. |last3=Wright |author-link3=Margaret H. Wright |year=1982 |title=Practical Optimization |publisher=Academic Press |location=London |isbn=0-12-283952-8 |ref=none}}
* {{cite book |last=Lee |first=Jon |author-link=Jon Lee (mathematician) |title=A First Course in Combinatorial Optimization |url=https://archive.org/details/firstcourseincom0000leej |publisher=Cambridge University Press |year=2004 |isbn=0-521-01012-8 |ref=none}}
* {{cite book | year=2006 |url=http://www.ece.northwestern.edu/~nocedal/book/num-opt.html |title=Numerical Optimization |edition=2nd |publisher=Springer |location=Berlin |isbn=0-387-30303-0 |first1=Jorge |last1=Nocedal |author-link=Jorge Nocedal |first2=Stephen J. |last2=Wright |ref=none}}
* {{cite book |last1=Snyman |first1=J. A. |last2=Wilke |first2=D. N. |title=Practical Mathematical Optimization : Basic Optimization Theory and Gradient-Based Algorithms |location=Berlin |publisher=Springer |edition=2nd |year=2018 |isbn=978-3-319-77585-2 |ref=none}}
==Pranala luar==
{{Commons category}}
* {{cite web |url=http://plato.asu.edu/guide.html |title=Decision Tree for Optimization Software }} Links to optimization source codes
* {{cite web |url=https://www.mat.univie.ac.at/~neum/glopt.html |title=Global optimization }}
* {{cite web |url=https://see.stanford.edu/Course/EE364A |title=EE364a: Convex Optimization I |work=Course from Stanford University }}
* {{cite web |title=Mathematical Optimization: Finding Minima of Functions |first=Gaël |last=Varoquaux |url=https://scipy-lectures.org/advanced/mathematical_optimization/index.html }}
{{authority control}}
{{Bidang matematika}}
[[Kategori:Riset operasi]]
[[Kategori:Optimisasi matematika]]
| |||