พื้นหลังทางคณิตศาสตร์สําหรับ PDLP

หน้านี้มีข้อมูลเบื้องต้นทางคณิตศาสตร์สำหรับนักพัฒนาและผู้ใช้ขั้นสูงของ PDLP ซึ่งเป็นโปรแกรมแก้โจทย์การเขียนโปรแกรมเชิงเส้นและเลขยกกำลังสองที่มีอยู่ในเครื่องมือ OR โดยทำหน้าที่เป็นข้อมูลอ้างอิงสำหรับส่วนของโค้ดและไม่ได้มีไว้เพื่ออ่านด้วยตัวเอง ผู้อ่านที่สนใจควรทำความคุ้นเคยกับบทความ "Practical Large-Scale Linear Programming โดยใช้ 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 \times n$ และ $Q$ คือเมทริกซ์ $n \times n$ ในแนวทแยง¹ เวกเตอร์ขอบเขตบน $u^{c}$ และ $u^{v}$ มีรายการใน $\mathbb{R} \cup \{ \infty\}$ และเวกเตอร์ขอบเขตล่าง $l^{c}$ และ $l^{v}$ มีรายการใน $\mathbb{R} \^v} และ $^l\infty{R} \{uv} {^le -\infty{R} {cup}

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$ มีตัวคูณร่วมคู่ใน \mathbb{R}^n$, $y \in \mathbb{R}^{c} ใน

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

ขอบเขตตัวแปรแบบคู่

เราว่า $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, \in \y]

นิยาม $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\})

แหล่งที่มา

ขอแนะนำตัวแปรเสริม $\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$ เราจะใช้ คำจำกัดความของคอนจูเกตแบบนูนที่มีการปรับเปลี่ยนเล็กน้อยสำหรับสัญลักษณ์

ซึ่งจะให้ผลการดำเนินการทั้ง 2 อย่างดังนี้

$$ \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$ ทำให้เราได้รับค่าคู่ตามที่ระบุไว้ที่ด้านบน

การกำหนดแบบ Saddle Point

การไล่ระดับสีแบบไฮบริด-คู่แบบ Primal-dual (ดู 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)$ เป็นฟังก์ชัน Convex เชิงเส้นแบบทีละส่วน ทั้ง $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 ถึงเวอร์ชัน 9.7 และ 9.8 หากต้องการตรวจสอบว่าใช้เวอร์ชันใด ให้ตรวจสอบความคิดเห็นที่กล่าวถึง SolverResult::reduced_costs ใน primal_dual_hybrid_gradient.h และดูว่าพูดถึงเวอร์ชัน 9.8 ไหม

เวอร์ชัน 9.7 และเก่ากว่า

นอกจากนี้เรายังรายงานวัตถุประสงค์คู่ซึ่งจะไม่สนใจคำศัพท์ที่ไม่จำกัดในค่าวัตถุประสงค์ เพื่อให้ค่าคู่ที่มีความหมายยิ่งขึ้นเมื่อวัตถุประสงค์แบบคู่ที่แก้ไขคือ $-\infty$ ส่วนที่เหลือคู่คือค่าของ $r$ จากคำที่ไม่สิ้นสุดในวัตถุประสงค์คู่ที่แก้ไขแล้ว โดยที่ 0 อยู่ในองค์ประกอบอื่นๆ และต้นทุนที่ลดลงที่ PDLP แสดงคือ $r$ จากข้อกำหนดที่แน่นอนในวัตถุประสงค์คู่ที่แก้ไขแล้ว โดยมี 0 ในองค์ประกอบอื่นๆ (เพื่อให้ $r = \mbox}{residual} มีค่าเป็น 0 บาท)

เวอร์ชัน 9.8 ขึ้นไป

เพื่อให้ได้ค่าคู่ที่มีความหมายยิ่งขึ้นเมื่อวัตถุประสงค์คู่ที่แก้ไขแล้วเป็น $-\infty$ เราจะรายงานวัตถุประสงค์คู่ ซึ่งจะแทนที่คำศัพท์ที่เป็นอนันต์ในค่าวัตถุประสงค์ด้วยค่าจำกัด ดังนี้ หากขอบเขตใดขอบเขตหนึ่งมีขีดจำกัด ระบบจะใช้ขอบเขตนั้นแทนขอบเขตอนันต์ มิเช่นนั้นจะใช้ 0 สำหรับขอบเขต ตัวเลือกนี้จะคงความเว้าของวัตถุประสงค์คู่ไว้ แต่ไม่จำเป็นต้องให้ขอบเขตล่างของค่าวัตถุประสงค์ เศษเหลือคู่คือค่าของ $r$ จากพจน์ที่ไม่จำกัดในอ็อบเจ็กต์คู่ที่แก้ไขแล้ว ค่าใช้จ่ายที่ลดลงซึ่ง PDLP ส่งคืนคือ $r$

การจัดการขอบเขตตัวแปรบางอย่างแบบไม่รู้จบ

ในทั้ง 2 เวอร์ชัน หากตัวเลือกเครื่องมือแก้โจทย์ 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}\t จะลดต้นทุนให้กับปัญหาเดิมที่ตัดออก)

การระบุถึงความยากง่าย

ใบรับรองว่าไม่สามารถป้องกันความผิดพลาดขั้นต้นคือคะแนน $(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 - = 0$ เพื่อให้ $x^T S x = z^T