PDLP の数学的背景

このページでは、OR-Tools で使用できる線形および二次プログラミング ソルバーである PDLP のデベロッパーと上級ユーザー向けに、数学的背景について説明します。コードの一部を参照するための参考情報であり、それ自体で読むことは想定されていません。興味を持たれた読者の方は、まず論文「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 \\ } と ${l{l^c} と仮定します。

二重

$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} \u{vector \$} という線形制約に対する二重乗数が含まれます）です。

$$ \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$ 項が有限である場合、$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\}, $ を考えてみましょう。

区間のインジケーター関数 $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$

$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 serviceAccount-\infty\})^n$ と $u \subseteq \cup \{\infty\})^n$ について、次のベクトル関数 $\mathcal{I}_{[l, u]} : \mathbb{R}

導出

補助変数 $\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$ における同時最小化は分解します。

これにより、

$$ \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$ のドメインを制限します。

$g$ の近似演算子は、$g$ が分離可能であることと、任意の関数 $f_1、f_2$ で保持される次のプロパティを使用して、$Q$ が対角線であると PDLP が前提としている閉形式で計算できます。

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

この事実を証明するには、たとえば、最適化における 1 次手法の定理 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-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 + {reiduals} となります）。

バージョン 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$ と因数分解（たとえばコレスキー因数分解）、制約 $R x - z = 0$ によって定義される追加の変数 $z$ を導入することで、この形式に変換できます。つまり、$x^T S x = z^T です。↩