Optimisasi Cembung — Konsep, Metode & Aplikasi

Optimisasi cembung berarti meminimalkan fungsi cembung pada himpunan feasible yang cembung. Alasan utama mengapa ini penting sederhana: jika syarat kecembungan itu terpenuhi, setiap minimum lokal juga merupakan minimum global.

Jaminan itu membuat masalah-masalah ini jauh lebih andal daripada masalah optimisasi umum. Anda tetap harus memodelkan masalah dengan benar, tetapi setelah modelnya cembung, Anda tidak sedang mengejar solusi yang hanya tampak terbaik di lingkungan kecil.

Bentuk yang umum adalah

$$\text{minimize } f(x)$$

dengan syarat

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

di mana $f$ dan setiap $g_i$ bersifat cembung, dan kendala persamaan bersifat afin. Dalam kondisi tersebut, himpunan feasible bersifat cembung dan masalah optimisasinya adalah optimisasi cembung.

Definisi Optimisasi Cembung

Suatu fungsi $f$ disebut cembung jika, untuk sembarang dua titik $x$ dan $y$ dalam domainnya dan sembarang $0 \le t \le 1$,

$$f(tx + (1-t)y) \le t f(x) + (1-t) f(y).$$

Dalam bahasa sederhana, ruas garis yang menghubungkan dua titik pada grafik berada di atas grafik itu sendiri. Dalam satu variabel, banyak fungsi cembung tampak seperti mangkuk, tetapi pertidaksamaan itulah uji yang sebenarnya.

Suatu himpunan disebut cembung jika, setiap kali himpunan itu memuat dua titik, himpunan itu juga memuat setiap titik pada ruas garis lurus di antara keduanya.

Anda memerlukan kedua bagian ini:

• fungsi objektif yang cembung
• himpunan feasible yang cembung

Jika salah satu bagian gagal, masalahnya mungkin tidak lagi cembung.

Mengapa Optimisasi Cembung Lebih Mudah Dianalisis

Optimisasi sering kali sulit karena bisa ada banyak lembah. Sebuah algoritme dapat terus memperbaiki nilai objektif tetapi tetap berhenti di titik yang hanya terbaik secara lokal.

Optimisasi cembung menghilangkan mode kegagalan khusus itu. Jika objektif cembung dan daerah feasible cembung, maka titik yang tidak bisa diperbaiki lagi secara lokal sudah pasti optimal secara global. Itulah sebabnya masalah cembung penting dalam statistika, machine learning, kontrol, dan riset operasi.

Ini tidak berarti setiap masalah cembung itu mudah. Beberapa tetap besar atau mahal secara komputasi. Artinya, strukturnya cukup bersih sehingga algoritme yang baik dapat menargetkan optimum sejati alih-alih terjebak oleh perilaku lokal yang menyesatkan.

Contoh Optimisasi Cembung yang Dikerjakan

Perhatikan masalah tak berkendala

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

Ini adalah masalah optimisasi cembung karena $f(x)$ adalah fungsi kuadrat dengan koefisien utama positif, sehingga cembung pada semua bilangan real.

Untuk mencari peminimumnya, turunkan:

$$f'(x) = 2(x-3).$$

Samakan turunan dengan nol:

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

Sekarang hitung nilai objektifnya:

$$f(3) = (3-3)^2 + 2 = 2.$$

Jadi nilai minimumnya adalah $2$, dicapai pada $x=3$.

Contoh ini sederhana, tetapi menunjukkan gagasan utamanya. Setelah Anda mencapai $x=3$, tidak ada lembah yang lebih rendah dan tersembunyi di tempat lain.

Metode Umum untuk Optimisasi Cembung

Metodenya bergantung pada struktur masalah.

Untuk masalah mulus yang tak berkendala atau berkendala sederhana, metode berbasis gradien umum digunakan karena bergerak berlawanan arah gradien dapat menurunkan nilai objektif.

Untuk banyak masalah cembung berkendala, metode interior-point banyak digunakan karena menangani kendala secara langsung dan sering bekerja baik dalam praktik.

Untuk masalah cembung tak mulus, metode subgradien atau proksimal mungkin lebih sesuai. Gagasan pentingnya bukan daftar algoritmenya. Yang penting adalah jaminan bahwa struktur cembung memberi algoritme-algoritme itu sesuatu yang stabil untuk dikerjakan.

Kesalahan Umum dalam Optimisasi Cembung

Menganggap Plot Membuktikan Kecembungan

Sebuah grafik bisa tampak seperti mangkuk pada satu plot tetapi tetap gagal memenuhi kecembungan pada seluruh domain atau pada dimensi yang lebih tinggi. Definisi atau aturan kecembungan standar lebih penting daripada sekadar sketsa.

Lupa Bahwa Kendala Itu Penting

Objektif cembung saja tidak cukup. Jika himpunan feasible tidak cembung, maka keseluruhan masalah bukanlah masalah optimisasi cembung.

Menganggap Setiap Titik Kritis Sebagai Minimum

Untuk fungsi cembung yang terdiferensialkan, titik dengan gradien nol adalah peminimum global. Tanpa kecembungan, kesimpulan itu umumnya tidak berlaku.

Mencampuradukkan Cembung dengan Cembung Ketat

Cembung ketat lebih kuat. Sifat ini sering memberikan peminimum yang unik, sedangkan kecembungan biasa tidak selalu menjamin keunikan.

Di Mana Optimisasi Cembung Digunakan

Optimisasi cembung muncul setiap kali masalah nyata dapat dimodelkan dengan biaya cembung dan kendala cembung.

Contoh umum meliputi fitting least-squares, support vector machines, pemilihan portofolio di bawah model risiko cembung, dan banyak masalah alokasi sumber daya. Model yang tepat tetap penting: suatu aplikasi hanya cembung jika objektif dan kendala yang dipilih benar-benar memenuhi asumsi kecembungan.

Kapan Kecembungan Membantu dalam Praktik

Optimisasi cembung sangat berguna ketika Anda membutuhkan lebih dari sekadar sebuah angka. Sering kali Anda menginginkan jaminan bahwa jawabannya benar-benar optimal untuk model yang Anda tuliskan.

Jaminan itu penting dalam rekayasa dan pekerjaan data karena memisahkan dua pertanyaan:

1. Apakah kita menyelesaikan masalah matematikanya dengan benar?
2. Apakah masalah matematika itu merupakan model yang baik untuk kenyataan?

Kecembungan sangat membantu untuk pertanyaan pertama. Namun, kecembungan tidak otomatis menyelesaikan pertanyaan kedua.

Coba Masalah Serupa

Ambil $f(x) = (x+1)^2 + 5$ dan cari nilai minimumnya. Lalu bandingkan dengan $f(x) = -(x+1)^2 + 5$, yang cekung, bukan cembung. Perbandingan berdampingan itu membuat peran kecembungan jauh lebih mudah dilihat.

Jika Anda ingin mengeksplorasi kasus lain, cobalah menyusun masalah least-squares kecil dan lihat bagaimana meminimalkan fungsi galat cembung menghasilkan pencocokan terbaik yang stabil.