線形計画の相補性 - コンピュータフリーク

線形計画の主問題と双対問題の最適解には相補性とよばれる特殊な関係が成り立ちます。この事実は主双対内点法など、線形計画のアルゴリズムで使われるほか、解を解釈するためにも有用です。

この記事では、二つの線形計画の定式化における相補性の定式化と、その直感的な意味を紹介します。

相補性定理

定理: 相補性

$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x = b \\ &\qquad \qquad x \ge 0\end{align*}$$ と $$\begin{align*}&\underset{\lambda \in \mathbb{R}^{m}}{\text{maximize}} \quad b^\top \lambda \\ &\quad \text{s.t.} \qquad A^\top \lambda \le c\end{align*}$$ を線形計画の主問題と双対問題とし、$x \in \mathbb{R}^n, \lambda \in \mathbb{R}^m$ を主問題と双対問題の実行可能解とする。このとき、$(c – A^\top \lambda)^\top x = 0$ であるときかつそのときのみ $x, \lambda$ はともに最適解である。

証明

必要性: $(c – A^\top \lambda)^\top x = 0$ とすると、$$(c – A^\top \lambda)^\top x = c^\top x – \lambda^\top A x = c^\top x – \lambda^\top b = 0$$ が成り立つ。ここで最後から二番目の等式は $x$ が実行可能のため、制約条件の $Ax = b$ より従う。よって、$c^\top x = b^\top \lambda$ となり、$x, \lambda$ は主問題と双対問題の実行可能解であり目的関数値が同じであるので、弱双対定理よりこれらはともに最適解である。

十分性: $x, \lambda$ が最適解であるとすると、強双対定理より $c^\top x = b^\top \lambda$ が成立。よって、$$(c – A^\top \lambda)^\top x = c^\top x – \lambda^\top A x = c^\top x – \lambda^\top b = 0$$ が成り立つ。

$(c – A^\top \lambda)^\top x = 0$ の条件を相補性条件といいます。$s = c – A^\top \lambda$ とおくと、相補性条件は全ての添字 $i = 1, \cdots, n$ において $x_i = 0$ または $s_i = 0$ が成り立つということと等価です。相補性定理より、線形計画を解く問題は、相補性条件が成り立つ実行可能解を発見する問題に帰着されます。主双対内点法などのアルゴリズムは、目的関数を直接最適化するのではなく、相補性条件が成り立つ解を見つけることを目指して設計されています。

相補性条件の直感的な意味

感度分析の記事で考えた以下の線形計画を通して相補性を直感的に理解しましょう。あなたは薬品工場のオーナーだとします。この工場では薬品 $1, 2, \cdots, m$ を生産しており、それぞれの薬品をどれだけ生産するかを決定したいと考えています。薬品 $i$は、過去の経験から、1kg 作るごとに $b_i$ 万円の利益が見込めます。ただし、薬品 $i$ を作るには希少材料 $j$ を $A_{ji}$ グラム消費してしまいます（$i = 1, \cdots, m, j = 1, \cdots, n$）。希少材料 $j$ の在庫は $c_j$ グラムです。材料が不足しないように利益を最大化するには、薬品をそれぞれ何kgずつ作ればよいでしょう。

この問題は以下の線形計画で定式化されます。$$\begin{align*}&\underset{\lambda \in \mathbb{R}^{m}}{\text{maximize}} \quad b^\top \lambda \\ &\quad \text{s.t.} \qquad A^\top \lambda \le c\end{align*}$$ ここで $\lambda_i$ は薬品 $j$ を生産する量を表す決定変数です。この問題の双対問題は $$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x = b \\ &\qquad \qquad x \ge 0\end{align*}$$ となります。感度分析の記事で述べたように、双対問題の最適解 $x^*$ は各材料の在庫を一単位増やした時に主問題の最適値が増える量を表しています。

$\lambda$ を実行可能解とすると、$A^\top \lambda \le c$ が成り立ちます。このとき、相補性条件 $(c – A^\top \lambda)^\top x = 0$ は「$A^\top_j \lambda < c_j$ であれば $x_j = 0$」であることを表しています。すなわち、在庫を全て消費していないのであれば在庫量を増やす価値はゼロであるということを表しています。最適解においてこれが成り立つというのは自然な発想かと思います。

他の定式化における相補性定理

上記の定理では、標準形線形計画とその双対問題を考えました。他の線形計画の定式化においても標準形に書き直せば上記の定理が成り立ちます。しかし、標準形以外の形式のまま相補性定理を解釈すると少し相補性条件の形が変わってくるので、ここでは不等式形の線形計画の相補性定理を取り上げて紹介します。

系: 別形式の相補性定理

$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x \ge b \\ &\qquad \qquad x \ge 0\end{align*}$$ と $$\begin{align*}&\underset{\lambda \in \mathbb{R}^{m}}{\text{maximize}} \quad b^\top \lambda \\ &\quad \text{s.t.} \qquad A^\top \lambda \le c \\ & \qquad \qquad \lambda \ge 0\end{align*}$$ を線形計画の主問題と双対問題とし、$x \in \mathbb{R}^n, \lambda \in \mathbb{R}^m$ を主問題と双対問題の実行可能解とする。このとき、$(c – A^\top \lambda)^\top x = 0$ かつ $(b – A x)^\top \lambda = 0$であるときかつそのときのみ $x, \lambda$ はともに最適解である。

証明

必要性: $(c – A^\top \lambda)^\top x = 0$ かつ $(b – A x)^\top \lambda = 0$ とすると、$$(c – A^\top \lambda)^\top x　 – (b – A x)^\top \lambda = c^\top x – \lambda^\top A x – b^\top \lambda + \lambda^\top A x = c^\top x – b^\top \lambda = 0$$ が成り立つ。よって、$c^\top x = b^\top \lambda$ となり、$x, \lambda$ は主問題と双対問題の実行可能解であり目的関数値が同じであるので、弱双対定理よりこれらはともに最適解である。

十分性: $x, \lambda$ が最適解であるとすると、強双対定理より $c^\top x = b^\top \lambda$ が成立。よって、$$(c – A^\top \lambda)^\top x – (b – A x)^\top \lambda = c^\top x – \lambda^\top A x – b^\top \lambda + \lambda^\top A x = c^\top x – b^\top \lambda = 0$$ となり、 $$(c – A^\top \lambda)^\top x = (b – A x)^\top \lambda$$ が成り立つ。実行可能性より、$x \ge 0, \lambda \ge 0, c – A^\top \lambda \ge 0, b – A x \le 0$ が成り立つので、$$(b – A x)^\top \lambda \le 0 \le (c – A^\top \lambda)^\top x$$ が成り立つ。この最左辺と最右辺が等しいので、その時の値は $0$ となる。

$(c – A^\top \lambda)^\top x = 0$ を主相補性条件、$(b – A x)^\top \lambda = 0$ を双対相補性条件といいます。この系の問題のように、主問題と双対問題の両方が不等式系の場合は、これらの両方が成り立たなければならないことに注意してください。不等式制約が等号成立していないときには常に対になる双対変数がゼロでなければならないということです。