線形計画の双対問題: 線形計画入門 9 - コンピュータフリーク

この章では、線形計画の双対問題について考えます。線形計画の双対問題も線形計画になること、線形計画の双対問題の最適値が元の問題の最適値に一致することがこの章のハイライトです。

線形計画の双対問題

標準形線形計画 $$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad a_1^\top x = b_1\\ &\qquad \qquad \qquad \vdots\\ &\qquad \qquad a_m^\top x = b_m \\ &\qquad \qquad x \ge 0\end{align*}$$を考えます。$\lambda_1, \cdots, \lambda_m \in \mathbb{R}, \lambda_{m+1}, \cdots, \lambda_{m+n} \ge 0$ に対して、この問題のラグランジュ双対関数は $$g(\lambda) = \min \left( c^\top x + \sum_{i=1}^m \lambda_i (b_i – a_i^\top x) ~- \sum_{i = 1}^n \lambda_{m+i} x_i \right)$$ となります。この関数の中身を各 $x_j$ についてまとめるように整理すると、$$\begin{align*} &c^\top x + \sum_{i=1}^m \lambda_i (b_i – a_i^\top x) ~- \sum_{i = 1}^n \lambda_{m+i} x_i \\ &= \sum_{i = 1}^m \lambda_i b_i + \sum_{j = 1}^n (c_j – (\sum_{i = 1}^m a_{ij}\lambda_i) – \lambda_{m+j}) x_j\end{align*}$$ となります。いま $x$ には制約はないので、$c_j – (\sum_{i = 1}^m a_{ij}\lambda_i) – \lambda_{m+j} \neq 0$ であれば $x_j \to \infty$ または $x_j \to – \infty$ とすることで中身を無限に小さくすることができ、$g(\lambda) = -\infty$ となります。逆に、全ての $j$ で $c_j – (\sum_{i = 1}^m a_{ij}\lambda_i) – \lambda_{m+j} = 0$ であれば、二項目は消失して一項目だけになります。つまり、$$g(\lambda) = \begin{cases} -\infty & \exists j \text{ s.t. } c_j – (\sum_{i = 1}^m a_{ij} \lambda_i) – \lambda_{m+j} \neq 0 \\ \sum_{i = 1}^m \lambda_i b_i\end{cases}$$ です、$g(\lambda) = -\infty$ のときには最大化問題の最適解にはなりようがないので、双対問題は $c_j – (\sum_{i = 1}^m a_{ij}\lambda_i) – \lambda_{m+j} = 0$ を制約とした以下の問題と等価です。 $$\begin{align*}&\underset{\lambda \in \mathbb{R}^{n+m}}{\text{maximize}} \quad \sum_{i = 1}^m \lambda_i b_i \\ &\quad \text{s.t.} \qquad c_j – (\sum_{i = 1}^m a_{ij}\lambda_i) – \lambda_{m+j} = 0 \quad (j = 1, \cdots, m) \\ &\qquad \qquad \lambda_j \ge 0 \quad (j = m+1, \cdots, m+n)\end{align*}$$ 等式制約を使って $\lambda_{m+1}, \cdots, \lambda_{n+m}$ を削除すれば、これは以下の問題と等価です。$$\begin{align*}&\underset{\lambda \in \mathbb{R}^{m}}{\text{maximize}} \quad \sum_{i = 1}^m \lambda_i b_i \\ &\quad \text{s.t.} \qquad c_j – (\sum_{i = 1}^m a_{ij} \lambda_i) \ge 0 \quad (j = 1, \cdots, m)\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*}$$ となります。

命題: 線形計画の双対問題

$$\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*}$$

つまり、線形計画の双対問題は線形計画になります。よって、双対問題の方もシンプレックス法で解くことができます。

問題が大規模で厳密な最適解を計算するのに時間がかかりそうなときは、もとの問題（主問題）と双対問題の両方に対して同時に最適化プログラムを走らせ、$f(x) – g(\lambda) \le \varepsilon$ となる実行可能解 $x, \lambda$ が見つかった時点で停止すると、弱双対定理より $f(x)$ は最適値よりも高々 $\varepsilon$ しか大きくないことが保証できます。

強双対定理

線形計画の双対問題を扱う上で最も重要な定理である強双対定理を紹介します。これは、双対問題の最適値が主問題の最適値に一致するというものです。言い換えると、うまく $\lambda$ を選べばラグランジュ緩和問題が有益な下界になることを意味しています。

強双対定理

主問題に最適解が存在すれば、双対問題の最適値は主問題の最適値に一致する。つまり、$f(x) = g(\lambda)$ となる実行可能解 $x, \lambda$ が存在する。

証明

主問題に対してシンプレックス法を適用する。最適解が存在するとき、シンプレックス法は $$c_{N}^\top – c_{B}^\top A_{B}^{-1} A_{N} \ge 0 \tag{1}$$となる基底解 $x^*_B = A_B^{-1} b$ および添字 $B, N$ を見つけて停止する。$$\lambda = A_B^{-\top} c_B \tag{2}$$とおくと、式 (1) より $A_N^\top \lambda \le c_N$ となり、式 (2) の両辺に $A_B^\top$ をかけると $A_B^\top \lambda = c_B$ である。よって、$\lambda$ は双対問題の実行可能解。また、このとき $$g(\lambda) = b^\top \lambda = b^\top A_B^{-\top} c_B = c_B^\top (A_B^{-1} b) = c_B^\top x^*_B = f(x^*)$$

弱双対定理は任意の最適化問題について成り立ちますが、強双対定理は線形計画問題など一部の最適化問題に成り立つ特殊な性質です。