Skip to content
Kembali ke hasil pencarian

Optimasi Konveks

Diperkenalkan oleh
Stephen Boyd & Lieven Vandenberghe
Tahun
2004
Jenis
Mathematical optimization framework
Keluarga
Mathematical programming

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Optimasi konveks adalah subbidang optimasi matematis yang mempelajari masalah minimisasi fungsi konveks pada himpunan konveks.

Diformalisasi dan dipopulerkan oleh Stephen Boyd dan Lieven Vandenberghe dalam buku teks mereka yang monumental tahun 2004, kerangka kerja ini menyatukan berbagai macam masalah — termasuk pemrograman linear, pemrograman kuadratik, pemrograman semidefinit, dan pemrograman kerucut orde kedua — di bawah satu payung teoretis. Sifat penentunya adalah bahwa setiap solusi optimal lokal juga merupakan solusi optimal global, membuatnya dapat dikelola dan andal untuk rekayasa, statistik, pembelajaran mesin, dan riset operasi.

Intuisi di balik metode

Bayangkan lembah berbentuk mangkuk: di mana pun Anda mulai menggelindingkan bola, bola itu akan selalu berakhir di titik terendah yang sama. Optimasi konveks memformalkan geometri ini secara matematis. Fungsi tujuan adalah mangkuk, daerah layak adalah medan berbentuk konveks, dan algoritma adalah bola yang mengikuti lereng. Karena tidak ada lekukan lokal tersembunyi atau punggungan yang menipu, Anda dijamin menemukan minimum global yang sebenarnya — menjadikan pendekatan ini secara fundamental berbeda dari dan lebih andal daripada optimasi nonlinier umum.

Sejarah

Dasar-dasar teoretis analisis konveks berasal dari karya Minkowski dan Farkas pada awal abad kedua puluh, dengan pemrograman linear muncul pada tahun 1940-an melalui Dantzig. Metode titik interior, yang diperkenalkan oleh Karmarkar pada tahun 1984 dan disempurnakan sepanjang tahun 1990-an, membuat program konveks umum dapat dikelola secara komputasi. Buku teks Cambridge University Press tahun 2004 oleh Boyd dan Vandenberghe, yang tersedia gratis secara online, menyintesis dekade hasil menjadi kerangka kerja yang koheren dan dapat diakses serta memunculkan paradigma pemrograman konveks yang disiplin yang diimplementasikan dalam CVX, CVXPY, dan alat terkait.

Kapan digunakan

Gunakan optimasi konveks ketika tujuan dan semua kendala dapat diekspresikan atau diformulasikan ulang sebagai fungsi konveks. Ini sesuai untuk optimasi portofolio, regresi dengan regularisasi, aliran jaringan, mesin vektor pendukung, dan desain kontrol. Asumsi utama adalah konveksitas himpunan layak dan tujuan; melanggar ini menghilangkan jaminan optimalitas global. Ketika masalahnya non-konveks, pertimbangkan relaksasi konveks atau pemecah nonlinier lokal. Pilih pemecah pemrograman linear ketika masalahnya linear untuk efisiensi tambahan.

Batasan dan pertimbangan

  • Aplikasi bergantung sepenuhnya pada apakah masalah dapat diformulasikan atau didekati dalam bentuk konveks; banyak masalah dunia nyata secara inheren non-konveks.
  • Metode titik interior menyimpan dan memfaktorkan matriks besar, membuat kebutuhan memori dan waktu menjadi substansial untuk masalah berdimensi sangat tinggi.
  • Relaksasi konveks dari masalah kombinatorial atau integer dapat menghasilkan solusi fraksional yang tidak dapat ditindaklanjuti secara langsung tanpa heuristik pembulatan.
  • Pemodelan masalah membutuhkan keahlian: pernyataan konveksitas yang salah secara diam-diam menghilangkan jaminan teoretis sementara pemecah tetap memberikan jawaban.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Menjamin solusi optimal global kapan pun formulasi konveks dapat dicapai — tidak ada risiko konvergensi ke minimum lokal.
  • Dapat diselesaikan dalam waktu polinomial melalui metode titik interior, memberikan efisiensi praktis bahkan untuk masalah skala besar.
  • Teori dualitas menghasilkan sertifikat optimalitas, variabel dual dengan interpretasi ekonomi, dan analisis sensitivitas tanpa biaya tambahan.
  • Aturan komposisi yang kaya (DCP) memungkinkan verifikasi konveksitas yang sistematis dan transformasi otomatis ke dalam bentuk yang siap untuk pemecah.

Penerapan

  • Optimasi portofolio: meminimalkan varians atau CVaR dengan tunduk pada target pengembalian dan kendala alokasi dalam keuangan kuantitatif.
  • Pembelajaran mesin: melatih mesin vektor pendukung, regresi lasso dan ridge, serta regresi logistik adalah program konveks kanonik.
  • Pemrosesan sinyal dan gambar: kompresi terukur (compressed sensing), denoising variasi total, dan pemulihan jarang diformulasikan sebagai program konveks.
  • Alokasi jaringan dan sumber daya: perutean optimal, kontrol daya dalam jaringan nirkabel, dan alokasi bandwidth di bawah kendala kapasitas.
  • Sistem kontrol: sintesis pengontrol H-infinit berdasarkan pemrograman semidefinit dan verifikasi stabilitas Lyapunov.

Cara kerjanya

Cara kerjanya

1

Analis memformulasikan masalah keputusan sebagai program konveks standar: minimalkan fungsi tujuan konveks f0(x) dengan tunduk pada kendala ketidaksamaan konveks fi(x) ≤ 0 dan kendala kesamaan afin Ax = b. Mendapatkan formulasi yang tepat — memilih representasi variabel yang benar dan mengekspresikan semua kendala dalam bentuk konveks — adalah langkah pertama yang kritis yang menentukan apakah jaminan kuat berlaku.

Rumus
\min_{x \in \mathcal{C}} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0,\; i=1,\ldots,m,\; Ax = b
2

Sebelum menyelesaikan, setiap fungsi dalam masalah diverifikasi sebagai konveks, yang berarti epigrafnya adalah himpunan konveks atau, secara ekuivalen, memenuhi ketidaksamaan titik tengah. Aturan pemrograman konveks yang disiplin (DCP) dari Boyd dan Vandenberghe menyediakan cara sistematis untuk mengkonfirmasi konveksitas melalui aturan komposisi, sehingga analis tidak perlu membuktikan konveksitas dari awal untuk setiap masalah.

Rumus
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \quad \forall x,y \in \text{dom}\,f,\; \theta \in [0,1]
3

Lagrangian L(x, λ, ν) dibentuk dengan merelaksasi kendala menggunakan pengali dual. Di bawah kualifikasi kendala Slater, dualitas kuat berlaku: optimum primal dan dual bertepatan dan kondisi KKT — stasioneritas, kelayakan primal/dual, dan slackness komplementer — adalah syarat perlu dan cukup untuk optimalitas global. Dualitas juga menghasilkan sertifikat optimalitas dan informasi sensitivitas tentang bagaimana optimum berubah seiring data masalah.

Rumus
L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^T(Ax-b), \quad \lambda_i \geq 0
4

Metode titik interior, varian penurunan gradien, atau algoritma proksimal secara iteratif bergerak melalui himpunan layak menuju optimum. Untuk masalah mulus tanpa kendala, langkah gradien dengan ukuran langkah yang sesuai konvergen pada laju yang diketahui. Untuk masalah yang terkendala atau terstruktur, metode titik interior mencapai konvergensi waktu polinomial dengan presisi tinggi, dan metode orde pertama seperti ADMM diskalakan ke instansi yang sangat besar.

Rumus
x^{(k+1)} = x^{(k)} - t_k \nabla f_0(x^{(k)}), \quad t_k > 0

Kesalahan umum

  • Menganggap suatu masalah konveks tanpa verifikasi formal — aturan komposisi harus diperiksa secara ketat, bukan dengan inspeksi visual tujuan.
  • Mengabaikan kondisi numerik: masalah yang diskalakan dengan buruk menyebabkan pemecah melaporkan solusi yang tidak akurat atau tidak layak meskipun secara teoretis layak.
  • Mengabaikan celah dualitas dalam pemecah non-standar atau pengaturan di mana kondisi Slater gagal, yang dapat membatalkan klaim optimalitas berbasis KKT.
  • Memperlakukan solusi relaksasi konveks sebagai solusi masalah asli ketika kendala integer atau kombinatorial dihilangkan selama reformulasi.

Pertanyaan yang sering diajukan

Bagaimana saya tahu apakah masalah saya konveks?

Periksa apakah fungsi tujuan dan setiap fungsi kendala memenuhi ketidaksamaan konveksitas titik tengah, atau verifikasi konveksitas menggunakan aturan pemrograman konveks yang disiplin. Jika setiap fungsi dibangun dari primitif konveks yang diketahui yang digabungkan sesuai dengan aturan komposisi yang mempertahankan konveksitas (fungsi luar konveks non-menurun, fungsi dalam konveks, dll.), masalahnya adalah konveks. Bab 3 buku Boyd dan Vandenberghe menyediakan katalog ekstensif fungsi konveks.

Apa perbedaan antara optimasi konveks dan pemrograman linear?

Pemrograman linear adalah kasus khusus dari optimasi konveks di mana baik tujuan maupun semua kendala adalah fungsi afin (linear). Optimasi konveks jauh lebih umum, mencakup program kuadratik, kerucut orde kedua, dan semidefinit. Sementara metode simpleks dan titik interior menyelesaikan program linear, hanya metode titik interior yang meluas langsung ke kelas konveks penuh.

Bisakah optimasi konveks menangani variabel integer atau biner?

Tidak secara langsung — kendala integer membuat masalah menjadi sulit secara kombinatorial dan umumnya non-konveks. Pendekatan umum adalah menyelesaikan relaksasi konveks (menghilangkan integralitas) untuk mendapatkan batas bawah, kemudian menerapkan branch-and-bound atau pembulatan. Pemecah pemrograman campuran integer konveks menggabungkan ide-ide ini, tetapi jaminan optimalitas global dari optimasi konveks murni tidak lagi berlaku dalam keumuman penuh.

Metode terkait

Sumber

  1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

    ISBN: 978-0-521-83378-3
    Disalin.