หน้านี้มีข้อมูลเบื้องต้นทางคณิตศาสตร์สำหรับนักพัฒนาและผู้ใช้ขั้นสูงของ PDLP ซึ่งเป็นโปรแกรมแก้โจทย์การเขียนโปรแกรมเชิงเส้นและเลขยกกำลังสองที่มีอยู่ในเครื่องมือ OR โดยทำหน้าที่เป็นข้อมูลอ้างอิงสำหรับส่วนของโค้ดและไม่ได้มีไว้เพื่ออ่านด้วยตัวเอง ผู้อ่านที่สนใจควรทำความคุ้นเคยกับบทความ "Practical Large-Scale Linear Programming โดยใช้ Primal-Dual Hybrid Gradient" จากนั้นดูโค้ด จากนั้นกลับมาที่เอกสารนี้เมื่อโค้ดอ้างอิงถึง
ปฐม
PDLP จะพิจารณาปัญหาการเขียนโปรแกรมกำลังสองแบบนูน
โดยที่ $A$ คือเมทริกซ์ $m \times n$ และ $Q$ คือเมทริกซ์ $n \times n$ ในแนวทแยง1 เวกเตอร์ขอบเขตบน $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} ใน
เมื่อ $Q = 0$ จะสามารถตัด $x$ ออกจากการทำงานคู่ ซึ่งก็คือการกู้คืน LP duality
ขอบเขตตัวแปรแบบคู่
เราว่า $y$ เป็นไปตามขอบเขตตัวแปรคู่หากคํา $y$- ในวัตถุประสงค์มีจํานวนเต็ม นั่นคือ
อนุพันธ์โดยใช้คู่สังยุค
รอบคัดเลือก
ให้ $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\}$ เป็น
เมื่อ $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$ เราจะระบุปัญหาเบื้องต้นดังนี้
การปรับข้อจำกัดความเท่าเทียมให้เป็นเท่าตัว เราได้รับสิ่งต่อไปนี้
การแลกเปลี่ยนค่าต่ำสุดกับค่าสูงสุดและการจัดกลุ่มใหม่:
การสลายตัวร่วมต่อ $x$, $\tilde x$ และ $\tilde a$ สำหรับ $x$ เราจะเห็นว่าค่าย่อ (หากมี) เป็นไปตาม $Qx + c - A^Ty = r$ ซึ่งในกรณีนี้ ค่าขั้นต่ำคือ $-\frac{1}{2} x^TQx$ สำหรับ $\tilde x$ และ $\tilde a$ เราจะใช้ คำจำกัดความของคอนจูเกตแบบนูนที่มีการปรับเปลี่ยนเล็กน้อยสำหรับสัญลักษณ์
ซึ่งจะให้ผลการดำเนินการทั้ง 2 อย่างดังนี้
การขยายคำจำกัดความของ $p$ ทำให้เราได้รับค่าคู่ตามที่ระบุไว้ที่ด้านบน
การกำหนดแบบ Saddle Point
การไล่ระดับสีแบบไฮบริด-คู่แบบ Primal-dual (ดู Chambolle และ Pock) กำหนดเป้าหมาย ปัญหาหลักของรูปแบบ
โดยสังยุคทวิภาคเท่ากับโจทย์รูปอานม้า
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$
ดูตัวอย่างข้อเท็จจริงนี้ได้เลย เช่น ทฤษฎีบท 6.13 ในวิธีการเพิ่มประสิทธิภาพลำดับแรก นิพจน์ที่ได้จะกำหนดโดย
ต้นทุนที่ลดลง ความคลาดเคลื่อนแบบคู่ และวัตถุประสงค์คู่ที่แก้ไขแล้ว
การกำหนดจุดอานหลักจะใช้ได้เฉพาะกับ $(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
เราได้รับปัญหาที่มีการเปลี่ยนรูปแบบดังต่อไปนี้
การแก้ไขปัญหาเดิมจะได้รับการกู้คืนเป็น $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$ ตามความพึงพอใจ:
การมีอยู่ของจุดนี้บอกเป็นนัยว่าปัญหาหลักไม่มีวิธีแก้ไข
ในทำนองเดียวกัน ใบรับรองความสามารถในการใช้งานควบคู่กันไม่ได้คือจุด $x \in \mathbb{R}^n$ โดยมีตัวอย่างดังนี้
โปรดทราบว่าใบรับรองสำหรับโปรแกรมเชิงเส้นสามารถรับได้โดยการตั้งค่า $Q=0$