この記事について

前の2つの記事で、線形計画（LP）の双対問題を2つの視点（1次結合とラグランジュ緩和）から導きました。今回はそれらの理論的な性質を整理する3つの重要定理、弱双対定理・強双対定理・相補性条件 を扱います。

数式が多めですが、これらが押さえられると感度分析・双対単体法・列生成法などの応用がぐっと理解しやすくなるはずなので頑張りましょう。

前提：主問題と双対問題

不等式標準形のLPで話を進めます。

主問題 (P)

\text{maximize} \quad \mathbf{c}^\top \mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq \mathbf{0}

双対問題 (D)

\text{minimize} \quad \mathbf{b}^\top \mathbf{y} \quad \text{s.t.} \quad \mathbf{A}^\top \mathbf{y} \geq \mathbf{c},\ \mathbf{y} \geq \mathbf{0}

ここで $\mathbf{A} \in \mathbb{R}^{m \times n}$、$\mathbf{x} \in \mathbb{R}^n$、$\mathbf{y} \in \mathbb{R}^m$ です。

弱双対定理（Weak Duality Theorem）

定理： $\mathbf{x}$ を主問題 (P) の実行可能解、$\mathbf{y}$ を双対問題 (D) の実行可能解とすると、

\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}

証明

主問題の制約 $\mathbf{A}\mathbf{x} \leq \mathbf{b}$、$\mathbf{x} \geq \mathbf{0}$ と双対問題の制約 $\mathbf{A}^\top \mathbf{y} \geq \mathbf{c}$、$\mathbf{y} \geq \mathbf{0}$ を組み合わせます。

\mathbf{c}^\top \mathbf{x} \leq (\mathbf{y}^\top \mathbf{A}) \mathbf{x} = \mathbf{y}^\top (\mathbf{A} \mathbf{x}) \leq \mathbf{y}^\top \mathbf{b} = \mathbf{b}^\top \mathbf{y}

不等号	根拠
最初の $\leq$	$\mathbf{c} \leq \mathbf{A}^\top \mathbf{y}$（双対の制約）かつ $\mathbf{x} \geq \mathbf{0}$
等号	結合則：$(\mathbf{y}^\top \mathbf{A}) \mathbf{x} = \mathbf{y}^\top (\mathbf{A} \mathbf{x})$
2番目の $\leq$	$\mathbf{A} \mathbf{x} \leq \mathbf{b}$（主の制約）かつ $\mathbf{y} \geq \mathbf{0}$

意味

任意の主問題の実行可能解の目的関数値は、任意の双対問題の実行可能解の目的関数値以下になります。図にすると以下のようなイメージです。

オレンジ側：主問題の実行可能解の目的関数値の集合（最適値以下に分布）
青側：双対問題の実行可能解の目的関数値の集合（最適値以上に分布）
赤の点・破線：両方の境目にある最適値（強双対定理により一致する）

「主問題のどの解も双対問題のどの解より小さい」 という強い分離が成り立つわけです。

思いのほかきれいな図ができた気がするので、上図を生成したコードも共有しておきます。

import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

plt.rcParams['font.family'] = 'Yu Gothic'

fig, ax = plt.subplots(figsize=(11, 5.5))

x_min, x_max = 0, 150
opt_val = 90

# 主問題の値の範囲（オレンジ）
ax.add_patch(Rectangle((x_min, 0.5), opt_val - x_min, 1.0,
                       facecolor='#FAD7A0', edgecolor='#E67E22',
                       linewidth=1.5, alpha=0.85))
ax.text((x_min + opt_val) / 2, 1.7,
        '主問題の実行可能解の値\n(最適値 以下)',
        ha='center', va='center', fontsize=13, fontweight='bold',
        color='#B9770E')

# 双対問題の値の範囲（青）
ax.add_patch(Rectangle((opt_val, 0.5), x_max - opt_val, 1.0,
                       facecolor='#AED6F1', edgecolor='#2980B9',
                       linewidth=1.5, alpha=0.85))
ax.text((opt_val + x_max) / 2, 1.7,
        '双対問題の実行可能解の値\n(最適値 以上)',
        ha='center', va='center', fontsize=13, fontweight='bold',
        color='#1F618D')

# 例解の点
for v in [15, 45, 75]:
    ax.scatter(v, 1.0, c='#E67E22', s=110, zorder=8,
               edgecolors='white', linewidths=1.5)
for v in [105, 125, 140]:
    ax.scatter(v, 1.0, c='#2980B9', s=110, zorder=8,
               edgecolors='white', linewidths=1.5)
ax.scatter(opt_val, 1.0, c='#C0392B', s=160, zorder=9,
           edgecolors='white', linewidths=2)

# 数直線
ax.annotate('', xy=(x_max + 5, 0), xytext=(x_min - 5, 0),
            arrowprops=dict(arrowstyle='->', color='black', lw=1.5))
ax.text(x_max + 7, 0, '目的関数値',
        fontsize=12, fontweight='bold', va='center')

# 目盛り
for v in [0, 30, 60, 90, 120, 150]:
    ax.plot([v, v], [-0.1, 0.1], color='black', lw=1.2)
    color = '#C0392B' if v == opt_val else 'black'
    weight = 'bold' if v == opt_val else 'normal'
    ax.text(v, -0.3, str(v), ha='center', va='top', fontsize=11,
            color=color, fontweight=weight)

# 最適値の縦線
ax.plot([opt_val, opt_val], [-0.5, 2.3],
        color='#C0392B', linewidth=2.5, linestyle='--', zorder=5)
ax.text(opt_val, 2.5, '最適値（主・双対が一致）',
        ha='center', va='bottom', fontsize=12, fontweight='bold',
        color='#C0392B',
        bbox=dict(boxstyle='round,pad=0.4', facecolor='white',
                  edgecolor='#C0392B', alpha=0.95, linewidth=1.5))

# 弱双対のラベル
ax.annotate('', xy=(110, -0.95), xytext=(70, -0.95),
            arrowprops=dict(arrowstyle='->', color='#7f8c8d',
                            lw=2.0, alpha=0.8))
ax.text(90, -1.25,
        r'弱双対定理：$\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}$（主問題のどの解 ≤ 双対問題のどの解）',
        ha='center', va='top', fontsize=12, color='#34495e',
        fontweight='bold')

ax.set_xlim(x_min - 18, x_max + 22); ax.set_ylim(-1.8, 3.4)
ax.axis('off')
ax.set_title('弱双対定理：主問題と双対問題の値は最適値で分離される',
             fontsize=14, fontweight='bold', pad=8)

plt.tight_layout()
plt.savefig('materials/weak_duality.png', dpi=150, bbox_inches='tight')

主問題・双対問題の組み合わせパターン

弱双対定理から、(P) と (D) の組み合わせは以下のパターンに整理できます。

主問題	双対問題
実行可能（有界）	実行可能（有界）
非有界	実行不能
実行不能	非有界
実行不能	実行不能（両方とも）

ポイント：

主問題が非有界（$\mathbf{c}^\top \mathbf{x} \to \infty$）なら、$\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}$ を満たす $\mathbf{y}$ は存在しない → 双対は実行不能
双対問題が非有界（$\mathbf{b}^\top \mathbf{y} \to -\infty$）なら、同じ理由で主問題は実行不能
両方とも実行不能というケースも理論的にはあり得ます

強双対定理（Strong Duality Theorem）

定理： 主問題 (P) が最適解を持つならば、双対問題 (D) も最適解を持ち、2つの問題の最適値は一致する。

\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*

弱双対定理は「不等式」でしたが、強双対定理は「等式」になります。これがLP双対の最も強力な性質です。

証明

主問題の最適基底解 $\mathbf{x}^* = (\mathbf{x}_B^, \mathbf{x}_N^)$ を考えます。基底分割を使った単体法の結果から

\mathbf{c}^\top \mathbf{x}^* = \mathbf{c}_B^\top \mathbf{B}^{-1} \mathbf{b} + (\mathbf{c}_N - \mathbf{N}^\top (\mathbf{B}^{-1})^\top \mathbf{c}_B)^\top \mathbf{x}_N^*

$\mathbf{x}^*$ が最適解なので、被約費用 $\mathbf{c}_N - \mathbf{N}^\top (\mathbf{B}^{-1})^\top \mathbf{c}_B \leq \mathbf{0}$ が成り立ちます。基底変数の被約費用は 0 なので、これを統合すると

\mathbf{c} - \mathbf{A}^\top (\mathbf{B}^{-1})^\top \mathbf{c}_B \leq \mathbf{0}

ここで シンプレックス乗数 $\mathbf{y}^* = (\mathbf{B}^{-1})^\top \mathbf{c}_B$ を定義します。すると

\mathbf{c} - \mathbf{A}^\top \mathbf{y}^* \leq \mathbf{0}, \quad \text{i.e.,} \quad \mathbf{A}^\top \mathbf{y}^* \geq \mathbf{c}

これは双対問題の制約と同じです。 つまり $\mathbf{y}^*$ は双対問題の実行可能解になっています。

さらに目的関数値は：

\mathbf{b}^\top \mathbf{y}^* = \mathbf{b}^\top (\mathbf{B}^{-1})^\top \mathbf{c}_B = (\mathbf{B}^{-1} \mathbf{b})^\top \mathbf{c}_B = \mathbf{x}_B^{*\top} \mathbf{c}_B = \mathbf{c}^\top \mathbf{x}^*

最後の等式は $\mathbf{x}_N^* = \mathbf{0}$ を使っています。

弱双対定理から $\mathbf{c}^\top \mathbf{x}^* \leq \mathbf{b}^\top \mathbf{y}$（任意の双対実行可能解）なので、$\mathbf{y}^*$ は双対問題の最適解になります。

意味

単体法でLPを解くと、副産物として双対問題の最適解も得られるということです。シンプレックス乗数 $\mathbf{y}^* = (\mathbf{B}^{-1})^\top \mathbf{c}_B$ がまさに双対変数の値になっています。

これは実用上もとても便利な性質で、感度分析（後続の記事で扱います）の基礎になります。

相補性条件（Complementary Slackness）

定理： $\mathbf{x}^, \mathbf{y}^$ がそれぞれ主問題・双対問題の最適解とすると、以下の 相補性条件 が成り立つ。

y_i^* \cdot \left( b_i - \sum_{j=1}^{n} a_{ij} x_j^* \right) = 0, \quad i = 1, \ldots, m

x_j^* \cdot \left( \sum_{i=1}^{m} a_{ij} y_i^* - c_j \right) = 0, \quad j = 1, \ldots, n

直感的な意味

各 $i$ について どちらか一方は必ず 0 ということを言っています。

y_i* > 0  ⇒  b_i - Σ a_ij x_j* = 0    （主問題の i 番目の制約が等号で成立）
b_i - Σ a_ij x_j* > 0  ⇒  y_i* = 0    （制約に余裕があれば双対変数は 0）

つまり：

主問題で制約が等号で活性化しているならば、双対変数は正になり得る
主問題で制約に余裕がある（スラックが正）ならば、双対変数は 0

証明

強双対定理から $\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*$。

\mathbf{y}^{*\top} \mathbf{b} = \mathbf{y}^{*\top} \mathbf{A} \mathbf{x}^* = \mathbf{c}^\top \mathbf{x}^*

途中の等式は強双対性と $\mathbf{x}^* , \mathbf{y}^*$ の関係から導けます。整理すると：

\mathbf{y}^{*\top} (\mathbf{b} - \mathbf{A} \mathbf{x}^*) = 0, \quad \mathbf{x}^{*\top} (\mathbf{A}^\top \mathbf{y}^* - \mathbf{c}) = 0

各成分は $\mathbf{x}^* , \mathbf{y}^* \geq \mathbf{0}$、$\mathbf{b} - \mathbf{A}\mathbf{x}^* \geq \mathbf{0}$、$\mathbf{A}^\top \mathbf{y}^* - \mathbf{c} \geq \mathbf{0}$ から非負。和が 0 になるためには 各成分が 0 でなければなりません。これが相補性条件です。

双対問題の双対は主問題

ついでに、もうひとつの興味深い性質も紹介します。

双対問題の双対問題は、元の主問題に戻る。

これは双対の操作を「対称的な変換」と見なせる根拠でもあります。証明は機械的に「最大化↔最小化」「変数↔制約」を入れ替えていけば確認できますが、興味があれば手を動かして確認して見てください。

まとめ

弱双対定理：主問題の任意の実行可能解 $\leq$ 双対問題の任意の実行可能解
強双対定理：両方に最適解があれば最適値が一致
相補性条件：$y_i^* > 0 \Rightarrow$ 制約 $i$ は等号で活性、$y_i^* = 0 \Rightarrow$ 制約 $i$ にスラックあり
双対問題の双対は主問題

次回の記事では、これらの定理を実用に活かす場面、感度分析・潜在価格・双対単体法 を扱います。