PDLP 的数学背景

本页面包含面向开发者和高级用户的 PDLP（OR 工具中提供的线性和二次编程求解器）的数学背景。它只供代码部分参考，不适合自行阅读。感兴趣的读者应先熟悉一下《Practical Large-Scale Linear Programming using 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$ 矩阵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$。↩