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$ ম্যাট্রিক্স 1 । উপরের আবদ্ধ ভেক্টর $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$ এর সংজ্ঞা প্রসারিত করে, আমরা শীর্ষে বর্ণিত দ্বৈতটি পাই।

স্যাডল-পয়েন্ট ফর্মুলেশন

প্রাথমিক-দ্বৈত হাইব্রিড গ্রেডিয়েন্ট ( চ্যাম্বোল এবং পক দেখুন) ফর্মের একটি প্রাথমিক সমস্যাকে লক্ষ্য করে

$$ \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 এর মধ্যে পরিবর্তিত হয়েছে। কোন সংস্করণটি প্রযোজ্য তা পরীক্ষা করতে, primal_dual_hybrid_gradient.h এ SolverResult::reduced_costs বর্ণনা করে মন্তব্যটি দেখুন এবং দেখুন এটি সংস্করণ 9.8 উল্লেখ করে কিনা।

সংস্করণ 9.7 এবং তার আগের

সংশোধিত দ্বৈত উদ্দেশ্য $-\infty$ হলে আরও অর্থপূর্ণ দ্বৈত মান পাওয়ার জন্য, আমরা একটি দ্বৈত উদ্দেশ্যও প্রতিবেদন করি যা উদ্দেশ্য মানের অসীম পদগুলিকে উপেক্ষা করে। দ্বৈত অবশিষ্টাংশ হল সংশোধন করা দ্বৈত উদ্দেশ্যের অসীম পদ থেকে $r$ এর মান, অন্যান্য উপাদানে 0 সহ, এবং PDLP দ্বারা প্রত্যাবর্তিত হ্রাসকৃত খরচ হল সংশোধন করা দ্বৈত উদ্দেশ্যের সীমাবদ্ধ পদ থেকে $r$ এর মান, অন্যান্য উপাদানে 0 সহ (যাতে $r = \mbox{residuals} + \mbox{reduced 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^TR$ হিসাবে ফ্যাক্টর করে (উদাহরণস্বরূপ, একটি চোলেস্কি ফ্যাক্টরাইজেশন), $R x - $R x - দ্বারা সংজ্ঞায়িত অতিরিক্ত চলক $z$ প্রবর্তন করে এই ফর্মটিতে রূপান্তর করা যেতে পারে। z = 0$, যাতে $x^TS x = z^T z$। ↩