רקע מתמטי ל-PDLP

דף זה מכיל רקע מתמטי למפתחים ולמשתמשים מתקדמים של PDLP, פתרון תכנות לינארי וריבועי שזמין ב-OR-Tools. הוא משמש כהפניה לחלקים של הקוד, והוא לא מיועד לקריאה בפני עצמו. קוראים מעוניינים יוכלו תחילה להכיר את המאמר "Practical Large-Scale Linear Program with Primal-Dual Hybrid Gradient", לאחר מכן לעיין בקוד ולחזור למסמך הזה כשהקוד מתייחס אליו.

ראשוני

ב-PDLP, נלקחת בחשבון בעיית התכנות הריבועית הקמורה הבאה,

$$ \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\tims n$ ו-$Q$ היא מטריצה לא שלילית של $n\times n$ ¹. בווקטורים של הגבול העליון $u^{c}$ ו-$u^{v}$ יש ערכים ב$\mathbb{R} \cup \{ \infty\}$, ובוקטורים של הגבול התחתון $l^{c}$ ו-$l^{v}$ יש ערכים ב-$\mathbb{R} \cup \{ -\infty\$}

כפול

הפונקציה $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 \le$ אפשר למצוא את הנקודות הלינאריות שנקראות $l^{c} \le Ax \le$ ) .

$$ \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$ באובייקט הוא סופי, כלומר:

$$ 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} \cupy \{-\infty,

$\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ פונקציית האינדיקטור של המרווח, כלומר $\mathcal{I}_{[a, b]}(x)$ שווה לאפס אם $x, \iny$ ו-$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)^*$ מציין את הצימוד הקמור.

For vectors $l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ and $u \subseteq (\mathbb{R} \cup \{\infty\})^n$, the indicator function $\mathcal{I}_{[l, u]} : \mathbb{R}^n \to \mathbb{R} \cup \{ \infty\}$ is defined analogously as $\mathcal{I}_{[l,u]}(x) = \sum_{i=1}^n \mathcal{I}_{[l_i, u_i]}(x_i)$, and similarly $p(y; l, u) = (\mathcal{I}_{[l, u]})^*(y) = \sum_{i=1}^n p(y_i; l_i, u_i)$.

גזירה

אנחנו מציגים את משתני העזר $\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$, אנחנו מקבלים את הכפול שמופיע למעלה.

הרכבה על בסיס אוכף

הדרגה היברידית דו-צדדית (ראו Chambolle ו-Pok) ממוקדת לבעיה ראשונית בצורה

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

טכנולוגיית PDLP מאלצת את בעיית התכנות הריבועית הקמורה לתוך הפורמט הזה על ידי הגדרה:

• $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$ בצורה סגורה בהנחה של PDLP ש-$Q$ הוא באלכסון, על סמך העובדה ש-$g$ הוא מפריד ואת המאפיין הבא שמחזיק בכל הפונקציות $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 בקטע First-Order Methods in Optimization (שיטות הזמנה ראשונה באופטימיזציה). הביטוי שמתקבל נקבע על ידי

$$ \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$ כשיש עלות שאינה אפס.

העלויות המופחתות והיעד הכפול שדווחו על ידי PDLP השתנו בגרסאות 9.7 ו-9.8 של הכלים OR. כדי לבדוק איזו גרסה רלוונטית, צריך לבדוק את התגובה עם תיאור SolverResult::reduced_costs ב-primal_dual_hybrid_gradient.h ולבדוק אם מצוינת בה גרסה 9.8.

גרסה 9.7 ומטה

כדי לקבל ערך כפול משמעותי יותר כשהיעד הכפול המתוקן הוא $-\infty$, אנחנו מדווחים גם על מטרה כפולה שמתעלמת מן האיברים האינסופיים שבערך האובייקט. שאריות הכפולות הן הערכים של $r$ ממונחים אינסופיים ביעד הכפול המתוקן, עם 0 בשאר הרכיבים, והעלויות המופחתות שהוחזרו על ידי PDLP הן הערכים של $r$ מהמונחים הסופיים במטרה הכפולה המתוקנת, עם 0 בשאר הרכיבים (כך ש $r = \mbox{residual costs} + .

גרסה 9.8 ואילך

כדי לקבל ערך כפול משמעותי יותר כשהמטרה הכפולה המתוקנת היא $-\infty$, אנחנו מדווחים גם על מטרה כפולה שמחליפה את האיברים האינסופיים שבערך האובייקטיבי בגבולות הסופיים, באופן הבא: אם אחד מהגבולות הוא סופי, הוא משמש במקום הגבול האינסופי. אחרת, משתמשים באפס עבור הגבול. הבחירה הזו משמרת את הקיעור של המטרה הכפולה, אבל לא בהכרח יוצרת גבול תחתון לערך האובייקט. שאריות הכפולות הן הערכים של $r$ מאיברים אינסופיים באובייקט הכפול המתוקן. העלויות המופחתות שהוחזרו על ידי PDLP הן $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$ כ-$S = R^T R$ (לדוגמה, פירוק לגורמים של Cholesky), ולהוסיף משתנים נוספים $z$ המוגדרים על ידי האילוצים $R x - z = 0$, כך ש-$x^T S x = $ z^T↩