پیشینه ریاضی برای PDLP

این صفحه حاوی پیش زمینه ریاضی برای توسعه دهندگان و کاربران پیشرفته PDLP است، یک حل کننده برنامه نویسی خطی و درجه دوم که در OR-Tools موجود است. این به عنوان مرجع برای بخش هایی از کد عمل می کند و قرار نیست به تنهایی خوانده شود. خوانندگان علاقه مند ابتدا باید خود را با مقاله " برنامه نویسی خطی در مقیاس بزرگ با استفاده از گرادیان ترکیبی اولیه-دوگانه " آشنا کنند، سپس به کد نگاه کنند، سپس زمانی که کد به آن ارجاع داد به این سند بازگردند.

اولیه

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 \times n$ و $Q$ یک ماتریس غیرمنفی $n \times n$ ¹ است. بردارهای کران بالا $u^{c}$ و $u^{v}$ دارای ورودی در $\mathbb{R} \cup \{ \infty\}$ و بردارهای کران پایین $l^{c}$ هستند. و $l^{v}$ ورودی‌هایی در $\mathbb{R} \cup \{ -\infty\}$ دارند. $l^{c} \le u^{c}$ و $l^{v} \le u^{v}$ را فرض می‌کنیم.

دوگانه

اجازه دهید $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 u^{c}$). بردار $r$ که هزینه‌های کاهش‌یافته نامیده می‌شود، حاوی ضرب‌کننده‌های دوگانه در محدودیت‌های محدود است ($l^{v} \le x \le u^{v}$).

$$ \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} \cup \{-\infty، \infty\}$.

اجازه دهید $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ تابع نشانگر بازه باشد، یعنی $\ mathcal{I}_{[a, b]}(x)$ صفر است وقتی که $x \in [a, b]$ و در غیر این صورت $\infty$ باشد.

$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{I}_{[l, u]} : \mathbb{R}^n \to \mathbb{R} \cup \{ \infty\}$ بطور مشابه $\mathcal{I} تعریف می‌شود _{[l,u]}(x) = \sum_{i=1}^n \mathcal{I}_{[l_i، u_i]}(x_i)$، و به طور مشابه $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 و Pock مراجعه کنید) یک مشکل اولیه شکل را هدف قرار می دهد.

$$ \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^TQ 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 در روشهای مرتبه اول در بهینه سازی را ببینید. عبارت به دست آمده توسط

$$ \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 بین OR-tools نسخه های 9.7 و 9.8 تغییر یافت. برای بررسی اینکه کدام نسخه اعمال می‌شود، نظری را که SolverResult::reduced_costs در primal_dual_hybrid_gradient.h توضیح می‌دهد، بررسی کنید و ببینید آیا در آن به نسخه 9.8 اشاره شده است یا خیر.

نسخه 9.7 و قبل از آن

برای اینکه زمانی که هدف دوگانه اصلاح شده $-\infty$ است، ارزش دوگانه معنی‌داری داشته باشیم، یک هدف دوگانه را نیز گزارش می‌کنیم که عبارت‌های نامحدود در مقدار هدف را نادیده می‌گیرد. باقیمانده‌های دوگانه مقادیر $r$ از جمله‌های نامتناهی در هدف دوگانه اصلاح‌شده، با 0 در سایر مؤلفه‌ها هستند، و هزینه‌های کاهش‌یافته‌ای که توسط PDLP برمی‌گردند، مقادیر r$ از جمله‌های محدود در هدف دوگانه اصلاح‌شده هستند. با 0 در اجزای دیگر (به طوری که $r = \mbox{residuals} + \mbox{کاهش هزینه}$).

نسخه 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^TR$ (به عنوان مثال، فاکتورسازی Cholesky)، با معرفی متغیرهای اضافی $z$ تعریف شده توسط محدودیت $R x - به این شکل تبدیل کرد. z = 0$، به طوری که $x^TS x = z^T z$. ↩