PDLP için matematiksel arka plan

Bu sayfada, VEYA Araçları'nda kullanılabilen bir doğrusal ve ikinci dereceden programlama çözücü olan PDLP'nin geliştiricileri ve ileri düzey kullanıcıları için matematiksel arka plan bilgileri bulunmaktadır. Bu metin, kodun bazı bölümleri için referans işlevi görür ve kendi başına okunması amaçlanmamıştır. İlgilenen okuyucular önce "Primal-Dual Hybrid Gradient" (Primal-Dual Hybrid Gradient kullanarak Pratik Büyük Ölçekli Doğrusal Programlama) başlıklı makaleyi tanımalı, daha sonra koda bakmalıdır ve kodda bu sayfaya referans verildiğinde bu dokümana tekrar bakmalıdır.

Primal

PDLP, aşağıdaki dışbükey ikinci dereceden programlama problemini,

$$ \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} $$

Burada $A$ bir $m \times n$ matrisi, $Q$ ise köşegen ve negatif olmayan $n \times n$ matrisidir1. $u^{c}$ ve $u^{v}$ vektörleri, $\mathbb{R} \cup \{ \infty\}$ girişlerine, $l^{c}$ ve $l^{v}$ alt sınır vektörlerinin $\mathbb{R} \$^} için $\mathbb{R} \$^} \{ ^} -\.'fty'de \{^v

Dual

$a \in \mathbb{R}$ izin verin. $[a]_+$ pozitif kısmını, $[a]_-$ negatif kısmını, yani $a = [a]_+ - [a]_-$ değerini göstersin. Bir vektöre uygulandığında, pozitif ve negatif parçalar elemanlar bazında hesaplanır.

Önceki asal problemin ikilisi, $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$ ve $r \in \mathbb{R}^n$ üzerindedir. $y$ vektörü, {l$ ^v{c} ^l kısıtları üzerinde {$l${c} \le Ax {cre} kısıtlamalarında çift çarpanlar içerir).

$$ \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} $$

$Q = 0$ olduğunda $x$ ikiliten çıkarılabilir ve böylece LP ikililiği kurtarılabilir.

Çift değişken sınırları

Hedefteki $y$ terimi sonluysa $y$, çift değişken sınırlarını karşıladığını belirtiriz. Diğer bir deyişle:

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

Eşlemli ikilik kullanarak türetme

Hazırlıklar

$a \in \mathbb{R} \cup \{-\infty\}$ ve $b \in \mathbb{R} \cup \{\infty\}$ için $b \ge a$ yazın ve $[a, b] \subseteq \mathbb{R} \cupfty \{-\inflik aralığını dikkate alın

$\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ aralığın gösterge fonksiyonu olsun. $\mathcal{I}_{[a, b]}(x)$, aksi halde $x \bty'de sıfır ve $x \bty] [$] için 0'dır.

$p(y; a, b): \mathbb{R} \to \mathbb{R} \cup \{\infty\}$ tanımını şu şekilde yapın:

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

$a$ veya $b$ sonsuz olduğunda standart genişletilmiş gerçek aritmetiği uygulayın.

Temel sonuç: $p(y; a; b) = (\mathcal{I}_{[a, b]})^*(y)$; burada $(\cdot)^*$, dışbükey eşleniği gösterir.

$l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ ve $u \subseteq (\mathbb{R} \cup \{\infty\})^n$, $l \subseteq (\$l_1t

Türetme

$\tilde a \in \mathbb{R}^m$ ve $\tilde x \in \mathbb{R}^n$ yardımcı değişkenlerine eklenerek asal problemi şu şekilde yeniden ifade ederiz:

$$ \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} $$

Eşitlik kısıtlamalarını ikiye bölerek şu sonucu elde ederiz:

$$ \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) $$

Maks. ile minimum değer değişimi ve yeniden gruplama:

$$ \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) $$

$x$, $\tilde x$ ve $\tilde a$ üzerindeki birleştirme işlemleri ayrıştırır. $x$ için, minimum değerin (varsa) $Qx + c - A^Ty = r$ koşulunu karşıladığını görüyoruz. Bu durumda minimum değer $-\frac{1}{2} x^TQx$ olur. $\tilde x$ ve $\tilde a$ için, işaretler için küçük ayarlamalarla dışbükey eşlemlerin tanımını uygularız.

Bu ikili sonuç verir:

$$ \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} $$

$$ ifadesinin tanımını genişleterek en üstte belirtilen çift rakamı elde ederiz.

Sefer noktası formülü

Pratik-çift karma gradyan (bkz. Chambolle ve Pock),

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

Bu da eşlenik ikilik açısından sırt noktası problemine

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

PDLP, aşağıdaki adımları uygulayarak dışbükey ikinci dereceden programlama problemini bu biçime dönüştürür:

  • $f(x) = 0 TL
  • $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$

Daha önce türetildiği gibi, $h^*(y) = p(y; -u^c,-l^c)$, parçalı bir doğrusal dışbükey fonksiyonudur. Hem $g$ hem de $h^*$ sonsuz değerler alabilir. Bu da sırasıyla $x$ ve $y$ alanlarını etkin bir şekilde sınırlandırır.

PDLP'ye göre $g$'ın köşegen olduğu varsayımı kapsamında $g$'ın yakınsal operatörü, $g$'ın ayrılabilir olduğu ve $f_1, f_2$ herhangi bir fonksiyon için kullanılan aşağıdaki özelliğin kullanıldığı gerçeği kullanılarak kapalı biçimde hesaplanabilir:

$$ 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). $$

Bunun kanıtı için Optimizasyonda Birinci Derece Yöntemler bölümündeki Teorem 6.13'e bakın. Elde edilen ifade,

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

Azaltılmış maliyetler, çift artıklar ve düzeltilmiş ikili hedef

Eyer noktası formülü yalnızca $(x,y)$ ile açık bir şekilde işe yarar; azaltılmış maliyetler $r$ örtülüdür. Eyer noktası formülasyonunu çözerken $(x,y,r)$ sonucunu döndürmek için $r$ değerini $r = Qx + c - A^Ty$ olarak tanımlarız. Düzeltilen çift hedef, ikili problemin nesnel değeridir ve nesnel değere her zaman alt sınır verir, ancak on-zor olmayan bir sınırda $-ero\inzty$ olarak sınırlanır.

PDLP tarafından bildirilen düşük maliyet ve ikili hedef, VEYA araçları sürümleri 9.7 ve 9.8 arasında değiştirildi. Hangi sürümün geçerli olduğunu kontrol etmek için primal_dual_hybrid_gradient.h ürününde SolverResult::reduced_costs özelliğini açıklayan yorumu kontrol edin ve 9.8 sürümünden bahsedilip bahsedilmediğine bakın.

9.7 ve önceki sürümler

Düzeltilen ikili hedef $-\infty$ olduğunda daha anlamlı bir ikili değere sahip olmak için hedef değerdeki sonsuz terimleri yok sayan bir ikili hedef de raporlarız. Çift artık, düzeltilen ikili hedefteki sonsuz terimlerden elde edilen ve diğer bileşenlerde 0 olacak şekilde r$'dır. PDLP tarafından döndürülen azaltılmış maliyetler ise düzeltilen ikili hedefteki sonlu terimlerden elde edilen ve diğer bileşenlerde 0 olacak şekilde, diğer bileşenlerde 0 olacak şekilde, $r = box\mbox{resit} değerine denir.

9.8 ve üzeri sürümler

Düzeltilen ikili hedef $-\infty$ olduğunda daha anlamlı bir ikili değere sahip olmak için bir ikili hedef de rapor ederiz. Bu hedef değerdeki sonsuz terimleri aşağıdaki gibi sonlu terimlerle değiştirir: Sınırlardan biri sonluysa sonlu yerine söz konusu sınır kullanılır; aksi takdirde, sınır için sıfır kullanılır. Bu seçim, ikili hedefin içbükeyliğini korur, ancak her zaman hedef değer için daha düşük bir sınır sağlamaz. Çift artıklar, düzeltilmiş ikili hedefteki sonsuz terimlerden elde edilen r$ değerlerinin değerleridir. PDLP tarafından döndürülen maliyetlerin azaltılması r$ tutarındadır.

Bazı değişken sınırlarının sonsuz olarak işlenmesi

Her iki sürümde de çözücü seçeneği handle_some_primal_gradients_on_finite_bounds_as_residuals, true (varsayılan) ise ikili hedef ve ikili artıkları hesaplarken ek değişken sınırları sonsuz olarak kabul edilebilir. Özellikle, $|x_i - l^v_i| > |x_i|$, $l^v_i$ sonsuz gibi kabul edilir ve benzer şekilde, $|x_i - u^v_i| > |x_i|$ olduğunda, $u^v_i$ sonsuz gibi kabul edilir.

handle_some_primal_gradients_on_finite_bounds_as_residuals değerinin hesaplanan yinelemeleri etkilemediğini, yalnızca sonlandırma testlerinde ve raporlanan istatistiklerde kullanılan ikili hedefi ve artıkları etkilediğini unutmayın.

Yeniden ölçeklendirme

Bize köşegen üzerinde pozitif girişlere sahip $C$ köşegen (sütun) yeniden ölçeklendirme matrisi ve $R$ köşegen (satır) yeniden ölçeklendirme matrisi verildiğini varsayalım. ShardedQuadraticProgram::RescaleQuadraticProgram'deki gibi yeniden ölçeklendirmeyi uygulayarak aşağıdaki dönüştürülen problemi elde ederiz:

$$ \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} $$

Baştaki problemin çözümü, $x = C\tilde x$ şeklinde kurtarılır. $\tilde y$ ikili çözümse ve $\tilde r$ dönüştürülen problemin maliyetleri azalırsa $y = R\tilde y$ ikili bir çözüm olur ve $r = C^{-1}\tilde r$ orijinal problem için azaltılır).

Uygulanabilirlik tespiti

Birincil uygulanabilirlik sertifikası, $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ tutarında bir puandır ve aşağıdaki koşulları sağlar:

$$ \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} $$

Böyle bir noktanın varlığı, temel sorunun çözümü olmadığı anlamına gelir.

Benzer şekilde, ikili uygulanabilirlik sertifikası $x \in \mathbb{R}^n$ noktasıdır. Örneğin:

$$ \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} $$

Doğrusal programlar için sertifikaların $Q=0$ ayarlanarak alınabileceğini unutmayın.

  1. Simetrik pozitif yarı tanımlı hedef matrisi $S$ bu forma dönüştürülebilir. $S$, $S = R^T R$ olarak hesaplanır (örneğin, Cholesky'nin çarpanlarına ayırması) ve $R x - z = 0$ kısıtlamalarıyla tanımlanan $z$ ek değişkenleri dahil edilir. Böylece $x^T S x = 0$ yapılır. ↩.