この記事について
以前の記事では「制約条件の1次結合で上界を作る」という発想から線形計画（LP）の双対問題を導きました。実はもう一つ、ラグランジュ緩和（Lagrangian Relaxation） という別の視点からも同じ双対問題が出てきます。
理論的背景から「同じ問題を別の角度から見て同じ結論に至る」という理解するのは面白いし、何より緩和問題という概念は LP に限らず広く使えるので、押さえておくとMIPや非線形最適化の理解にもつながります。
緩和問題（Relaxation Problem）とは
最適解を求めることが難しい問題に対するアプローチとして、原問題を簡単な問題に変形して上界を求める という考え方があります。
\begin{aligned}
\text{原問題 (P):} \quad & \max f(\mathbf{x}) \quad \text{s.t.} \quad \mathbf{x} \in S \\
\text{緩和問題 (R):} \quad & \max \bar{f}(\mathbf{x}) \quad \text{s.t.} \quad \mathbf{x} \in \bar{S}
\end{aligned}
緩和問題が満たすべき2つの条件：
| 条件 | 内容 | 意味 |
|---|---|---|
| R1 | $S \subseteq \bar{S}$ | 実行可能領域を広げる |
| R2 | $\bar{f}(\mathbf{x}) \geq f(\mathbf{x}),\ \mathbf{x} \in S$ | 目的関数を上に持ち上げる |
この2条件のもとでは、原問題の最適解 $\mathbf{x}^*$ と緩和問題の最適解 $\bar{\mathbf{x}}$ の関係は：
f(\mathbf{x}^*) \leq \bar{f}(\mathbf{x}^*) \leq \bar{f}(\bar{\mathbf{x}})
つまり 緩和問題の最適値が原問題の最適値の上界 になります。緩和問題は原問題より解きやすい問題なので、上界を比較的安価に得られるわけです。
代表的な緩和問題：
- LP緩和：整数計画問題の整数条件を外す
- ラグランジュ緩和：一部の制約を取り除き、ペナルティとして目的関数に組み込む
ラグランジュ緩和問題の作り方
例題：
\begin{aligned}
\text{maximize} \quad & 20x_1 + 10x_2 \\
\text{subject to} \quad & x_1 + x_2 \leq 6 \\
& 3x_1 + x_2 \leq 12 \\
& x_1 + 2x_2 \leq 10 \\
& x_1, x_2 \geq 0
\end{aligned}
3本の不等式制約を取り除き、それぞれの 違反度 にペナルティ重み $w_1, w_2, w_3 \geq 0$ を掛けて目的関数に組み込みます。
\begin{aligned}
\text{maximize} \quad & 20x_1 + 10x_2 \\
& - w_1(x_1 + x_2 - 6) \\
& - w_2(3x_1 + x_2 - 12) \\
& - w_3(x_1 + 2x_2 - 10) \\
\text{subject to} \quad & x_1, x_2 \geq 0
\end{aligned}
これが ラグランジュ緩和問題 です。元の制約が削除されて、代わりに目的関数にペナルティ項が加わっています。
なぜこれが「緩和」になっているか？
元の制約を満たす $\mathbf{x}$ では $x_1 + x_2 - 6 \leq 0$ なので、$-w_1(x_1 + x_2 - 6) \geq 0$。つまりペナルティ項は非負で、目的関数を上に持ち上げるだけ。R2 を満たします。
また、元の制約をなくすので実行可能領域は広がる方向。R1 も満たします。
ペナルティ重みを最適化する
ラグランジュ緩和問題の最適値は、ペナルティ重み $\mathbf{w}$ に依存します。これを $z(\mathbf{w})$ と書きます。
z(\mathbf{w}) = \max_{\mathbf{x} \geq \mathbf{0}} \Big[ 20x_1 + 10x_2 - w_1(x_1 + x_2 - 6) - w_2(3x_1 + x_2 - 12) - w_3(x_1 + 2x_2 - 10) \Big]
任意の $\mathbf{w} \geq \mathbf{0}$ で $z(\mathbf{w})$ は原問題の上界になります。最も良い（小さい）上界は $z(\mathbf{w})$ を $\mathbf{w}$ について最小化することで得られます。
\min_{\mathbf{w} \geq \mathbf{0}} z(\mathbf{w})
これを ラグランジュ双対問題（Lagrangian Dual Problem） と呼びます。
重みごとに緩和問題を解いてみる
$z(\mathbf{w})$ を $x_1, x_2$ について整理します。
z(\mathbf{w}) = \max_{\mathbf{x} \geq \mathbf{0}} \Big[ (20 - w_1 - 3w_2 - w_3)x_1 + (10 - w_1 - w_2 - 2w_3)x_2 + 6w_1 + 12w_2 + 10w_3 \Big]
ここで重要な観察：$x_1, x_2$ の係数が正だと、$x_1, x_2$ を無限大に増やせるので $z(\mathbf{w}) = \infty$（非有界）になってしまいます。
つまり「意味のある上界」を得るためには、係数を非正に抑える必要があります。
20 - w_1 - 3w_2 - w_3 \leq 0, \quad 10 - w_1 - w_2 - 2w_3 \leq 0
この条件のもとでは、$x_1, x_2$ を 0 にしないと目的関数が悪化するので、最適解は常に $x_1 = x_2 = 0$。すると：
z(\mathbf{w}) = 6w_1 + 12w_2 + 10w_3
双対問題が現れる
「$z(\mathbf{w})$ を最小化、ただし係数は非正、$w_i \geq 0$」をまとめると：
\begin{aligned}
\text{minimize} \quad & 6w_1 + 12w_2 + 10w_3 \\
\text{subject to} \quad & 20 - w_1 - 3w_2 - w_3 \leq 0 \\
& 10 - w_1 - w_2 - 2w_3 \leq 0 \\
& w_1, w_2, w_3 \geq 0
\end{aligned}
整理すると：
\begin{aligned}
\text{minimize} \quad & 6w_1 + 12w_2 + 10w_3 \\
\text{subject to} \quad & w_1 + 3w_2 + w_3 \geq 20 \\
& w_1 + w_2 + 2w_3 \geq 10 \\
& w_1, w_2, w_3 \geq 0
\end{aligned}
これは、以前の記事で導いた双対問題そのものです。
つまり：
ラグランジュ双対問題 ＝ LPの双対問題
「制約の1次結合で上界を作る」アプローチと「ラグランジュ緩和で上界を作る」アプローチが、まったく同じ問題に到達しました。これがLPの双対の美しさかと思います。
一般形（不等式標準形）
任意の不等式標準形のLPに対しても同じ流れが成り立ちます。
主問題（P）
\max \sum_{j=1}^{n} c_j x_j \quad \text{s.t.} \quad \sum_{j=1}^{n} a_{ij} x_j \leq b_i,\ x_j \geq 0
ラグランジュ緩和
\max \sum_{j=1}^{n} c_j x_j - \sum_{i=1}^{m} w_i \left( \sum_{j=1}^{n} a_{ij} x_j - b_i \right) \quad \text{s.t.} \quad x_j \geq 0,\ w_i \geq 0
整理して双対問題（D）
$x_j$ の係数 $c_j - \sum_i a_{ij} w_i$ を非正に抑える条件を加えると：
\min \sum_{i=1}^{m} b_i w_i \quad \text{s.t.} \quad \sum_{i=1}^{m} a_{ij} w_i \geq c_j,\ w_i \geq 0
これは双対問題と一致しています。
等式制約の場合
主問題が等式標準形 $\mathbf{A}\mathbf{x} = \mathbf{b}$ の場合は、等式を「$\leq$」と「$\geq$」の2本の不等式に分けて、それぞれにペナルティ重み $w_i, v_i \geq 0$ を導入します。差 $y_i = w_i - v_i$ は符号自由になるので、 双対変数 $y_i$ には非負制約が付かない（自由変数になる） ことになります。これも以前の対応表と一致します。
Pythonで重みを変えて上界を観察
ラグランジュ緩和の上界が、重み $\mathbf{w}$ によってどう変化するか確認してみます。
import numpy as np
import pulp
def lagrangian_relaxation(w1, w2, w3):
"""ラグランジュ緩和問題を解く"""
# x の係数
coef_x1 = 20 - w1 - 3*w2 - w3
coef_x2 = 10 - w1 - w2 - 2*w3
if coef_x1 > 1e-9 or coef_x2 > 1e-9:
return float('inf') # 非有界
# それ以外は x1 = x2 = 0 が最適
return 6*w1 + 12*w2 + 10*w3
# いろんな w で上界を計算
weights = [
(0, 6, 2), # x1 係数 = 20-0-18-2 = 0, x2 係数 = 10-0-6-4 = 0
(0, 5, 5),
(5, 5, 0), # 真の最適双対解
(10, 0, 10),
(20, 0, 0),
]
print("重み (w1, w2, w3) | x1係数 | x2係数 | z(w) ")
print("-" * 50)
for w1, w2, w3 in weights:
c1 = 20 - w1 - 3*w2 - w3
c2 = 10 - w1 - w2 - 2*w3
z = lagrangian_relaxation(w1, w2, w3)
z_str = f"{z:.1f}" if z != float('inf') else "∞ (非有界)"
print(f"({w1:2d}, {w2:2d}, {w3:2d}) | {c1:5.1f} | {c2:5.1f} | {z_str}")
# 真の主問題の最適値を比較用に表示
P = pulp.LpProblem("Primal", pulp.LpMaximize)
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
P += 20*x1 + 10*x2
P += x1 + x2 <= 6
P += 3*x1 + x2 <= 12
P += x1 + 2*x2 <= 10
P.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"\n主問題の最適値（真の値）: {pulp.value(P.objective):.1f}")
実行結果：
重み (w1, w2, w3) | x1係数 | x2係数 | z(w)
--------------------------------------------------
( 0, 6, 2) | 0.0 | 0.0 | 92.0
( 0, 5, 5) | 0.0 | -5.0 | 110.0
( 5, 5, 0) | 0.0 | 0.0 | 90.0
(10, 0, 10) | 0.0 | -10.0 | 160.0
(20, 0, 0) | 0.0 | -10.0 | 120.0
主問題の最適値（真の値）: 90.0
どの重みでも上界（$z(\mathbf{w})$）が主問題の最適値 90 以上になっていることが確認できます。そして $\mathbf{w} = (5, 5, 0)$ で最小値 90 を達成し、これが真の最適値とぴったり一致します。これが「ラグランジュ双対問題の最適解 = LPの双対問題の最適解」の意味です。
LP以外への応用：整数計画
ラグランジュ緩和は 整数計画（MIP） や 非線形計画 にも適用できる汎用的なテクニックです。
例：難しい整数計画問題のうち「特に厄介な制約だけ」を取り除いてラグランジュ緩和することで、解きやすい部分問題に分解できます。
原問題： max cᵀx s.t. Ax ≤ b, Dx ≤ d, x ∈ ℤⁿ
↑ Ax ≤ b が「簡単な制約」、Dx ≤ d が「厄介な制約」とすると
ラグランジュ緩和：
max cᵀx - wᵀ(Dx - d) s.t. Ax ≤ b, x ∈ ℤⁿ
↑ 厄介な制約を消すと簡単な部分問題に
巡回セールスマン問題（TSP）の Held-Karp 緩和や、施設配置問題のラグランジュ緩和などが有名な応用例です。
まとめ
- 緩和問題は「実行可能領域を広げ、目的関数を上に持ち上げる」変形で上界を与える
- ラグランジュ緩和は制約を取り除き、ペナルティ項として目的関数に組み込む手法
- ペナルティ重み $\mathbf{w}$ について上界 $z(\mathbf{w})$ を最小化すると、LPの双対問題が現れる
- 「1次結合で上界」と「ラグランジュ緩和」は同じLPの双対問題に到達する
- ラグランジュ緩和はMIPや非線形最適化にも適用できる汎用的なテクニック