Optimisasi Robust — Pemrograman Matematis Kasus Terburuk
- Diperkenalkan oleh
- Ben-Tal, El Ghaoui & Nemirovski (seminal book, 2009); Bertsimas & Sim (tractable polyhedral formulation, 2004)
- Tahun
- 1970s theoretical roots; modern tractable form from late 1990s–2004
- Jenis
- Mathematical programming framework
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Optimisasi robust adalah kerangka kerja pemrograman matematis, yang diformalkan oleh Ben-Tal dan Nemirovski pada akhir 1990-an dan dibuat dapat ditangani secara luas oleh Bertsimas dan Sim (2004), yang menemukan keputusan yang dijamin berkinerja dapat diterima di bawah setiap skenario dalam himpunan ketidakpastian yang telah ditentukan sebelumnya — daripada mengasumsikan nilai parameter diketahui secara pasti.
Alih-alih mengoptimalkan untuk satu hasil yang diharapkan, ia meminimalkan tujuan kasus terburuk di semua realisasi data yang tidak pasti yang masuk akal.
Intuisi di balik metode
Optimisasi biasa mempercayai angka yang Anda berikan. Optimisasi robust bertanya: bagaimana jika angka-angka itu salah — dalam rentang terbatas tertentu? Ia menemukan keputusan yang paling sedikit merugikan ketika alam memilih masukan terburuk yang mungkin di dalam rentang itu. Anggap saja seperti merancang jembatan untuk menahan bukan beban rata-rata tetapi beban terberat yang masuk akal, menerima sedikit penurunan kinerja dalam kasus biasa sebagai ganti jaminan dalam kasus buruk.
Sejarah
Akar teoretis optimisasi robust dapat ditelusuri ke Soyster (1971) dan teori keputusan minimax Wald (1945). Bidang ini diberi landasan modern yang dapat ditangani oleh Arkadi Nemirovski dan Aharon Ben-Tal dalam serangkaian makalah mulai tahun 1997 dan seterusnya, yang berpuncak pada monograf mereka tahun 2009 bersama El Ghaoui. Dimitris Bertsimas dan Melvyn Sim (2004) memperkenalkan formulasi ketidakpastian anggaran (polihedral) yang mempertahankan linearitas masalah nominal dan membuat pemrograman linear robust dapat diakses secara luas. Sejak itu, optimisasi robust telah berkembang untuk mencakup program bilangan bulat, formulasi dua tahap, dan himpunan ketidakpastian yang digerakkan oleh data yang berasal dari pengamatan historis.
Kapan digunakan
Optimisasi robust sesuai ketika ketidakpastian parameter terbatas tetapi distribusinya tidak diketahui atau tidak dapat diandalkan, ketika jaminan kasus terburuk diperlukan (konteks kritis keselamatan atau peraturan), dan ketika satu keputusan yang dapat diimplementasikan diperlukan daripada distribusi kebijakan seperti dalam pemrograman stokastik. Ia bekerja dengan variabel keputusan kontinu. Tidak ada persyaratan ukuran sampel minimum — himpunan ketidakpastian didefinisikan secara analitis, bukan diperkirakan dari data. Ia tidak cocok ketika ketidakpastian tidak terbatas, ketika distribusi probabilitas untuk parameter yang tidak pasti tersedia dan akurat (gunakan optimisasi stokastik sebagai gantinya), atau ketika evaluasi kurang dari sekitar 1.000 skenario akan layak untuk validasi berbasis skenario.
Batasan dan pertimbangan
- Solusinya pasti lebih konservatif daripada optimum nominal; harga robust bisa signifikan ketika himpunan ketidakpastian besar.
- Mendefinisikan himpunan ketidakpastian yang realistis membutuhkan pengetahuan domain; himpunan yang dipilih dengan buruk mungkin terlalu konservatif atau gagal mencakup gangguan sebenarnya.
- Untuk masalah non-cembung atau program campuran-bilangan bulat umum, formulasi ulang robust bisa NP-hard dan memerlukan algoritma dekomposisi khusus.
- Optimisasi robust tidak menggabungkan informasi probabilitas; ketika distribusi yang andal tersedia, pemrograman stokastik dapat menghasilkan kinerja yang diharapkan lebih tinggi.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Memberikan jaminan kasus terburuk deterministik tanpa memerlukan distribusi probabilitas untuk parameter yang tidak pasti.
- Formulasi ulang untuk himpunan ketidakpastian cembung seringkali sama dapat ditangani seperti masalah nominal — tidak ada ledakan komputasi tambahan.
- Tingkat konservatisme dapat dikontrol secara langsung melalui ukuran dan bentuk himpunan ketidakpastian, membuat tradeoff robust-kinerja eksplisit dan transparan.
- Dapat diterapkan di berbagai domain — rantai pasokan, keuangan, desain teknik, sistem energi — di mana pun terdapat ketidakpastian parameter yang terbatas.
Penerapan
- Desain jaringan rantai pasokan dan logistik di bawah permintaan dan waktu tunggu yang tidak pasti.
- Optimisasi portofolio di bawah ketidakpastian dalam imbal hasil aset — batas rata-rata-varians robust.
- Desain teknik (struktural, mekanik, kedirgantaraan) di mana toleransi manufaktur menimbulkan ketidakpastian parameter.
- Perencanaan sistem energi di bawah ketidakpastian pembangkitan terbarukan dan harga bahan bakar.
- Masalah penjadwalan dan perutean di mana waktu pemrosesan atau waktu perjalanan diketahui secara tidak tepat.
Cara kerjanya
Cara kerjanya
Analis menentukan himpunan ketidakpastian — wilayah gangguan yang masuk akal di sekitar nilai parameter nominal. Bentuk umum termasuk kotak (setiap parameter bervariasi secara independen dalam interval), elipsoidal (gangguan dibatasi dalam norma Euclidean), polihedral, dan himpunan yang dibatasi anggaran (Bertsimas-Sim). Pilihan tersebut mengkodekan asumsi tentang seberapa berkorelasi dan parah ketidakpastian dapat terjadi, dan secara langsung mengontrol konservatisme solusi yang dihasilkan.
Masalah optimisasi dirumuskan dalam bentuk minimax: minimalkan keputusan atas biaya maksimum yang dapat ditimbulkan oleh ketidakpastian musuh. Secara formal, tujuannya menjadi min_x max_{u in U} f(x, u) tunduk pada kendala yang harus berlaku untuk semua u dalam himpunan ketidakpastian U. Maksimisasi dalam ini memodelkan alam yang memilih realisasi terburuk dari parameter yang tidak pasti.
Untuk himpunan ketidakpastian cembung, masalah minimax secara analitis setara dengan program cembung deterministik — seringkali program kerucut orde kedua untuk himpunan elipsoidal atau program linear untuk himpunan polihedral. Formulasi ulang yang dapat ditangani ini adalah wawasan kunci dari Ben-Tal dan Nemirovski: rekanan robust dari banyak masalah klasik tidak lebih sulit untuk dipecahkan daripada masalah nominal. Untuk struktur non-cembung, dekomposisi Benders membagi masalah menjadi submasalah utama dan musuh yang diselesaikan secara iteratif.
Program deterministik yang diformulasikan ulang diteruskan ke pemecah cembung atau campuran-bilangan bulat standar. Karena formulasi ulang biasanya merupakan program kerucut atau linear, pemecah siap pakai menanganinya secara efisien. Pemecah mengembalikan satu vektor keputusan — solusi optimal robust — yang layak dan mendekati optimal di semua skenario dalam himpunan ketidakpastian.
Analis memeriksa harga robust: kesenjangan antara nilai tujuan optimal nominal (tanpa ketidakpastian) dan nilai optimal robust. Himpunan ketidakpastian yang ketat menghasilkan kesenjangan kecil tetapi jaminan yang lebih lemah; himpunan besar menghasilkan perlindungan kasus terburuk yang kuat dengan biaya kinerja yang lebih tinggi dalam skenario biasa. Analisis sensitivitas terhadap ukuran himpunan ketidakpastian memandu pilihan akhir tingkat konservatisme.
Kesalahan umum
- Memilih himpunan ketidakpastian yang terlalu besar menghasilkan solusi yang sangat konservatif sehingga hampir tidak berguna — kalibrasi ukuran himpunan terhadap pengetahuan domain atau batas variabilitas historis.
- Mencampuradukkan optimisasi robust dengan optimisasi stokastik: jika distribusi probabilitas untuk parameter yang tidak pasti sudah mapan dan dipercaya, pemrograman stokastik kemungkinan lebih sesuai.
- Menerapkan optimisasi robust ketika ketidakpastian benar-benar tidak terbatas membatalkan jaminan kasus terburuk — optimisasi robust mengasumsikan gangguan terbatas.
- Mengabaikan pemeriksaan harga robust setelah pemecahan: kesenjangan besar antara tujuan nominal dan robust menandakan bahwa himpunan ketidakpastian mungkin terlalu luas dan harus ditinjau kembali.
Pertanyaan yang sering diajukan
Bagaimana optimisasi robust berbeda dari pemrograman stokastik?
Optimisasi robust mencari satu keputusan yang layak dan mendekati optimal untuk setiap skenario dalam himpunan ketidakpastian yang terbatas, tanpa mengasumsikan distribusi probabilitas apa pun atas skenario tersebut. Pemrograman stokastik menggunakan distribusi probabilitas yang diketahui (atau diperkirakan) untuk mengoptimalkan kinerja yang diharapkan, biasanya menghasilkan kebijakan atau tindakan pemulihan daripada satu solusi tetap. Pilih optimisasi robust ketika jaminan kasus terburuk penting dan tidak ada distribusi yang andal tersedia; pilih pemrograman stokastik ketika distribusi yang baik diketahui dan kinerja rata-rata adalah kriteria utama.
Apa itu harga robust?
Harga robust adalah peningkatan nilai tujuan (untuk masalah minimisasi) dibandingkan dengan solusi optimal nominal yang diperoleh tanpa memperhitungkan ketidakpastian. Bertsimas dan Sim (2004) menunjukkan bahwa untuk formulasi ketidakpastian anggaran mereka, harga ini tumbuh hanya sebanding dengan akar kuadrat dari jumlah parameter yang tidak pasti, membuatnya tidak signifikan dalam praktik. Memeriksa kesenjangan ini setelah pemecahan sangat penting: jika sangat besar, himpunan ketidakpastian mungkin terlalu konservatif.
Bentuk himpunan ketidakpastian mana yang harus saya pilih?
Himpunan kotak adalah yang paling sederhana dan paling konservatif — setiap parameter bervariasi secara independen. Himpunan elipsoidal (Ben-Tal & Nemirovski) memodelkan gangguan berkorelasi yang dibatasi dalam norma Euclidean dan mengarah ke program kerucut orde kedua. Himpunan polihedral / dibatasi anggaran (Bertsimas & Sim) mengontrol jumlah parameter yang dapat menyimpang secara bersamaan, mempertahankan linearitas dan mengurangi konservatisme. Pilih berdasarkan pengetahuan domain tentang bagaimana gangguan terjadi bersama dan kelas pemecah mana yang tersedia.
Bisakah optimisasi robust menangani variabel keputusan bilangan bulat?
Ya, tetapi pemrograman bilangan bulat dan campuran-bilangan bulat robust secara substansial lebih sulit. Rekanan robust dari program linear campuran-bilangan bulat seringkali NP-hard dalam kasus terburuk. Dekomposisi Benders dan algoritma generasi kolom-dan-kendala adalah pendekatan standar, tetapi ukuran masalah dan kompleksitas himpunan ketidakpastian harus tetap dapat dikelola.
Metode terkait
Sumber
Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press.
ISBN: 9780691143682Disalin.Bertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53.
Buka referensi DOIDisalin.