Optimasi Cembung

📚 Ringkasan Konten

Kursus tingkat pascasarjana yang komprehensif dan buku teks yang membahas teori, aplikasi, serta algoritma numerik optimisasi cembung. Fokus utama adalah mengenali dan merumuskan masalah cembung dalam rekayasa dan sains.

Kelola dasar matematis dan algoritma praktis optimisasi cembung untuk rekayasa dan ilmu data.

Penulis: Stephen Boyd, Lieven Vandenberghe

Ucapan Terima Kasih: Didukung sebagian oleh NSF, serta melalui kontribusi dari mahasiswa dan rekan di Stanford dan UCLA, termasuk penghargaan khusus kepada Arkadi Nemirovski dan Kishan Baheti.

🎯 Tujuan Pembelajaran

1. Mendefinisikan komponen masalah optimisasi matematis, termasuk fungsi tujuan, kendala, dan variabel.
2. Membedakan antara masalah kuadrat terkecil, pemrograman linear, dan optimisasi cembung berdasarkan sifat matematisnya.
3. Membandingkan strategi optimisasi lokal dan global serta mengevaluasi kompleksitas komputasi yang terkait dengan masing-masing.
4. Mendefinisikan dan membedakan antara himpunan afine, himpunan cembung, dan kerucut menggunakan notasi kombinasi formal.
5. Mengidentifikasi dan merepresentasikan himpunan cembung standar seperti bola Euklides, elipsoida, polihedra, dan kerucut semi-positif-definit.
6. Menerapkan operasi yang mempertahankan sifat cembung, seperti irisan, transformasi afine, dan fungsi perspektif, untuk memverifikasi sifat himpunan.
7. Mengidentifikasi dan menerapkan operasi yang mempertahankan sifat cembung, termasuk supremum titik-titik dari fungsi afine dan aturan komposisi vektor.
8. Menurunkan konjugat Lagrange dari berbagai fungsi dan menerapkan ketidaksamaan Young.
9. Karakterisasi kemonotonan (quasiconvexity) menggunakan himpunan sublevel dan kondisi diferensial orde pertama/kedua.
10. Merumuskan dan Mengubah: Mengkonversi masalah optimisasi mentah menjadi bentuk standar cembung menggunakan variabel slack dan eliminasi kendala.

🔹 Pelajaran 1: Pengantar Optimisasi Matematis

Gambaran Umum: Pelajaran ini memperkenalkan konsep dasar optimisasi matematis, beralih dari formulasi umum ke kelas-kelas spesifik yang dapat diselesaikan seperti kuadrat terkecil dan pemrograman linear. Fokus diberikan pada perbedaan kritis antara optimisasi cembung dan non-cembung, menjelaskan bagaimana metode cembung berfungsi sebagai "tonggak" andalan untuk efisiensi dan menyediakan alat penting untuk menangani masalah nonlinear yang lebih sulit.

Hasil Pembelajaran:

• Mendefinisikan komponen masalah optimisasi matematis, termasuk fungsi tujuan, kendala, dan variabel.
• Membedakan antara masalah kuadrat terkecil, pemrograman linear, dan optimisasi cembung berdasarkan sifat matematisnya.
• Membandingkan strategi optimisasi lokal dan global serta mengevaluasi kompleksitas komputasi yang terkait dengan masing-masing.

🔹 Pelajaran 2: Teori Himpunan Cembung

Gambaran Umum: Pelajaran ini mengeksplorasi geometri dasar optimisasi, beralih dari struktur linear dasar ke sifat-sifat kompleks himpunan cembung dan kerucut. Meliputi definisi matematis himpunan afine dan cembung, menelaah geometri tertentu seperti polihedra dan kerucut semi-positif-definit, serta menjelaskan operasi dan teorema yang memungkinkan peneliti untuk mengkarakterisasi dan memanipulasi himpunan cembung dalam ruang dimensi tinggi.

Hasil Pembelajaran:

• Mendefinisikan dan membedakan antara himpunan afine, himpunan cembung, dan kerucut menggunakan notasi kombinasi formal.
• Mengidentifikasi dan merepresentasikan himpunan cembung standar seperti bola Euklides, elipsoida, polihedra, dan kerucut semi-positif-definit.
• Menerapkan operasi yang mempertahankan sifat cembung, seperti irisan, transformasi afine, dan fungsi perspektif, untuk memverifikasi sifat himpunan.

🔹 Pelajaran 3: Fungsi Cembung dan Sifat-Sifatnya

Gambaran Umum: Pelajaran ini mengeksplorasi operasi lanjutan yang mempertahankan sifat cembung, seperti supremum titik-titik dan aturan komposisi khusus, serta memperkenalkan fungsi konjugat Lagrange. Memperluas konsep cembung ke fungsi quasiconvex dan log-konkaf, sambil juga meninjau konveksitas terhadap ketidaksamaan umum dan sifat matriks khusus seperti komplement Schur. Konsep-konsep ini membentuk dasar matematis untuk mengidentifikasi dan merumuskan masalah optimisasi kompleks.

Hasil Pembelajaran:

• Mengidentifikasi dan menerapkan operasi yang mempertahankan sifat cembung, termasuk supremum titik-titik dari fungsi afine dan aturan komposisi vektor.
• Menurunkan konjugat Lagrange dari berbagai fungsi dan menerapkan ketidaksamaan Young.
• Karakterisasi kemonotonan (quasiconvexity) menggunakan himpunan sublevel dan kondisi diferensial orde pertama/kedua.

🔹 Pelajaran 4: Pemformulasian Masalah Optimisasi Cembung

Gambaran Umum: Pelajaran ini membahas struktur formal dan transformasi masalah optimisasi cembung, mulai dari bentuk standar dan kondisi optimalitas hingga kelas-kelas spesifik seperti Pemrograman Linear (LP), Kuadratik (QP), dan Pemrograman Semidefinite (SDP). Mahasiswa akan belajar cara mengidentifikasi optimalitas global, menggunakan metode biseksi untuk masalah quasiconvex, dan menerapkan scalarization pada optimisasi vektor multi-kriteria.

Hasil Pembelajaran:

• Merumuskan dan Mengubah: Mengkonversi masalah optimisasi mentah menjadi bentuk cembung standar menggunakan variabel slack dan eliminasi kendala.
• Analisis Optimalitas: Menerapkan kriteria optimalitas berbasis gradien untuk menentukan apakah suatu titik bersifat optimal secara global.
• Klasifikasi dan Menyelesaikan: Membedakan antara LP, QP, SOCP, GP, dan SDP, serta menerapkan metode khusus seperti Metode Biseksi untuk fungsi quasiconvex.

🔹 Pelajaran 5: Dualitas Lagrange dan Kondisi KKT

Gambaran Umum: Pelajaran ini mengeksplorasi teori dasar dualitas Lagrange, beralih dari definisi fungsi dual Lagrange hingga formulasi masalah dual. Meliputi celah kritis antara nilai optimal primal dan dual, interpretasi geometris dan teoretis permainan terhadap hubungan ini, serta kondisi Karush-Kuhn-Tucker (KKT) yang mencirikan solusi optimal. Akhirnya, pelajaran ini diperluas ke analisis sensitivitas dan harga bayangan (shadow prices).

Hasil Pembelajaran:

• Menurunkan fungsi dual Lagrange dan merumuskan masalah dual untuk berbagai masalah optimisasi.
• Mengevaluasi hubungan antara masalah primal dan dual menggunakan dualitas lemah/kuat serta kualifikasi kendala Slater.
• Menerapkan kondisi optimalitas KKT untuk menyelesaikan dan memverifikasi solusi optimal pada masalah cembung maupun non-cembung.

🔹 Pelajaran 6: Aproksimasi, Penyesuaian, dan Regularisasi

Gambaran Umum: Pelajaran ini mengeksplorasi fondasi matematis dan aplikasi praktis dari pendekatan penyelesaian sistem persamaan linear dan penyesuaian fungsi terhadap data. Meliputi aproksimasi berbasis norma termasuk fungsi hukuman dan regularisasi untuk mengelola outlier dan densitas rendah, serta teknik optimisasi robust untuk menangani ketidakpastian data. Selain itu, pelajaran ini menjelaskan penyesuaian fungsi di bawah kendala tertentu seperti konveksitas dan monotonitas.

Hasil Pembelajaran:

• Merumuskan dan menyelesaikan masalah aproksimasi norma, serta menafsirkan perbedaan geometris dan statistik antara pendekatan Kuadrat Terkecil, Chebyshev, dan L1.
• Merancang dan menerapkan model aproksimasi terregularisasi untuk mencapai kompromi antara kesalahan residu, besar solusi, dan densitas.
• Membangun kerangka aproksimasi robust untuk mempertimbangkan ketidakpastian dalam matriks data.

🔹 Pelajaran 7: Estimasi dan Inferensi Statistik

Gambaran Umum: Pelajaran ini mengeksplorasi interseksi antara inferensi statistik dan optimisasi cembung. Fokus pada perumusan masalah estimasi—termasuk maksimum likelihood, estimasi distribusi nonparametrik, dan desain detektor optimal—asal dari program cembung. Mahasiswa akan belajar menggunakan optimisasi untuk menemukan parameter dan merancang eksperimen informatif.

Hasil Pembelajaran:

• Merumuskan dan menyelesaikan masalah Estimasi Maksimum Likelihood (MLE) dan Regresi Logistik sebagai tugas optimisasi cembung.
• Merancang detektor optimal menggunakan Pemrograman Linear (LP) dan menafsirkan Karakteristik Operasi Penerima (ROC).
• Menerapkan teknik estimasi nonparametrik, termasuk Entropi Maksimum dan minimisasi divergensi Kullback-Leibler.

🔹 Pelajaran 8: Masalah Geometri dan Klasifikasi

Gambaran Umum: Pelajaran ini mengeksplorasi penerapan optimisasi cembung pada masalah geometri, termasuk proyeksi titik ke himpunan, perhitungan jarak antar himpunan, dan karakterisasi pusat himpunan. Lebih lanjut, prinsip-prinsip geometri ini diperluas ke tugas dunia nyata seperti klasifikasi linear dan non-linear, penempatan fasilitas optimal, serta perencanaan lantai menggunakan pemrograman geometri.

Hasil Pembelajaran:

• Merumuskan dan menyelesaikan masalah proyeksi dan jarak antar himpunan cembung menggunakan kondisi KKT dan representasi dual.
• Mengaproksimasi himpunan cembung kompleks menggunakan elipsoida volume ekstremal dan mengidentifikasi faktor efisiensinya.
• Menghitung berbagai pusat himpunan dan menerapkannya untuk diskriminasi dan klasifikasi yang robust.

🔹 Pelajaran 9: Algoritma Minimisasi Tak Terbatas

Gambaran Umum: Pelajaran ini membahas dasar teoretis dan implementasi algoritmik minimisasi tak terbatas untuk fungsi cembung. Menjabarkan metode turunan dari metode Gradien Turunan Pertama hingga Metode Newton Turunan Kedua. Sebagian besar waktu difokuskan pada analisis konvergensi, dengan penekanan pada konveksitas kuat dan teori invariant afine dari self-concordance.

Hasil Pembelajaran:

• Mendefinisikan konveksitas kuat dan memanfaatkan implikasinya untuk memberikan batas atas pada suboptimalitas dan jarak ke titik optimal.
• Membandingkan dan membedakan Gradien Turunan dengan Turunan Tercuram di bawah norma Euclidean, Kuadratik, dan L1.
• Menghitung langkah Newton dan dekrement Newton, menjelaskan mengapa metode Newton bersifat invariant afine.

🔹 Pelajaran 10: Minimisasi dengan Kendala Kesamaan

Gambaran Umum: Pelajaran ini mengeksplorasi metode untuk menyelesaikan masalah optimisasi cembung dengan kendala kesamaan linear. Fokus pada derivasi dan implementasi langkah Newton, membandingkan metode start layak dan tidak layak, serta menafsirkan langkah-langkah ini dalam kerangka primal-dual. Penekanan khusus diberikan pada implementasi numerik yang efisien melalui eliminasi blok sistem KKT.

Hasil Pembelajaran:

• Menghitung dan menafsirkan langkah Newton dan dekrement untuk masalah dengan kendala kesamaan.
• Menunjukkan ekuivalensi antara metode Newton dengan kendala kesamaan dan eliminasi kendala tersebut.
• Menerapkan metode Newton Start Tidak Layak dan menjelaskan sifat pengurangan residu primal-dualnya.

🔹 Pelajaran 11: Metode Titik Dalam

Gambaran Umum: Pelajaran ini membahas metode titik dalam, yang menyelesaikan masalah optimisasi cembung dengan kendala ketidaksamaan dengan menerapkan metode Newton pada rangkaian masalah kesamaan. Inti pembahasan meliputi fungsi barrier logaritmik, menelusuri lintasan pusat menuju solusi optimal, serta memanfaatkan kerangka primal-dual untuk meningkatkan efisiensi dan ketahanan.

Hasil Pembelajaran:

• Mendefinisikan dan membuat fungsi barrier logaritmik serta mengkarakterisasi lintasan pusat dan titik dual terkait.
• Menerapkan metode barrier, termasuk kompromi antara langkah pusat dan iterasi luar.
• Merumuskan dan menyelesaikan masalah fase I kelayakan untuk menemukan titik awal yang secara ketat layak.