Optimisasi

**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. Masalah optimisasi muncul dalam banyak bidang ilmu dari ilmu komputer dan ilmu teknik sampai riset operasi dan ekonomi, juga selama bertahun-tahun menarik perhatian matematika dalam mengembangkan metode menemukan solusi.

Dalam kasus paling sederhana, sebuah masalah optimisasi berisi tentang cara memaksimumkan atau meminimumkan nilai sebuah fungsi real, dengan secara sistematis memilih nilai 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 f: A\to \mathbb{R} yang memetakan suatu himpunan A ke bilangan real
:*Dicari:* sebuah elemen \mathbf{x}_0 \in A yang memenuhi f(\mathbf{x}_0) \leq f(\mathbf{x}) untuk setiap \mathbf{x} \in A (masalah minimisasi), atau yang memenuhi f(\mathbf{x}_0) \geq f(\mathbf{x}) untuk setiap \mathbf{x} \in A (masalah maksimisasi)

Formulasi tersebut juga disebut dengan **masalah pemrograman matematika**. Terminologi ini yang tidak berhubungan langsung dengan pemrograman komputer, tetapi masih digunakan di beberapa hal seperti pemrograman linear. Banyak masalah nyata (*real-world problem*) maupun masalah teoretis dapat dimodelkan dalam kerangka umum tersebut.

Perhatikan bahwa hubungan 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) terpenuhi jika kita mendefinisikan \tilde{f}\left(\mathbf{x}\right) := - f\left(\mathbf{x}\right),\, \tilde{f}\, :\, A \rightarrow \mathbb{R}. 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 f merepresentasikan energi dari sistem yang dimodelkan. Dalam pemelajaran mesin, penting untuk mengevaluasi kualitas parameter data menggunakan fungsi biaya, dengan nilai fungsi yang minimum mengimplikasikan kemungkinan parameter dengan nilai optimal (terkecil).

Umumnya A adalah subset dari ruang Euklides \mathbb{R}^n, umum ditandai oleh sebuah himpunan konstrain, yakni kumpulan persamaan atau pertidaksamaan yang perlu dipenuhi oleh anggota A. Domain A dari fungsi f disebut dengan *ruang pencarian* atau *ruang pilihan*, sedangkan elemen dari A disebut dengan *kandidat solusi* atau *solusi feasibel* (solusi yang mungkin).

Terdapat banyak nama bagi fungsi f, yang secara umum disebut dengan *fungsi objektif*. Untuk masalah minimisasi, fungsi ini terkadang disebut dengan *[[fungsi kerugian]]* atau *fungsi biaya*); 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* \mathbf{x}^* didefinisikan sebagai elemen yang memiliki suatu \delta > 0 dan untuk\forall\mathbf{x}\in A \; \text{dengan} \;\left\Vert\mathbf{x}-\mathbf{x}^{\ast}\right\Vert\leq\delta,\,akan berlaku hubungan f(\mathbf{x}^*) \leq f(\mathbf{x}). Secara informal definisi ini mengatakan bahwa \mathbf{x}^* 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 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 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:\min_{x\in\mathbb R}\; \left(x^2 + 1\right)Notasi ini menandakan nilai minimum dari fungsi objektif x^2+1, ketika x dipilih dari himpunan bilangan real \mathbb{R}. Nilai minimum dalam kasus ini adalah 1, dan terjadi ketika x=0 .

Serupa dengan itu, notasi\max_{x\in\mathbb R}\; 2xmenandakan nilai maksimum dari fungsi objektif 2x, dengan x 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

Notasi seperti\underset{x\in(-\infty,-1]}{\operatorname{arg\,min}} \; x^2 + 1,atau secara ekuivalen juga dapat ditulis sebagai\underset{x}{\operatorname{arg\,min}} \; x^2 + 1, \; \text{dengan kendala:} \; x\in(-\infty,-1].menandakan nilai (atau nilai-nilai jika ada lebih dari satu) argumen x pada selang (-\infty, -1] yang meminimumkan fungsi objektif x^2+1. Perlu diperhatikan notasi ini tidak merujuk pada nilai minimum dari fungsi, tetapi nilai argumen yang membuat nilai fungsi minimum. Dalam kasus ini, jawabannya adalah x=-1. Nilai x=0 bukan solusi karena dia bukan anggota himpunan feasibel x^2+1.

Serupa dengan itu, notasi seperti
:\underset{x\in[-5,5], \; y\in\mathbb R}{\operatorname{arg\,max}} \; x\cos y,
atau juga dapat ditulis sebagai
:\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos y, \; \text{dengan kendala:} \; x\in[-5,5], \; y\in\mathbb R,

merepresentasikan semua himpunan berurut \{x, y\} yang memaksimumkan nilai fungsi objektif x \cos y, dengan batasan nilai x perlu terletak di selang [-5,5]. Dalam kasus ini, solusi dari notasi tersebut adalah semua himpunan berurut yang memiliki bentuk \{5, 2k\pi\} dan \{-5, (2k+1)\pi\}, dengan k merupakan bilangan bulat.

Operators \arg \min dan \arg \max terkadang juga ditulis sebagai \text{argmin} dan \text{argmax}; secara berurutan memiliki arti "argumen dari minimum" dan "argumen dari maksimum".

## Sejarah
Fermat dan Lagrange menemukan formula untuk mengidentifikasi nilai optimal, yang berdasar pada kalkulus. Sementara itu, Newton dan Gauss mengusulkan metode iteratif yang mengubah nilai feasibel ke arah nilai optimal. George B. Dantzig mencetuskan istilah "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 "pemrogramam komputer", tetapi 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 memublikasikan algoritma simplex, sedangkan John von Neumann mengembangkan teori dualitas. Beberapa peneliti lain yang terkenal dalam bidang optimisasi adalah:
* Richard Bellman
* 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 Tucker

## Referensi

## Bacaan lebih lanjut
* 
* 
* 
* 
* 

## Pranala luar

*  Links to optimization source codes
* 
* 
*