पीडीएलपी के लिए गणितीय बैकग्राउंड

इस पेज पर, डेवलपर और पीडीपी के ज़्यादा जानकारी रखने वाले उपयोगकर्ताओं के लिए, गणित के विषय का बैकग्राउंड मौजूद है. यह OR-टूल में उपलब्ध लीनियर और क्वाड्रेटिक प्रोग्रामिंग सॉल्वर है. यह कोड के कुछ हिस्सों के लिए रेफ़रंस के तौर पर काम करता है, न कि सिर्फ़ पढ़ने के लिए. दिलचस्पी रखने वाले लोगों को सबसे पहले "प्रैक्टिकल लार्ज-स्केल लीनियर प्रोग्रामिंग इस्तेमाल करके प्राइमल-ड्यूअल हाइब्रिड ग्रेडिएंट" पेपर के बारे में पढ़ना चाहिए. इसके बाद, कोड को देखें और जब कोड इसका रेफ़रंस दे, तो इस दस्तावेज़ पर वापस आएं.

प्राइमल

पीडीपी, इन कन्वेक्स क्वाड्रेटिक प्रोग्रामिंग समस्या को ध्यान में रखता है,

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

जहां $A$ एक $m \times n$ मैट्रिक्स है और $Q$, डाइगनल नॉन-नेगेटिव $n \times n$ मैट्रिक्स1 है. अपर बाउंड वेक्टर $u^{c}$ और $u^{v}$ की एंट्री $\mathbb{R} \cup \{ \infty\}$ में हैं, और लोअर बाउंड वेक्टर $l^{c}$ और $l^{v}$ में एंट्री हैं $\math\b${R} \cup \cup \yl. ${ ^$ $$.

Dual

$a \in \mathbb{R}$. मान लें कि $[a]_+$ इसका पॉज़िटिव पार्ट दिखाता है और $[a]_-$ इसका नेगेटिव हिस्सा दिखाता है, यानी $a = [a]_+ - [a]_-$. किसी वेक्टर पर लागू करने पर, पॉज़िटिव और नेगेटिव पार्ट का आकलन, एलिमेंट के हिसाब से किया जाता है.

पहले की मूल समस्या का ड्यूअल, $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$, और $r \in \mathbb{R}^n$ से ज़्यादा है. वेक्टर $y$ में लीनियर\वेक्टर ($l^{c} \le Ax$resd) पर ड्यूअल मल्टीप्लायर शामिल हैं, ^${redus}.

$$ \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$ होने पर, $x$ को डुअल से हटाया जा सकता है, जिससे LP द्वैता वापस मिल जाता है.

ड्यूअल वैरिएबल बाउंड

हम कहते हैं कि $y$ ड्यूअल वैरिएबल सीमाओं को पूरा करता है. ऐसा तब होता है, जब मकसद में $y$-term सीमित हो, यानी कि:

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

संयुग्मी द्वैत का इस्तेमाल करके व्युत्पन्न करना

प्रारंभिक दौर

$a \in \mathbb{R} \cup \{-\infty\}$ और $b \in \mathbb{R} \cup \{\infty\}$ को $b \ge a$ के साथ स्वीकार करें और अंतराल $[a, b] \subseteq \mathbb{R} \cup \$yft.

$\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ यह देखें कि इंटरवल का इंडिकेटर फ़ंक्शन है, यानी $\mathcal{I}_{[a, b]}(x)$ जब $x b]}(x)$ में शून्य होगा और ऐसा नहीं होगा

$p(y; a, b): \mathbb{R} \to \mathbb{R} \cup \{\infty\}$ को इस रूप में परिभाषित करें:

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

जब $a$ या $b$ अनंत हो, तो स्टैंडर्ड एक्सटेंडेड रीयल अंकगणित अपनाएं.

बुनियादी नतीजा: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$ जहां $(\cdot)^*$ उद्धरण संयुग्मी को दिखाता है.

$l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ और $u \subseteq (\mathbb{R} \cup \{\infty\})^n$, सूचक \mathcal\जैसा}_{[l,u]} :

पहले से मौजूद रचना पर आधारित काम

पेश हैं सहायक वैरिएबल $\tilde a \in \mathbb{R}^m$ और $\tilde x \in \mathbb{R}^n$, हम शुरुआती समस्या को इस तरह बताते हैं:

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

समानता की पाबंदियों को दोहराते हुए, हमें ये फ़ायदे मिले:

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

कम से कम वैल्यू को ज़्यादा से ज़्यादा और फिर से ग्रुप में बांटने के साथ:

$$ \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$, और $\tilde a$ को डिकंपोज़ किया जाने से जुड़ा जाइंट मिनिमाइज़ेशन. $x$ के लिए हम देखते हैं कि छोटा करने वाला अगर मौजूद है, तो $Qx + c - A^Ty = r$ संतुष्ट होता है. इस स्थिति में कम से कम वैल्यू $-\frac{1}{2} x^TQx$ है. $\tilde x$ और $\tilde a$ के लिए हम, संकेतों के लिए मामूली अडजस्टमेंट के साथ कन्वर्ज़न की परिभाषा लागू करते हैं.

इससे ड्यूअल मिलती है:

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

$p$ की परिभाषा को बड़ा करने पर, हमें सबसे ऊपर ड्यूअल हैंडजैट मिलते हैं.

सैडल-पॉइंट फ़ॉर्म्यूलेशन

प्राइमल-ड्यूअल हाइब्रिड ग्रेडिएंट (चैंबोल और पॉक देखें) इस फ़ॉर्म की एक अहम समस्या को टारगेट करता है

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

जो संयुग्मी द्वैत (डुअलिटी) से सैडल-पॉइंट समस्या के बराबर होता है

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

पीडीपी, कन्वर्ज़न की क्वाड्रेटिक प्रोग्रामिंग समस्या को इस फ़ॉर्म में सुलझाने के लिए, नीचे दी गई सेटिंग लागू करता है:

  • $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$

जैसा कि पहले बताया गया है, $h^*(y) = p(y; -u^c,-l^c)$ एक पीस वाइज लीनियर कन्वर्ज़न फ़ंक्शन है. $g$ और $h^*$, दोनों में असीमित वैल्यू का इस्तेमाल किया जा सकता है, जो कि $x$ और $y$ के डोमेन को सीधे तौर पर सीमित कर देता है.

ध्यान दें कि पीडीपी के मुताबिक $g$ का प्रॉक्सिमल ऑपरेटर, क्लोज़्ड फ़ॉर्म में कंप्यूट किया जा सकता है. यह अनुमान लगाया गया है कि $Q$ डायगनल है. ऐसा इसलिए, क्योंकि $g$ को अलग किया जा सकता है. $f_1, f_2$ किसी भी फ़ंक्शन के लिए दी गई आगे दी गई प्रॉपर्टी $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). $$

इस तथ्य को बेहतर तरीके से समझने के लिए, ऑप्टिमाइज़ेशन के लिए पहले से ऑर्डर करने के तरीके सेक्शन में थ्योरम 6.13 देखें. नतीजे के तौर पर मिलने वाला एक्सप्रेशन,

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

कम की गई कीमत, दोहराव के बारे में जानकारी, और सही किए गए दोहरा मकसद

सैडल पॉइंट फ़ॉर्मूला सिर्फ़ $(x,y)$ के साथ काम करता है. कम लागत $r$ का मतलब साफ़ तौर पर नहीं है. काजल-बिंदु के फ़ॉर्मूले को हल करते समय $(x,y,r)$ पाने के लिए, हम $r$ को $r = Qx + c - A^Ty$ के रूप में परिभाषित करते हैं. सही दो मकसद, दोहरा सवाल का वास्तविक मकसद है. यह घटी हुई वास्तविक वैल्यू के लिए हमेशा एक निचली सीमा देता है, लेकिन कोई गैर-शून्य लागत होने पर $-\infty$ होता है.

पीडीपी की ओर से रिपोर्ट की गई कम लागत और दो मकसद को OR-टूल के वर्शन 9.7 और 9.8 में बदल दिया गया था. यह जानने के लिए कि कौनसा वर्शन लागू होता है, primal_dual_hybrid_gradient.h में SolverResult::reduced_costs के बारे में बताने वाली टिप्पणी देखें और देखें कि क्या उसमें वर्शन 9.8 का ज़िक्र है.

वर्शन 9.7 और उससे पहले के वर्शन

सही किए गए डुअल वैल्यू $-\infty$ होने पर, ज़्यादा काम की ड्यूअल वैल्यू पाने के लिए, हम एक ड्यूअल मकसद भी रिपोर्ट करते हैं जो मकसद की वैल्यू में मौजूद अनंत शब्दों को अनदेखा करता है. ड्यूअल रेज़िड्यूअल का मतलब, इनफ़ाइनाइट टर्म में तय किए गए 'इनफ़ाइनाइट टर्म' की वैल्यू के तौर पर $r$ है. अन्य कॉम्पोनेंट में इसकी वैल्यू 0 है और पीडीएलपी की वजह से हुई कम की गई लागत, दोनों कॉम्पोनेंट में तय की गई शर्तों के लिए $r$ की वैल्यू है. अन्य कॉम्पोनेंट में यह वैल्यू 0 होती है, यानी कि $r = \mbox{residuals} + \ resided.

वर्शन 9.8 और उसके बाद के वर्शन

सही किए गए डुअल वैल्यू $-\infty$ होने पर ज़्यादा सही ड्यूअल वैल्यू पाने के लिए, हम एक ड्यूअल मकसद भी रिपोर्ट करते हैं जो मकसद की वैल्यू में इनफ़ाइनाइट टर्म को सीमित मानों से बदल देता है: अगर एक बाउंड सीमा है, तो इंफ़ाइनाइट की जगह वह बाउंड इस्तेमाल किया जाता है; नहीं तो, बाउंड के लिए शून्य का इस्तेमाल किया जाता है. यह विकल्प दो मकसद की बारीकी को बनाए रखता है, लेकिन यह ज़रूरी नहीं है कि मकसद की वैल्यू की सीमा को कम रखा जाए. ड्यूअल रिज़िड्यूअल, सही किए गए ड्यूअल मकसद में अनंत शब्दों से $r$ की वैल्यू हैं. पीडीएलपी की मदद से, लौटाए गए पैसों में कमी $r$ होती है.

कुछ वैरिएबल बाउंड का इनफ़ाइनाइट के तौर पर इलाज

दोनों वर्शन में, अगर सॉल्वर विकल्प handle_some_primal_gradients_on_finite_bounds_as_residuals, true (डिफ़ॉल्ट तौर पर) है, तो ड्यूअल उद्देश्य और ड्यूअल रेज़िड्यूअल की गणना करते समय, अतिरिक्त वैरिएबल बाउंड को अनंत माना जा सकता है. खास तौर पर, अगर $|x_i - l^v_i| > |x_i|$, $l^v_i$ को अनंत वैल्यू की तरह माना जाता है. इसी तरह, अगर $|x_i - u^v_i| > |x_i|$, $u^v_i$ को अनंत मान लिया जाता है.

ध्यान दें कि handle_some_primal_gradients_on_finite_bounds_as_residuals के दिए गए फ़ॉर्मूला के आधार पर, उसके आकलन पर असर नहीं पड़ता है. इससे, सिर्फ़ दो मकसद और पहले से रिपोर्ट किए गए आंकड़ों पर असर पड़ता है.

स्केलिंग

मान लें कि हमें एक विकर्ण (कॉलम) का रीस्केलिंग मैट्रिक्स $C$ और एक विकर्ण (पंक्ति) रीस्केलिंग मैट्रिक्स $R$ दिया गया है, जिसमें विकर्ण पर पॉज़िटिव एंट्री हैं. ShardedQuadraticProgram::RescaleQuadraticProgram की तरह स्केलिंग को लागू करने पर, हमें ये बदलती समस्याएं मिलती हैं:

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

मूल समस्या का समाधान $x = C\tilde x$ के रूप में फिर से हासिल किया गया है. अगर $\tilde y$ एक दोहरा समाधान है और रूपांतरित समस्या के लिए $\tilde r$ कम लागत दे रहा है, तो $y = R\tilde y$ एक दोहरा समाधान है और मूल समस्या के लिए $r = C^{-1}\tilde r$ कम की गई लागत होती है (हटाई गई).

जोखिम की आशंका की पहचान

प्राइमल इंफ़सिबिलिटी का सर्टिफ़िकेट, पॉइंट $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ को संतुष्ट करता है:

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

ऐसे बिंदु के मौजूद होने का मतलब है कि इस शुरुआती समस्या में कोई समाधान नहीं होता.

इसी तरह, दोहरी अक्षमता का प्रमाणपत्र एक पॉइंट $x \in \mathbb{R}^n$ है, जैसे:

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

ध्यान दें कि लीनियर प्रोग्राम के सर्टिफ़िकेट $Q=0$ को सेट करके पाए जा सकते हैं.

  1. $S$ को $S = R^T R$ (उदाहरण के लिए, कोलेस्की फ़ैक्टराइज़ेशन के तौर पर फ़ैक्टराइज़ेशन) के तौर पर, सिमेट्रिक पॉज़िटिव सेमीडेफ़िनिट ऑब्जेक्ट मैट्रिक्स $S$ को इस फ़ॉर्म में बदला जा सकता है. $R x - z = 0$, कंस्ट्रेंट $R x - z = 0$ के हिसाब से तय किए गए अतिरिक्त वैरिएबल $z$ पेश किए जा रहे हैं, ताकि $x^T S x = z^↩