Nền toán học cho PDLP

Trang này cung cấp kiến thức toán học dành cho các nhà phát triển và người dùng nâng cao của PDLP – một trình giải quyết lập trình tuyến tính và bậc hai có trong OR-Tools. Mã này đóng vai trò là tài liệu tham khảo cho các phần của mã và không để độc giả đọc riêng. Trước tiên, những độc giả quan tâm nên làm quen với bài viết "Thực hành lập trình tuyến tính trên quy mô lớn thực tế bằng cách sử dụng Primal-Dual Hybrid Gradient", sau đó xem mã rồi quay lại tài liệu này khi mã tham chiếu đến mã.

Gốc

PDLP xem xét vấn đề lập trình bậc hai lồi sau,

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

trong đó $A$ là ma trận $m \times n$ và $Q$ là một đường chéo không âm $n \times n$ ma trận¹. Vectơ giới hạn trên $u^{c}$ và $u^{v}$ có các mục nhập bằng $\mathbb{R} \cup \{ \infty\}$, còn vectơ giới hạn dưới $l^{c}$ và $l^{v}$ có mục nhập trong $\mathbb{R} \cup \{ -\infty$\c}. Chúng ta giả sử $\u^l\c}.

Đôi

Đặt $a \in \mathbb{R}$. Đặt $[a]_+$ biểu thị phần dương và $[a]_-$ biểu thị phần âm, nghĩa là $a = [a]_+ - [a]_-$. Khi áp dụng cho vectơ, phần dương và phần âm được tính theo phần tử.

Kép của bài toán nguyên hàm trước đó là trên $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$, và $r \in \mathbb{R}^n$. Vectơ $y$ chứa các nhân kép trên các giới hạn tuyến tính ($l^{c} \le Ax \$ u^{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} $$

Khi $Q = 0$, $x$ có thể bị loại bỏ khỏi kép, khôi phục tính năng kép LP.

Giới hạn của biến kép

Chúng ta nói rằng $y$ đáp ứng các giới hạn của biến kép nếu $y$-term trong mục tiêu là hữu hạn, tức là:

$$ y_i \geq 0 \qquad \text{if }u^c_i = \infty, \\ y_i \leq 0 \qquad \text{if }l^c_i = -\infty. $$

Đạo hàm bằng cách sử dụng phép đối ngẫu liên hợp

Đấu loại

Giả sử $a \in \mathbb{R} \cup \{-\infty\}$ và $b \in \mathbb{R} \cup \{\infty\}$ với $b \ge a$ và tính khoảng $[a, b] \subseteq \mathbb{R} \cup \infty,

Đặt $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ là hàm chỉ báo của khoảng, nghĩa là $\mathcal{I}_{[a, b]}(x)$ là 0 khi $x \b]$ và $\ftin [a]

Định nghĩa $p(y; a, b): \mathbb{R} \to \mathbb{R} \cup \{\infty\}$ dưới dạng:

$$ p(y; a, b) = \begin{cases} ay & \text{ if } y < 0 \\ 0 & \text{ if } y = 0 \\ by & \text{ if } y > 0 \end{cases}. $$

Khi $a$ hoặc $b$ là vô hạn, hãy tuân theo số học thực mở rộng tiêu chuẩn.

Kết quả cơ bản: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$ trong đó $(\cdot)^*$ biểu thị liên hợp lồi.

Với vectơ $l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ và $u \subseteq (\mathbb{R} \cup \{\infty\})^n$, hàm chỉ báo $\mathcal{I}_{l,u]}

Đạo hàm

Ra mắt các biến phụ $\tilde a \in \mathbb{R}^m$ và $\tilde x \in \mathbb{R}^n$, chúng ta trình bày lại bài toán nguyên thuỷ như sau:

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

kép các điều kiện ràng buộc bằng nhau, chúng ta sẽ có:

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

Đổi giá trị tối thiểu với giá trị tối đa và giá trị ghi nhớ:

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

Việc giảm thiểu sự kết hợp trên $x$, $\tilde x$ và $\tilde a$ bị phân huỷ. Đối với $x$, chúng ta thấy một trình tối thiểu (nếu có) thoả mãn $Qx + c - A^Ty = r$, trong trường hợp này, giá trị nhỏ nhất là $-\frac{1}{2} x^TQx$. Với $\tilde x$ và $\tilde a$, chúng tôi áp dụng định nghĩa liên kết lồi với các điều chỉnh nhỏ cho các dấu.

Điều này tạo ra đối tượng kép:

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

Bằng cách mở rộng định nghĩa $p$, chúng ta sẽ có được đối tượng kép nêu ở trên cùng.

Công thức tính điểm yên

Chế độ chuyển màu kết hợp kép chính (xem Chambolle và Pock) sẽ nhắm đến một vấn đề cơ bản của biểu mẫu

$$ \begin{align} \min_x f(x) + g(x) + h(Kx) \end{align} $$

mà theo tính nhị phân liên hợp tương đương với bài toán điểm yên

$$ \begin{align} \min_x \max_y f(x) + g(x) + y^TKx - h^*(y) \end{align} $$

PDLP ép buộc bài toán lập trình bậc hai lồi thành biểu mẫu này bằng cách thiết lập:

• $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$

Như đạo hàm trước đó, $h^*(y) = p(y; -u^c,-l^c)$ là một hàm lồi tuyến tính xác định theo từng khoảng. Cả $g$ và $h^*$ đều có thể nhận các giá trị vô hạn, nhờ đó giới hạn các miền tương ứng của $x$ và $y$ một cách hiệu quả.

Xin lưu ý rằng toán tử gần của $g$ có thể tính được ở dạng đóng theo giả định của PDLP là đường chéo, sử dụng thực tế là $g$ có thể phân tách được và thuộc tính sau đây dành cho mọi hàm $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). $$

Để chứng minh điều này, hãy xem ví dụ về Định lý 6.13 trong Phương thức bậc nhất trong tính năng tối ưu hoá. Biểu thức kết quả được đưa ra bởi

$$ \begin{equation} \mathrm{prox}_{\lambda g}(x) = \mathrm{proj}_{[l^v, u^v]}\left( (I + \lambda Q)^{-1} (x - \lambda c) \right) \end{equation} $$

Giảm chi phí, dư nợ kép và mục tiêu kép đã được điều chỉnh

Công thức điểm yên chỉ hoạt động rõ ràng với $(x,y)$; chi phí giảm $r$ được ngầm định. Để trả về $(x,y,r)$ khi giải công thức điểm yên, chúng ta xác định $r$ là $r = Qx + c - A^Ty$. Mục tiêu kép đã sửa là giá trị mục tiêu của bài toán kép và luôn cho giới hạn dưới đối với giá trị mục tiêu, nhưng $-\infty$ bất cứ khi nào có chi phí khác 0.

Chi phí giảm và mục tiêu kép do PDLP báo cáo đã được thay đổi giữa công cụ OR phiên bản 9.7 và 9.8. Để kiểm tra xem phiên bản nào áp dụng, hãy kiểm tra bình luận mô tả SolverResult::reduced_costs trong primal_dual_hybrid_gradient.h và xem bình luận đó có đề cập đến phiên bản 9.8 hay không.

Phiên bản 9.7 trở xuống

Để có giá trị kép có ý nghĩa hơn khi mục tiêu kép đã sửa là $-\infty$, chúng ta cũng báo cáo một mục tiêu kép bỏ qua các số hạng vô hạn trong giá trị mục tiêu. Phần dư kép là các giá trị của $r$ từ các số hạng vô hạn trong mục tiêu kép đã sửa, với 0 trong các thành phần khác và chi phí giảm do PDLP trả về là các giá trị của $r$ từ các số hạng hữu hạn trong mục tiêu kép đã hiệu chỉnh, với 0 trong các thành phần khác (để $r = \mbox{residuals} + }$r = $

Phiên bản 9.8 trở lên

Để có giá trị kép có ý nghĩa hơn khi mục tiêu kép đã sửa là $-\infty$, chúng tôi cũng báo cáo một mục tiêu kép thay thế các điều kiện vô hạn trong giá trị mục tiêu bằng các giới hạn hữu hạn như sau: nếu một trong các giới hạn là hữu hạn, giới hạn đó sẽ được dùng thay cho giới hạn vô hạn; nếu không, giới hạn đó sẽ được dùng thay cho giới hạn đó. Lựa chọn này giúp đảm bảo độ lõm của mục tiêu kép, nhưng không nhất thiết đem lại giới hạn thấp hơn cho giá trị mục tiêu. Phần dư kép là giá trị của $r$ từ các số hạng vô hạn trong mục tiêu kép đã hiệu chỉnh. Chi phí giảm mà PDLP trả về là r$.

Xử lý một số giới hạn thay đổi là vô hạn

Trong cả hai phiên bản, nếu lựa chọn trình giải handle_some_primal_gradients_on_finite_bounds_as_residuals là true (mặc định), thì các giới hạn biến bổ sung có thể được coi là vô hạn khi tính toán mục tiêu kép và phần dư kép. Cụ thể, nếu $|x_i – l^v_i| > |x_i|$, thì $l^v_i$ được xử lý như là vô hạn, và tương tự nếu $|x_i - u^v_i| > |x_i|$, $u^v_i$ được xử lý như là vô hạn.

Xin lưu ý rằng handle_some_primal_gradients_on_finite_bounds_as_residuals không ảnh hưởng đến các vòng lặp được tính toán; nó chỉ ảnh hưởng đến mục tiêu kép và phần còn lại được dùng trong các thử nghiệm chấm dứt cũng như số liệu thống kê được báo cáo.

Điều chỉnh quy mô

Giả sử chúng ta được cung cấp một ma trận đổi tỷ lệ đường chéo (cột) $C$ và một ma trận đổi tỷ lệ đường chéo (hàng) $R$ có các phần tử dương trên đường chéo. Áp dụng việc đổi tỷ lệ như trong ShardedQuadraticProgram::RescaleQuadraticProgram, chúng ta nhận được vấn đề đã chuyển đổi sau:

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

Nghiệm cho bài toán ban đầu được khôi phục dưới dạng $x = C\tilde x$. Nếu $\tilde y$ là một nghiệm kép và $\tilde r$ giảm chi phí cho bài toán biến đổi, thì $y = R\tilde y$ là một nghiệm kép và $r = C^{-1}\tilde r$ giảm chi phí cho bài toán ban đầu (dẫn xuất).

Xác định yếu tố không khả thi

Chứng chỉ tính không khả thi nguyên thuỷ là một điểm $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ thoả mã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} $$

Sự tồn tại của một điểm như vậy ngụ ý rằng vấn đề nguyên thuỷ không có giải pháp.

Tương tự, chứng chỉ không có khả năng kép là một điểm $x \in \mathbb{R}^n$ sao cho:

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

Xin lưu ý rằng bạn có thể lấy chứng chỉ cho chương trình tuyến tính bằng cách đặt $Q=0$.

---

1. Bạn có thể chuyển đổi một ma trận mục tiêu bán xác định dương đối xứng $S$ thành dạng này bằng cách lấy $S$ thành $S = R^T R$ (ví dụ: thừa số Cholesky), giới thiệu các biến bổ sung $z$ được xác định trong các điều kiện ràng buộc $R x - z = 0$, để $x^T S x = z^T z$. ↩