本当は便利な相補性定理

この記事は数理最適化 Advent Calendar 2024の25日目の記事です．

はじめに

線形計画問題をはじめとする制約付き最適化問題には相補性 (complementarity) とよばれる性質があります．相補性は解の最適性条件を与えるものですが，実は主双対の枠組みを通して最適解「全体」を捉えることができるという非常に強力な帰結が存在します．本記事では，線形計画問題における相補性定理の説明とそれを用いて最適解全体を捉える方法，また組合せ最適化での例を紹介します．

準備

線形計画問題

目的関数も制約もどちらも線形であるような最適化問題を線形計画問題 (linear programming^[1]; LP) とよびます．とくに，$m$ 次元ベクトル $b \in \mathbb{R}^m$，$n$ 次元ベクトル $c \in \mathbb{R}^n$，$m \times n$ 行列 $A \in \mathbb{R}^{m \times n}$ によって定まる，$x \in \R^n$を変数とする以下の形式の問題 (P)

$$\tag{P} \begin{array}{ll} \text{maximize} & c^\top x \\ \text{subject to} & Ax \le b, \\ & x \ge 0 \end{array}$$

を不等式標準形 (standard inequality form) とよびます．ここで $c^\top$ は $c$ の転置です．また，ベクトル $u,v \in \mathbb{R}^d$に対する不等式 $u \le v$ は，すべての $i = 1, \dotsc, d$ について $u_i \le v_i$ であるという条件を意味すると約束します．解 $x \in \R^n$ は問題 (P) の制約を満たすときに実行可能 (feasible)，そうでないときに実行不可能 (infeasible) であるといわれます．また，実行可能解がある（ない）ときに問題 (P) そのものを実行（不）可能といいます．実行可能解であって最大を達成するものを最適 (optimal) とよびます．実行可能解全体を実行可能領域 (feasible region) とよびます．LPの実行可能領域は各制約が表す半空間の共通部分として得られる多面体となります．

不等式標準形は以下で説明する双対問題も対称的な形式を持ち，またすべてのLPは適切に変数を導入したりすることで不等式標準形に変形することができるので，本稿では不等式標準形のLPを考えます．

なお，線形計画問題は楕円体法や内点法などの手法により多項式時間で解く（最適解を得る）ことができます．最も有名なのは単体法（シンプレックス法）かと思いますが，残念ながら単体法は多項式時間アルゴリズムではありません^[2]．

双対性

双対性 (duality) は線形計画理論の一丁目一番地です．天下り的ですが，$y \in \R^m$ を変数とする以下のLP

$$\tag{D} \begin{array}{ll} \text{minimize} & y^\top b \\ \text{subject to} & y^\top A \ge c^\top, \\ & y \ge 0 \end{array}$$

を問題 (P) の双対問題 (dual problem) とよびます．最大化と最小化が入れ替わっていることに注意してください．双対問題 (D) に対して，(P) を (D) の主問題 (primal problem) とよびます．

$\mathrm{OPT}(\mathrm{P})$ と $\mathrm{OPT}(\mathrm{D})$ をそれぞれ主・双対問題の最適値と定義します^[3]．これらの量の間には以下の二種類の定理が成立します．

• 弱双対定理 (weak duality theorem): $\mathrm{OPT}(\mathrm{P}) \le \mathrm{OPT}(\mathrm{D})$.
• 強双対定理 (strong duality theorem): $\mathrm{OPT}(\mathrm{P}) = \mathrm{OPT}(\mathrm{D})$.

弱双対定理は以下のように簡単に示すことができます．主問題と双対問題のどちらかが実行不可能のときは自明^[4]です．$x \in \R^n$，$y \in \R^m$ をそれぞれ主・双対問題の任意の実行可能解としたときに，

• $y^\top A \ge c^\top$ かつ $x \ge 0$ より $c^\top x \le y^\top A x$
• $Ax \le b$ かつ $y \ge 0$ より $y^\top A x \le y^\top b$

より，

$$\tag{1} \mathrm{OPT}(\mathrm{P}) \le c^\top x \le y^\top A x \le y^\top b \le \mathrm{OPT}(\mathrm{D})$$

となります．一方，強双対定理を示すには非自明な議論^[5]が必要となりますので，この記事では認めることとします．

相補性

いよいよ本記事の主題である相補性について説明します．$x$ と $y$ をそれぞれ主・双対問題の実行可能解とします．もし $x$ と $y$ がともに最適解であれば，強双対定理から $c^\top x = y^\top b$ となりますが，特に式 (1) より $c^\top x = y^\top A x = y^\top b$ となります．さて，$c^\top x = y^\top A x$ が何を意味するか考えてみましょう．移項すると $(y^\top A - c^\top)x = 0$ です．総和記号を使って書き下すと

$$\tag{2} \sum_{i=1}^n ((y^\top A)_i - c_i) x_i = 0$$

となります．$x$ と $y$ の実行可能性から，任意の $i = 1, \dotsc, n$ に対して $x_i \ge 0$ かつ $(y^\top A)_i \ge c_i$ なので，$((y^\top A)_i - c_i) x_i \ge 0$ となります．これらの $i = 1, \dotsc, n$ に対する和が 0 ということは，すべての $i$ に対して $((y^\top A)_i - c_i) x_i = 0$ でなくてはならず，これはつまり $x_i = 0$ または $(y^\top A)_i = c_i$ の少なくとも一方が成立するということを意味します．同様に $y^\top A x = y^\top b$ からは，すべての $j = 1, \dotsc, m$ に対して $y_j = 0$ または $(Ax)_j = b_j$ の少なくとも一方が成立するという結論が得られます．

まとめると，実行可能解 $x, y$ が最適ならば，条件

• すべての $i = 1, \dotsc, n$ に対し，$x_i = 0$ または $(y^\top A)_i = c_i$
• すべての $j = 1, \dotsc, m$ に対し，$y_j = 0$ または $(Ax)_j = b_j$

が成立します．これらの条件を相補性条件 (complementarity condition) とよびます．逆に，実行可能解 $x, y$ が相補性条件を満たすならば $c^\top x = y^\top A x = y^\top b$ を満たすことも分かります．すなわち，$x$ と $y$ の目的関数値が一致しているので，弱双対定理より，これらは最適解となります．したがって，次の定理が得られます．

相補性定理 (complementarity theorem)：$x$ と $y$ をそれぞれ主・双対問題の実行可能解とする．$x$ と $y$ がそれぞれ主・双対問題の最適解であることと，相補性条件を満たすことは同値である．

相補性定理と最適解集合

以上で見たように，相補性定理はLPの双対定理の帰結として自然に得られ，その内容は最適性の必要十分条件を与えるものです．より一般の非線形凸計画問題の場合でも，Slater 条件などの適当な仮定のもとで同様の相補性条件が最適性の条件（の一部）を与えることが知られています（Karush–Kuhn–Tucker 条件）．この文脈では，相補性定理は最適解の候補の絞り込みや得られた解の最適性の確認に用いられるのが普通の使われ方だと思います．以下では，このような普通の使い方とはちょっと違った，LPの最適解全体を得るための使い方を説明します．

LPの最適解は一般に一意ではありません．最適解全体の集合は，LPの実行可能領域である多面体の一つの面を成します．これは以下のような幾何的なイメージを考えてもらうと納得できると思います．

つまり，最適解集合は，元の不等式制約に面を表す等式制約を追加することで記述できるはずです．特に，実行可能集合は各不等式制約が表す半空間の積空間であることから，最適解集合は主問題の制約をいくつか不等式から等式に修正したものになるはずです．この制約を得るにはどうすればよいか考えてみましょう．

ここで相補性定理が役に立ちます．双対問題の最適解 $y^*$ を任意に一つ固定します．相補性定理より，主問題の任意の実行可能解 $x$ に対して，$x$ が最適であることと，$(x, y^*)$ に対して相補性条件が成立することが等価です．相補性条件をおもむろに以下のように書き換えてみましょう．

• $((y^*)^\top A)_i > c_i$ であるすべての $i = 1, \dotsc, n$ に対し $x_i = 0$
• $y^*_j > 0$ であるすべての $j = 1, \dotsc, m$ に対し $(Ax)_j = b_j$

なんということでしょう，これらは主問題のいくつかの制約の不等式を等式に変えたものではありませんか！　繰り返しますが，主問題の任意の実行可能解 $x$ に対して，$x$ が最適であることとこれらの等式制約が成立することが等価です．したがって，主問題の不等式制約 $Ax \le b$ において，双対最適解 $y^*$ を好きに一つ選ぶと定まるこれらの制約を不等式から等式に変える（または単に $Ax \le b$ に加える）と，それが最適解全体の集合を表す制約集合になっているわけです．

双対問題の最適解を一つ持ってくるだけで主問題の最適解全体を記述できてしまうと主張しているこの事実は個人的に驚愕に値すると思っています．なお，双対問題の最適解も一般に一意でないので，異なる双対最適解 $y^*, z^*$ から得られる等式制約は違うものになり得ますが，主問題の不等式制約 $Ax \le b$ と合わせると定めている領域は同じものとなります．

組合せ最適化における例

最後に組合せ最適化での応用例を紹介します．$G = (U, V; E)$ を（孤立点のない）二部グラフとします．辺部分集合 $M \subseteq E$ はその中の相異なる任意の二辺が端点を共有しないときにマッチング (matching) とよばれます．辺重み $w \in \R^E$ の和 $w(M) \coloneqq \sum_{e \in M} w_e$ を最大化するマッチング全体がどのような構造をもつか調べましょう．

$G$ における重み $w$ に関する最大重みマッチング問題は，以下の整数計画問題

$$\tag{IP} \begin{array}{lll} \text{maximize} & w^\top x \\ \text{subject to} & \displaystyle \sum_{v \in V} x_{uv} \le 1 & (u \in U), \\ & \displaystyle \sum_{u \in U} x_{uv} \le 1 & (v \in V), \\ & x_{uv} \in \{0, 1\} & (uv \in E) \end{array}$$

として記述できます．ここで二値変数 $x_{uv}$ の値は，辺 $uv \in E$ をマッチングに採用するなら1，しないなら0に対応します．一番目と二番目の制約はそれぞれ $U, V$ の各頂点まわりで辺を高々一本しか選ぶことができないことを表しています．この問題の係数行列は完全単模^[6]なので，整数制約を緩和^[7]した以下のLP

$$\tag{LP} \begin{array}{lll} \text{maximize} & w^\top x \\ \text{subject to} & \displaystyle \sum_{v \in V} x_{uv} \le 1 & (u \in U), \\ & \displaystyle \sum_{u \in U} x_{uv} \le 1 & (v \in V), \\ & x \ge 0 \end{array}$$

は目的関数値を変化させない緩和となります（(IP) の実行可能解全体の凸包 = (LP) の実行可能領域）．(LP) の双対問題は $s \in \mathbb{R}^U, t \in \mathbb{R}^V$ を変数とする以下の問題

$$\tag{DLP} \begin{array}{ll} \text{minimize} & \displaystyle \sum_{u \in U} s_u + \sum_{v \in V} t_v \\ \text{subject to} & \displaystyle s_u + t_v \ge w_{uv} \quad (uv \in E), \\ & s, t \ge 0 \end{array}$$

です．

さて，相補性定理を使いましょう．$(s^*, t^*)$ を双対最適解とします．相補性定理より，(LP) の実行可能解 $x$ が最適であることと，

• $s_u^* + t_v^* > w_{uv}$ である任意の $uv \in E$ に対し，$x_{uv} = 0$
• $s_u^* > 0$ である任意の $u \in U$ に対し，$\sum_{v \in V} x_{uv} = 1$
• $t_v^* > 0$ である任意の $v \in V$ に対し，$\sum_{u \in U} x_{uv} = 1$

が成立することが等価です．つまり，

$$E^+ \coloneqq \{uv \in E \mid s_u^* + t_u^* > w_{uv}\}, \quad U^+ \coloneqq \{u \in U \mid s_u^* > 0\}, \quad V^+ \coloneqq \{v \in V \mid t_v^* > 0\}$$

とおくと，(LP) の最適解全体は

$$\tag{3} \begin{array}{llll} \displaystyle \sum_{v \in V} x_{uv} \le 1 & (u \in U \setminus U^+), & \displaystyle \sum_{v \in V} x_{uv} = 1 & (u \in U^+), \\ \displaystyle \sum_{u \in U} x_{uv} \le 1 & (v \in V \setminus V^+), \quad & \displaystyle \sum_{u \in U} x_{uv} = 1 & (v \in V^+), \\ x_{uv} \ge 0 & (uv \in E \setminus E^+), \quad & x_{uv} = 0 & (uv \in E^+) \end{array}$$

で記述される領域と一致します．(3) の係数行列は (IP) の制約のそれと変わっておらず完全単模なので，(IP) の最適解全体は (3) に整数制約 $x_{uv} \in \{0, 1\}$ を入れたものと一致します．

(3) は組合せ的には何を意味しているでしょうか？　まず $\sum_{v \in V} x_{uv} = 1$ $(u \in U^+)$ は，$U^+$ に含まれる各頂点を被覆（頂点に接続する辺を選ぶ）しなければならないということを意味します．$\sum_{u \in U} x_{uv} = 1$ $(v \in V^+)$ も同様です．$x_{uv} = 0$ $(uv \in E^+)$ は，$E^+$ に含まれる辺は使用できないということを意味します．言い換えると，$E^* \coloneqq E \setminus E^+ = \{uv \in E \mid s_u^* + t_u^* = w_{uv}\}$ としたときに，最大重みマッチングに含まれる辺は，部分グラフ $G^* \coloneqq (U, V; E^*)$ の辺でなくてはならないということを要請しています．$G^*$ をタイト部分グラフ (tight subgraph) とよぶことがあります．つまり，$G$ の重み $w$ に関する最大重みマッチング全体は，$G^*$ のマッチングであって，$U^+ \cup V^+$ の頂点を被覆するようなもの全体と一致するということがわかります．このように相補性定理を用いることで，二部グラフの最大重みマッチング全体の特徴づけを得ることができます．

参考文献

• K. Murota. Computing the degree of determinants via combinatorial relaxation. SIAM Journal on Computing, 24(4):765–96, 1990.

脚注

1. linear programming は線形目的関数・線形制約であるような問題に対する最適化手法を意味する線形計画（法），各々具体的な問題のことは linear programming problem または linear program というのが正しいかもしれません．この辺の語句の意味や和語と英語の対応は自信がないです．この記事では全部LPと書いてごまかします．

2. 正確に述べると，任意のインスタンスに対して多項式時間で単体法の反復が終了するような枢軸変換規則は知られていません．

3. 主問題 (P) が実行不可能の場合は $\mathrm{OPT}(\mathrm{P}) = -\infty$，非有界の（いくらでも大きい目的関数値をもつ実行可能解が存在する）場合は $\mathrm{OPT}(\mathrm{P}) = +\infty$ とします．同様に双対問題 (D) が実行不可能の場合は $\mathrm{OPT}(\mathrm{D}) = +\infty$，非有界の場合は $\mathrm{OPT}(\mathrm{D}) = -\infty$ と定義します．

4. $\mathrm{OPT}(\mathrm{P}) = -\infty$ または $\mathrm{OPT}(\mathrm{D}) = +\infty$ なので．

5. Farkas の補題を利用するか，単体法などのLPに対する主双対アルゴリズムの正当性から示すのが主な証明手法です．

6. 任意の正方な小行列の行列式が $\{0, +1, -1\}$ のいずれかであるような行列を完全単模 (totally unimodular) とよびます．完全単模行列を制約の係数とするLPは，最適解が存在するなら，最適解を整数にとれるということが知られています．

7. $x_{uv} \in \{0, 1\}$ を $0 \le x_{uv} \le 1$ に置き換えます．$x_{uv} \le 1$ が消えているように思うかもしれませんが，（孤立点がなければ）一番目と二番目の制約から従う冗長な制約になっているので，削除しました．