Optimisasi Lanjut dan Analisis Konveks - Modul Becker 2: Pemisahan Douglas-Rachford
Status pembaca. Modul ini menerjemahkan tepat baris 2750–2797 dari Stephen Becker, convex-optimization-class, commit
98ed6930084c435ba0f675f7646ced1f2fd8729e; catatan ketik sumber mengreditkan Mitchell Krock. Catatan donor mengreditkan Bauschke dan Combettes serta Lions dan Mercier. Materi program linear dan bagian ADMM yang bersebelahan tidak diimpor. Materi donor mempertahankan Lisensi MIT; terjemahan, koreksi, dan penghubung mandiri tersedia berdasarkan CC BY-SA 4.0. Ini bukan edisi resmi atau dukungan pihak sumber.Provenans produksi: OpenAI Codex gpt-5.6-sol, Ultra, atas instruksi pengguna repositori; seluruh kredit penulis dan kontributor manusia tetap dipertahankan.
Pemisahan Douglas–Rachford
Bab ini menyajikan metode Douglas–Rachford untuk meminimumkan jumlah dua fungsi konveks melalui operator proksimal. Notasi subdiferensial dan bentuk dual dinormalkan agar persamaan konsisten dengan parameter skala yang dipakai dalam algoritma.
Kredit catatan donor.
Catatan donor menyatakan bahwa bagian ini mengikuti Bauschke dan Combettes (B&C), edisi kedua (2017), §20.3, dan mengatribusi analisis Douglas–Rachford kepada Lions dan Mercier (1979). Kredit turunan tersebut dipertahankan; edisi ini tidak mengimpor isi dari bagian yang bersebelahan.
Ambil \(f,g\in\Gamma_0(\mathbb{R}^n)\), yaitu fungsi konveks proper dan semikontinu bawah. Seperti pada donor, andaikan terdapat titik pelana primal–dual dan aturan jumlah subdiferensial \[\begin{equation} \label{becker:eq:dr-sum-rule} \partial(f+g)=\partial f+\partial g \end{equation}\] berlaku. Masalah primal adalah \[\begin{equation} \label{becker:eq:dr-primal} (P)\qquad p^*=\min_{x\in\mathbb{R}^n}\bigl\{f(x)+g(x)\bigr\}. \end{equation}\] Dengan konjugat Fenchel \(h^*(u)=\sup_x\{\langle u,x\rangle-h(x)\}\), bentuk maksimisasi dual yang konsisten adalah \[\begin{equation} \label{becker:eq:dr-dual} (D)\qquad d^*=\sup_{u\in\mathbb{R}^n}\bigl\{-f^*(-u)-g^*(u)\bigr\}. \end{equation}\] Secara ekuivalen, titik dual yang sama meminimumkan \(f^*(-u)+g^*(u)\). Tanda pada bentuk dual donor diperbaiki secara terbuka dalam edisi ini.
Untuk \(h\in\Gamma_0(\mathbb{R}^n)\) dan \(\rho>0\), tuliskan \[\begin{equation} \label{becker:eq:dr-prox-definition} \operatorname{prox}_{\rho h}(v) =\operatorname*{arg\,min}_{w\in\mathbb{R}^n} \left\{h(w)+\frac{1}{2\rho}\left\lVert w-v\right\rVert_2^2\right\} =(I+\rho\partial h)^{-1}(v). \end{equation}\] Pilih \(y_0\in\mathbb{R}^n\), parameter skala \(\rho>0\), dan parameter relaksasi tetap \(\lambda\in(0,2)\). Iterasi Douglas–Rachford adalah \[\begin{equation} \label{becker:eq:dr-iteration} \begin{aligned} x_k&=\operatorname{prox}_{\rho g}(y_k),\\ z_k&=\operatorname{prox}_{\rho f}(2x_k-y_k),\\ y_{k+1}&=y_k+\lambda(z_k-x_k). \end{aligned} \end{equation}\] Catatan donor memperingatkan bahwa konvensi untuk \(\rho\) pada bagian lain mungkin memakai kebalikannya. Di sini \(\rho\) selalu memiliki arti yang ditetapkan oleh definisi operator proksimal.
Limit bayangan dan persamaan titik tetap
Jika barisan pada iterasi Douglas--Rachford memenuhi \(y_k\to\bar y\) dan \[\begin{equation} \bar x=\operatorname{prox}_{\rho g}(\bar y), \end{equation}\] maka \(\bar x\) adalah solusi optimal masalah masalah primal.
Proof. Karena \(y_k\) konvergen, \(y_{k+1}-y_k=\lambda(z_k-x_k)\to0\), sehingga \(z_k-x_k\to0\). Operator proksimal kontinu, maka \[\begin{equation} \bar x=\operatorname{prox}_{\rho g}(\bar y), \qquad \bar x=\operatorname{prox}_{\rho f}(2\bar x-\bar y). \end{equation}\] Syarat optimalitas kedua operator proksimal memberi \[\begin{equation} \frac{\bar y-\bar x}{\rho}\in\partial g(\bar x), \qquad \frac{\bar x-\bar y}{\rho}\in\partial f(\bar x). \end{equation}\] Menjumlahkan kedua inklusi dan memakai aturan aturan jumlah menghasilkan \(0\in\partial(f+g)(\bar x)\), yang setara dengan optimalitas primal. ◻
Persamaan titik tetapnya dapat dilihat langsung dari syarat optimalitas. Untuk solusi primal \(x\), pilih \(u\in\partial g(x)\) dengan \(-u\in\partial f(x)\), lalu definisikan \(y=x+\rho u\). Dengan demikian \[\begin{equation} \label{becker:eq:dr-resolvent-motivation} \begin{aligned} y&\in x+\rho\partial g(x), &x&=(I+\rho\partial g)^{-1}(y)=\operatorname{prox}_{\rho g}(y),\\ 2x-y=x-\rho u&\in x+\rho\partial f(x), &x&=(I+\rho\partial f)^{-1}(2x-y)=\operatorname{prox}_{\rho f}(2x-y). \end{aligned} \end{equation}\] Jadi, dengan \[\begin{equation} x=\operatorname{prox}_{\rho g}(y), \qquad z=\operatorname{prox}_{\rho f}(2x-y), \end{equation}\] syarat solusi menjadi \(z-x=0\). Pembaruan \(y\leftarrow y+\lambda(z-x)\) pada iterasi Douglas--Rachford merupakan iterasi relaksasi menuju titik tetap itu. Faktor \(\rho\) dan pilihan subgradien \(u\) ditulis eksplisit karena subdiferensial pada umumnya bernilai himpunan dan tidak dapat diperlakukan sebagai satu vektor \(d g(x)\).
Hubungan dengan ADMM
Pernyataan singkat donor bahwa ADMM merupakan kasus khusus Douglas–Rachford dipahami dalam bentuk yang lazim dan lebih presisi: ADMM dapat diperoleh sebagai pemisahan Douglas–Rachford yang diterapkan pada masalah dual yang sesuai. Bagian ADMM yang mendahului rentang beku tidak diimpor ke modul ini.
Perubahan dan batas sumber
Edisi menormalkan notasi subdiferensial, membetulkan tanda dual Fenchel, memulihkan faktor \(\rho\) dalam derivasi titik tetap, memperjelas bukti limit bayangan, dan menyatakan hubungan ADMM sebagai pemisahan Douglas–Rachford pada masalah dual yang sesuai. Salah eja nama Mercier dibetulkan. Tidak ada isi di luar baris 2750–2797 yang diterjemahkan ke dalam unit ini.
Atribusi, lisensi, dan nondukungan
Sumber: Stephen Becker, repositori
convex-optimization-class; catatan ketik APPM5720Notes
oleh Mitchell Krock; commit
98ed6930084c435ba0f675f7646ced1f2fd8729e; https://github.com/stephenbeckr/convex-optimization-class.
Catatan donor menyatakan bahwa bagian ini mengikuti Bauschke dan
Combettes, edisi kedua (2017), §20.3, serta mengatribusi analisis
Douglas–Rachford kepada Lions dan Mercier (1979). Materi donor berada di
bawah Lisensi MIT. Terjemahan, koreksi, dan penghubung mandiri tersedia
berdasarkan Creative Commons Attribution-ShareAlike 4.0 International,
https://creativecommons.org/licenses/by-sa/4.0/. Stephen
Becker, Mitchell Krock, Bauschke, Combettes, Lions, Mercier, dan
University of Colorado Boulder tidak menyusun, memeriksa, menyetujui,
atau mendukung edisi ini.
Pemberitahuan Lisensi MIT sumber
MIT License
Copyright (c) 2017 Stephen Becker
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.