خلفية رياضية لميزة "منع فقدان البيانات"

تحتوي هذه الصفحة على خلفية رياضية للمطوِّرين والمستخدمين المتقدِّمين لميزة PDLP، وهي أداة لحلّ البرمجة الخطية والتربيعية المتوفّرة في أدوات OR. إنها بمثابة مرجع لأجزاء من التعليمات البرمجية وليس الغرض منها قراءتها من تلقاء نفسها. يجب أن يطّلع القرّاء المهتمّون أولاً على البحث بعنوان "ممارسة البرمجة الخطية على نطاق واسع باستخدام التدرّج الأولي-الثنائي المختلط"، ثم الاطّلاع على الرمز البرمجي ثم العودة إليه عند إشارة الرمز إليه.

أساسي

تراعي 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 \tعدد n$ و $Q$ هي مصفوفة $n \tمرات n$ غير سالبة¹. يحتوي المتجهان ذوا الحد الأعلى $u^{c}$ و$u^{v}$ على إدخالات في $\mathbb{R} \cup \{ \infty\}$، والمتجهات ذات الحد السفلي $l^{c}$ و$l^{v}$ لهما إدخالات في $\mathbb{R} \cup \{$l} y. {$cup} \{$c} y.

زوجي

لنفترض أن $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 {rlid, The rbound} $d Ax { \$ 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} $$

عندما يكون $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 {R} \cup \{$}

دع $\mathcal{I}_{[a, b]} : \mathbb{R}\to \mathbb{R} \cup \{ \infty\}$ هي دالة المؤشر للفاصل، أي، $\mathcal{I}_{[a, b]}(x)$ هي صفر [a, \in]$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)^*$ إلى المرافق المحدبة.

(\mathbb{R} \cup \{-\infty\})^n$ و$u \subseteq (\mathbb{R} \cup \{\infty\})^n$، {\infty\})^n$، {$\mathcal\cup \cup \{-\infty\})^n$ و$u \subseteq (\mathbb{R} \cup \{\infty\})^n$، {\infty\})^n$، {$\mathcal\cup} =${i}\cup {[l, . \t_ma}

الاشتقاق

عند تقديم المتغيرات الإضافية $\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^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 في طرق الترتيب الأول في التحسين. يتم التعبير عن التعبير الناتج من خلال

$$ \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-tools. لمعرفة الإصدار المناسب، راجِع التعليق الذي يصف SolverResult::reduced_costs في primal_dual_hybrid_gradient.h وما إذا كان يذكر الإصدار 9.8.

الإصدار 9.7 والإصدارات الأقدم

للحصول على قيمة مزدوجة أكثر أهمية عندما يكون الهدف المزدوج الذي تم تصحيحه هو $-\infty$، نبلغ أيضًا عن هدف ثنائي يتجاهل المصطلحات اللانهائية في القيمة الهدف. القيمتان المتبقّية المتبقية هي قيم $r$ من المصطلحات اللانهائية في الهدف الثنائي الذي تم تصحيحه، مع 0 في المكوّنات الأخرى، وتمثّل التكاليف المخفّضة التي تعرضها PDLP قيم $r$ من الشروط المحدودة في الهدف الثنائي الذي تم تصحيحه، بحيث تكون القيمة 0 في المكونات الأخرى (بحيث $r = \mbox {residuals}{residual}).

الإصدار 9.8 والإصدارات الأحدث

للحصول على قيمة مزدوجة أكثر وضوحًا عندما يكون الهدف الثنائي الذي تم تصحيحه هو $-\infty$، نبلغ أيضًا عن هدف ثنائي يستبدل العبارات اللانهائية في القيمة الهدف بأخرى محدودة على النحو التالي: إذا كان أحد الحدود محدودًا، يتم استخدام هذا الحد بدلاً من الحد اللانهائي، وإلا يتم استخدام الصفر مع الحد. يحافظ هذا الاختيار على تقعر الهدف المزدوج، لكنه لا يعطي بالضرورة حدًا أدنى على القيمة الموضوعية. المخلفات المزدوجة هي قيم $r$ من المصطلحات اللانهائية في الهدف الثنائي الذي يتم تصحيحه. تبلغ التكاليف المخفّضة التي تؤديها ميزة PDLP دولار أمريكي (أو ما يعادلها بالعملة المحلية).

التعامل مع بعض الحدود المتغيّرة على أنّها لانهائية

في كلا الإصدارين، إذا كان خيار الحلّ 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$ (على سبيل المثال، تحليل Colsky)، وتقديم متغيرات إضافية $z$ محدّدة بقيود $R x - z = 0$، بحيث $x^T S x = z^T z$.