PDLP 的数学背景

本页面包含面向开发者和高级用户的 PDLP（OR 工具中提供的线性和二次编程求解器）的数学背景。它只供代码部分参考，不适合自行阅读。感兴趣的读者应先熟悉一下《Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient》这篇论文，然后查看代码，然后在代码引用时再回来查阅本文档。

原初

PDLP 考虑以下凸二次规划问题，

min

其中 A 为 m\times n 矩阵，Q 为对角非负 n\times n 矩阵1。上限向量 u^{c} 和 u^{v} 包含 \Mathbb{R} \cup \{ \infty\} 中的条目，下限向量 l^{c} 和 l^{v} 的条目假设为 $\Mathbb{R} \cup \{le ^v{le ^v{le ^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 ^le {xl} ^le } ^le 约束条件）。

\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-term 是有限的，则我们说 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,in

以 \Mathcal{I}_{[a, b]} : \Mathbb{R}\to \Mathbb{R} \cup \{ \infty\} 为区间的指示函数，即当 x \in [a, b] 时，\Mathcal{I}_{[a, b]}(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)^* 表示凸共振。

对 l \subseteq (\Mathbb{R} \cup \{-\infty\})^n 和 u \subseteq (\Mathbb{R} \cup \{\infty\})^n，指示函数 $\Mathcal{I}_{[l, u]} 数学符号 \ux{1} \ux_cal{1} \ux_sum_{1] \ux_cal{1} \u x y {1} 数学符号 \ux{x

衍生

在引入辅助变量 \tilde \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 的域。

请注意，在 PDLP 假设 Q 为对角线的情况下，g 的邻近运算符可计算为闭合形式，这是因为 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。校正的双目标是对对二问题的目标值，但代价为有限且不小于零的下限，且始终为小于零的值

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}{residuals}）。

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^T R（例如，Cholesky 因式分解），引入由约束 R x - z = 0 定义的额外变量 z，以便 x^T S x = z^T z。↩