Latar belakang matematika untuk PDLP

Halaman ini berisi latar belakang matematika untuk developer dan pengguna tingkat lanjut PDLP, sebuah pemecah masalah pemrograman linear dan kuadrat yang tersedia di OR-Tools. Hal ini berfungsi sebagai referensi untuk bagian kode dan tidak dimaksudkan untuk dibaca sendiri. Pembaca yang berminat harus memahami makalah ini terlebih dahulu, "Pemrograman Linear Skala Besar Praktis menggunakan Gradien Hybrid Primal-Dual", lalu melihat kodenya, lalu kembali ke dokumen ini saat kode tersebut mereferensikannya.

Primal

PDLP mempertimbangkan masalah pemrograman kuadrat cembung berikut ini,

$$ \begin{align} \min_x & \, c^Tx + \frac{1}{2}x^TQx \\ \text{s.t.}\; & l^{c} \le Ax \le u^{c} \\ & l^{v} \le x \le u^{v} \end{align} $$

dengan $A$ adalah matriks $m \times n$ dan $Q$ adalah matriks $n \times n$ diagonal non-negatif1. Vektor terikat atas $u^{c}$ dan $u^{v}$ memiliki entri dalam $\mathbb{R} \cup \{ \infty\}$, dan vektor batas bawah $l^{c}$ dan $l^{v}$ memiliki entri dalam $\mathbb{R} \^c \{ -\infty\$c} \{ -\infty $l} dan asumsi

Dual

Misalkan $a \in \mathbb{R}$. Misalkan $[a]_+$ menunjukkan bagian positifnya dan $[a]_-$ menunjukkan bagian negatifnya, yaitu, $a = [a]_+ - [a]_-$. Bila diterapkan pada vektor, bagian positif dan negatif dihitung berdasarkan elemen.

Ganda dari soal dasar sebelumnya adalah lebih dari $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$, dan $r \in \mathbb{R}^n$. Vektor $y$ berisi pengganda ganda pada batasan linear ($l^{c} \le Ax \le u^

$$ \begin{align} \max_{x, y, r} & \, -\frac{1}{2}x^TQx + \left((l^{c})^T[y]_+ - (u^{c})^T[y]_- \right) + \left((l^{v})^T[r]_+ - (u^{v})^T[r]_- \right) \\ \text{s.t.}\; & Qx + c - A^Ty = r \end{align} $$

Ketika $Q = 0$, $x$ dapat dihapus dari dual, memulihkan dualitas LP.

Batas variabel ganda

Kita katakan bahwa $y$ memenuhi batas variabel ganda jika suku $y$ dalam objektif terbatas, yaitu:

$$ y_i \geq 0 \qquad \text{if }u^c_i = \infty, \\ y_i \leq 0 \qquad \text{if }l^c_i = -\infty. $$

Turunan menggunakan dualitas konjugasi

Persiapan

Misalkan $a \in \mathbb{R} \cup \{-\infty\}$ dan $b \in \mathbb{R} \cup \{\infty\}$ dengan $b \ge a$ dan pertimbangkan interval $[a, b] \subseteq \mathbb{R} \cup \{-\infty}

Misalkan $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ menjadi fungsi indikator interval, yaitu, $\mathcal{I}_{[a, b]}(x)$ adalah nol jika $x \in [a, $.fty]

Definisikan $p(y; a, b): \mathbb{R} \to \mathbb{R} \cup \{\infty\}$ sebagai:

$$ p(y; a, b) = \begin{cases} ay & \text{ if } y < 0 \\ 0 & \text{ if } y = 0 \\ by & \text{ if } y > 0 \end{cases}. $$

Jika $a$ atau $b$ tak terbatas, ikuti aritmetika riil yang diperluas standar.

Hasil dasar: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$ dengan $(\cdot)^*$ menunjukkan konjugasi konveks.

Untuk vektor $l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ dan $u \subseteq (\mathbb{R} \cup \{\infty\})^n$, fungsi indikator $\mathcal{I}_{[l, u]} : \math

Turunan

Memperkenalkan variabel tambahan $\tilde a \in \mathbb{R}^m$ dan $\tilde x \in \mathbb{R}^n$, kami menyatakan kembali masalah utamanya sebagai:

$$ \begin{align} \min_{x, \tilde x, \tilde a} & \, c^Tx + \frac{1}{2}x^TQx + \mathcal{I}_{[l^c,u^c]}(\tilde a) + \mathcal{I}_{[l^v,u^v]}(\tilde x) \\ \text{s.t.}\; & \tilde a = Ax \\ & \tilde x = x \end{align} $$

Dengan menduplikasi batasan kesetaraan, kita memperoleh:

$$ \min_{x, \tilde x, \tilde a} \max_{y, r} c^Tx + \frac{1}{2}x^TQx + y^T\tilde a - y^TAx + r^T\tilde x - r^Tx + \mathcal{I}_{[l^c,u^c]}(\tilde a) + \mathcal{I}_{[l^v,u^v]}(\tilde x) $$

Bertukar min dengan nilai maksimum dan pengelompokan ulang:

$$ \max_{y, r} \min_{x, \tilde x, \tilde a} c^Tx + \frac{1}{2}x^TQx - y^TAx - r^Tx + \left( \mathcal{I}_{[l^c,u^c]}(\tilde a) + y^T\tilde a \right) + \left(\mathcal{I}_{[l^v,u^v]}(\tilde x) + r^T\tilde x \right) $$

Minimalisasi gabungan di atas $x$, $\tilde x$, dan $\tilde a$ terurai. Untuk $x$, kita melihat bahwa meminimalkan, jika ada, memenuhi $Qx + c - A^Ty = r$, dengan nilai minimumnya adalah $-\frac{1}{2} x^TQx$. Untuk $\tilde x$ dan $\tilde a$, kita menerapkan definisi konjugat konveks dengan sedikit penyesuaian untuk tanda.

Hal ini menghasilkan dual:

$$ \begin{align} \max_{x, y, r} & \, -\frac{1}{2}x^TQx - p(-y, l^c, u^c) - p(-r, l^v, u^v) \\ \text{s.t.}\; & Qx + c - A^Ty = r \end{align} $$

Dengan memperluas definisi $p$, kita memperoleh nilai ganda yang disebutkan di bagian atas.

Formulasi titik pelana

Gradien hybrid primal-dual (lihat Chambolle dan Pock) menargetkan masalah utama bentuk

$$ \begin{align} \min_x f(x) + g(x) + h(Kx) \end{align} $$

yang oleh dualitas konjugasi setara dengan masalah titik pelana

$$ \begin{align} \min_x \max_y f(x) + g(x) + y^TKx - h^*(y) \end{align} $$

PDLP memaksakan masalah pemrograman kuadrat cembung ke dalam bentuk ini dengan menetapkan:

  • $f(x) = $0
  • $g(x) = c^T x + \frac{1}{2} x^T Q x + \mathcal{I}_{[l^v, u^v]}(x)$
  • $h(a) = \mathcal{I}_{[-u^c,-l^c]}(a)$
  • $K = -A$

Seperti yang diperoleh sebelumnya, $h^*(y) = p(y; -u^c,-l^c)$ adalah fungsi konveks linear piecewise. $g$ dan $h^*$ dapat mengambil nilai tak terbatas, yang secara efektif membatasi domain $x$ dan $y$.

Perhatikan bahwa operator proksimal $g$ dapat dihitung dalam bentuk tertutup berdasarkan asumsi PDLP bahwa $Q$ adalah diagonal, menggunakan fakta bahwa $g$ dapat dipisahkan dan properti berikut yang berlaku untuk fungsi apa pun $f_1, f_2$:

$$ f_2(t) = f_1(t) + \frac{\mu}{2} t^2 \Rightarrow \mathrm{prox}_{\lambda f_2}(t) = \mathrm{prox}_{\frac{\lambda}{1 + \lambda \mu} f_1}\left( \frac{t}{1 + \lambda \mu} \right). $$

Untuk bukti fakta ini, lihat misalnya Teorema 6.13 di Metode Urutan Pertama dalam Pengoptimalan. Ekspresi yang dihasilkan diberikan oleh

$$ \begin{equation} \mathrm{prox}_{\lambda g}(x) = \mathrm{proj}_{[l^v, u^v]}\left( (I + \lambda Q)^{-1} (x - \lambda c) \right) \end{equation} $$

Pengurangan biaya, residual ganda, dan tujuan ganda yang dikoreksi

Formulasi titik pelana hanya secara eksplisit berfungsi dengan $(x,y)$; pengurangan biaya $r$ bersifat implisit. Untuk menampilkan $(x,y,r)$ saat menyelesaikan rumusan titik pelana, kita menentukan $r$ sebagai $r = Qx + c - A^Ty$. Tujuan ganda yang dikoreksi adalah nilai objektif dari soal ganda, dan selalu memberikan batas bawah pada nilai objektif, tetapi $-\infty$ adalah biaya yang tak terbatas setiap kali ada biaya yang tidak terbatas.

Pengurangan biaya dan tujuan ganda yang dilaporkan oleh PDLP diubah antara alat OR versi 9.7 dan 9.8. Untuk memeriksa versi yang berlaku, periksa komentar yang menjelaskan SolverResult::reduced_costs di primal_dual_hybrid_gradient.h dan lihat apakah komentar tersebut menyebutkan versi 9.8.

Versi 9.7 dan sebelumnya

Untuk memiliki nilai ganda yang lebih bermakna saat tujuan ganda yang dikoreksi adalah $-\infty$, kami juga melaporkan tujuan ganda yang mengabaikan suku tak terbatas dalam nilai objektif. Residual ganda adalah nilai $r$ dari istilah tak terbatas dalam tujuan ganda yang dikoreksi, dengan 0 dalam komponen lainnya, dan pengurangan biaya yang ditampilkan oleh PDLP adalah nilai $r$ dari istilah terbatas dalam tujuan ganda yang dikoreksi, dengan 0 dalam komponen lainnya (sehingga $r = \mbox{residuals} + mbox}).{

Versi 9.8 dan yang lebih baru

Untuk mendapatkan nilai ganda yang lebih bermakna jika objektif ganda yang dikoreksi adalah $-\infty$, kami juga melaporkan tujuan ganda yang menggantikan istilah tak tak terbatas dalam nilai objektif dengan istilah terbatas sebagai berikut: jika salah satu batas terbatas, maka yang digunakan bukan yang tak terbatas; jika tidak, nol akan digunakan untuk batas. Pilihan ini mempertahankan kecekungan tujuan ganda, tetapi tidak selalu memberikan batas lebih rendah pada nilai objektif. Residual ganda adalah nilai $r$ dari suku tak terhingga dalam tujuan ganda yang telah dikoreksi. Pengurangan biaya yang ditampilkan oleh PDLP adalah $r$.

Perlakuan beberapa batas variabel sebagai tak terbatas

Di kedua versi, jika handle_some_primal_gradients_on_finite_bounds_as_residuals opsi pemecah adalah true (default), batas variabel tambahan dapat diperlakukan sebagai tak terbatas saat menghitung tujuan ganda dan residual ganda. Secara khusus, jika $|x_i - l^v_i| > |x_i|$, $l^v_i$ dianggap seolah-olah tak terhingga, dan begitu pula jika $|x_i - u^v_i| > |x_i|$, $u^v_i$ dianggap seolah-olah tak terbatas.

Perhatikan bahwa handle_some_primal_gradients_on_finite_bounds_as_residuals tidak memengaruhi iterasi yang dihitung; tetapi hanya memengaruhi tujuan ganda dan residual yang digunakan dalam pengujian penghentian dan statistik yang dilaporkan.

Penskalaan ulang

Misalkan kita diberi matriks penskalaan ulang diagonal (kolom) $C$ dan matriks penskalaan ulang diagonal (baris) $R$ dengan entri positif pada diagonal tersebut. Dengan menerapkan penskalaan ulang seperti dalam ShardedQuadraticProgram::RescaleQuadraticProgram, kita akan mendapatkan masalah yang telah ditransformasi berikut:

$$ \begin{align} \min_{\tilde x} & \, (Cc)^T{\tilde x} + \frac{1}{2}{\tilde x}^T(CQC){\tilde x} \\ \text{s.t.}\; & Rl^{c} \le RAC\tilde x \le Ru^{c} \\ & C^{-1}l^{v} \le \tilde x \le C^{-1}u^{v} \end{align} $$

Solusi untuk masalah awal dipulihkan sebagai $x = C\tilde x$. Jika $\tilde y$ adalah solusi ganda dan $\tilde r$ adalah pengurangan biaya untuk masalah yang ditransformasi, maka $y = R\tilde y$ adalah solusi ganda dan $r = C^{-1}\tilde r$ adalah pengurangan biaya untuk masalah awal (turunan biaya untuk masalah awal).

Identifikasi ketidaklayakan

Sertifikat ketidaklayakan primal adalah poin $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ memuaskan:

$$ \begin{equation} \left((l^{c})^T[y]_+ - (u^{c})^T[y]_- \right) + \left((l^{v})^T[r]_+ - (u^{v})^T[r]_- \right) > 0 \\ -A^T y = r . \end{equation} $$

Keberadaan titik seperti itu menyiratkan bahwa masalah utama tidak memiliki solusi.

Demikian pula, sertifikat inkompatibilitas ganda berupa titik $x \in \mathbb{R}^n$ sehingga:

$$ \begin{equation} Qx = 0 \\ c^T x < 0 \\ (Ax)_i \begin{cases} = 0 & \text{if }l^c_i , u^c_i \in \mathbb{R}, \\ \geq 0 & \text{if }l^c_i \in \mathbb{R}, u^c_i = \infty, \\ \leq 0 & \text{if }l^c_i = -\infty, u^c_i \in \mathbb{R}, \end{cases} \\ x_i \begin{cases} = 0 & \text{if }l^v_i , u^v_i \in \mathbb{R}, \\ \geq 0 & \text{if }l^v_i \in \mathbb{R}, u^v_i = \infty, \\ \leq 0 & \text{if }l^v_i = -\infty, u^v_i \in \mathbb{R}. \end{cases} \end{equation} $$

Perlu diperhatikan bahwa sertifikat untuk program linear dapat diperoleh dengan menetapkan $Q=0$.

  1. Matriks objektif semidefinit positif simetris $S$ dapat dikonversi menjadi bentuk ini dengan memfaktorkan $S$ sebagai $S = R^T R$ (misalnya, faktorisasi Cholesky), dengan memasukkan variabel tambahan $z$ yang ditentukan dengan batasan $R x - z = 0$, sehingga $x^T S x ↩↩