Skip to content
Kembali ke hasil pencarian

Metode Lagrangian Teregumentasi

Diperkenalkan oleh
Magnus R. Hestenes and M. J. D. Powell
Tahun
1969
Jenis
algorithm
Keluarga
Optimization

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

Ukuran huruf

Apa fungsinya?

Metode Lagrangian Teregumentasi, dikembangkan oleh Magnus R. Hestenes dan M. J. D. Powell pada tahun 1969, adalah teknik yang ampuh untuk menyelesaikan masalah optimasi terkendala.

Metode ini mengubah masalah terkendala menjadi urutan submasalah tak terkendala dengan menambahkan suku penalti kuadratik pada Lagrangian, memungkinkan penyelesaian masalah skala besar yang efisien, termasuk kasus cembung dan non-cembung.

Intuisi di balik metode

Metode ini dibangun di atas pendekatan relaksasi Lagrangian klasik tetapi memperbaikinya dengan menambahkan suku penalti kuadratik yang mencegah pelanggaran kendala. Alih-alih mendorong bobot penalti ke tak terhingga (yang menyebabkan masalah numerik), algoritma mempertahankan bobot penalti yang masuk akal dan secara iteratif memperbarui pengali Lagrange (variabel dual) untuk menegakkan kendala. Keseimbangan antara pembaruan penalti dan pengali ini memastikan konvergensi yang lebih cepat daripada metode penalti murni sambil tetap stabil secara numerik. Metode ini sangat efektif untuk masalah dengan struktur yang dapat dipisahkan.

Sejarah

Hestenes dan Powell secara independen memperkenalkan metode Lagrangian teregumentasi pada tahun 1969, membangun konsep relaksasi Lagrangian sebelumnya. Metode ini mendapatkan perhatian pada tahun 1970-an-80-an untuk menyelesaikan masalah terkendala dalam riset operasi dan teknik. Perkembangan utama termasuk Metode Pengali Arah Bergantian (ADMM) oleh Boyd dkk. (2011), yang mengkhususkan metode ini untuk masalah cembung dengan struktur terpisah dua blok, menemukan aplikasi luas dalam pembelajaran mesin, pemrosesan sinyal, dan statistik.

Kapan digunakan

Terapkan metode Lagrangian teregumentasi pada masalah optimasi terkendala di mana dekomposisi menjadi submasalah dimungkinkan atau ketika kendala sulit ditangani secara langsung. Metode ini ideal untuk masalah skala besar dengan struktur khusus, tujuan cembung atau non-cembung, dan kendala kesamaan atau ketidaksetaraan. Gunakan ketika penyelesaian submasalah lebih mudah daripada menyelesaikan seluruh masalah. Untuk masalah tak terkendala atau masalah skala sangat besar yang memerlukan paralelisasi, pertimbangkan varian khusus seperti ADMM.

Batasan dan pertimbangan

  • Memerlukan penyelesaian submasalah secara akurat, yang bisa mahal
  • Kecepatan konvergensi bergantung pada kualitas pemecah submasalah
  • Pemilihan dan pembaruan parameter penalti memerlukan penyesuaian
  • Kurang efektif dibandingkan pemecah khusus pada masalah tanpa struktur yang dapat dieksploitasi
  • Dapat sensitif terhadap presisi numerik dalam perhitungan residu kendala

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

Kelebihan

  • Memungkinkan penyelesaian masalah terkendala yang sulit melalui submasalah yang dapat dikelola
  • Menangani kendala kesamaan dan ketidaksetaraan secara alami
  • Bekerja untuk masalah non-cembung dengan modifikasi yang sesuai
  • Menghindari masalah pengkondisian buruk dari metode penalti murni
  • Secara alami dapat diterapkan pada komputasi paralel dan terdistribusi
  • Fleksibel dalam pilihan pemecah submasalah

Penerapan

  • Optimasi jaringan: menyelesaikan masalah desain dan aliran jaringan skala besar
  • Pembelajaran mesin: pelatihan terdistribusi model dengan kendala
  • Pemrosesan gambar: menyelesaikan masalah invers dengan kendala regularisasi
  • Kontrol optimal: menangani optimasi lintasan dengan kendala dinamis
  • Sistem tenaga: dispatch ekonomi dengan kendala transmisi dan stabilitas
  • Alokasi sumber daya: mendistribusikan sumber daya antar agen yang tunduk pada kendala penggabungan

Cara kerjanya

Cara kerjanya

1

Tetapkan pengali Lagrange awal (biasanya nol), pilih parameter penalti awal, dan definisikan fungsi Lagrangian teregumentasi yang menggabungkan Lagrangian asli dengan penalti kuadratik.

2

Minimalkan Lagrangian teregumentasi terhadap variabel primal (submasalah tak terkendala), menggunakan metode optimasi yang sesuai. Penalti kuadratik mengarahkan solusi menuju kelayakan.

3

Perbarui pengali Lagrange berdasarkan residu kendala (langkah kenaikan dual). Sesuaikan parameter penalti secara opsional. Ulangi langkah minimisasi dan pembaruan hingga konvergensi tercapai.

Kesalahan umum

  • Menggunakan solusi submasalah yang tidak akurat, yang mengarah pada konvergensi keseluruhan yang buruk
  • Memilih parameter penalti yang terlalu besar atau terlalu kecil, menyebabkan masalah numerik atau konvergensi lambat
  • Gagal memperhitungkan struktur masalah saat melakukan dekomposisi menjadi submasalah
  • Tidak menskalakan kendala dan variabel dengan benar, menyebabkan ketidakstabilan numerik

Pertanyaan yang sering diajukan

Bagaimana Lagrangian teregumentasi meningkatkan relaksasi Lagrangian klasik?

Metode Lagrangian klasik memerlukan bobot penalti ke tak terhingga untuk kepuasan kendala, menyebabkan pengkondisian buruk. Lagrangian teregumentasi mempertahankan bobot penalti yang masuk akal dan memperbarui pengali secara adaptif, mencapai konvergensi yang lebih cepat dan stabilitas numerik yang lebih baik.

Apa hubungan antara Lagrangian teregumentasi dan ADMM?

ADMM adalah varian khusus dari metode Lagrangian teregumentasi yang dirancang untuk masalah cembung dengan struktur terpisah dua blok. Metode ini memecah masalah menjadi dua submasalah yang diselesaikan secara bergantian, memungkinkan implementasi paralel dan terdistribusi.

Bagaimana parameter penalti harus dipilih dan diperbarui?

Mulai dengan parameter penalti sedang (misalnya, 1 atau berdasarkan penskalaan masalah). Tingkatkan jika kendala dilanggar setelah pembaruan; kurangi jika solusi submasalah menjadi sulit. Skema adaptif menyesuaikannya berdasarkan tren residu kendala.

Bisakah metode ini menyelesaikan masalah non-cembung?

Ya, dengan modifikasi yang sesuai. Jaminan konvergensi berbeda (konvergensi ke titik stasioner daripada optimum global), dan pemecah submasalah harus menangani non-cembungan. Metode ini tetap efektif untuk banyak masalah non-cembung praktis.

Metode terkait

Sumber

  1. Hestenes, M. R. (1969). Multiplier and gradient methods. Journal of Optimization Theory and Applications, 4(5), 303-320.

    Buka referensi DOI
    Disalin.
  2. Powell, M. J. D. (1969). A method for nonlinear constraints in minimization problems. In Optimization (pp. 283-298). Academic Press.

    Buka referensi publikasi
    Disalin.
  3. Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1), 1-122.

    Buka referensi DOI
    Disalin.