凸最適化問題と双対理論

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：凸集合と凸関数・不等式制約とKKT条件　|　関連：線形計画の双対性

要点（BLUF）

凸最適化問題は 凸関数を凸集合上で最小化する問題。局所最適＝大域最適（凸集合と凸関数）。
ラグランジュ双対：制約を乗数で目的に取り込み、 $\lambda$ について最小化した 双対関数を最大化する。
弱双対は常に成立、強双対は Slater 条件（狭義実行可能点が存在）で成立。LP 双対（線形計画の双対性）の一般化。

凸最適化問題の標準形

\min_x f_0(x) \quad \text{s.t.}\quad f_i(x) \le 0\ (i=1..m),\ Ax = b

ここで $f_0,\dots,f_m$ が 凸関数、等式制約が アフィン（線形）。実行可能領域は凸集合の交わりで凸、目的が凸なので、これは凸問題。よって 任意の KKT 点が大域最適（不等式制約とKKT条件の凸版）。

ラグランジュ双対

ラグランジュ関数：

\mathcal{L}(x,\lambda,\nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \nu^\top(Ax-b)

双対関数は $x$ について下限を取ったもの：

g(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu)

$g$ は（ $\mathcal{L}$ が $\lambda,\nu$ について線形なので）常に凹関数（元が凸でなくても！）。双対問題は

\max_{\lambda \ge 0,\ \nu} g(\lambda,\nu)

これは常に凸最適化（凹関数の最大化）。元が難しくても双対は扱いやすい、という非対称性が緩和（整数計画とは・LP緩和）に効く。

弱双対と強双対

弱双対定理（常に成立、凸でなくても）：任意の双対実行可能 $(\lambda\ge0,\nu)$ について

g(\lambda,\nu) \le f_0(x^\star) \quad (\text{双対の値は主の最適値の下界})

差 $f_0(x^\star) - g(\lambda^\star,\nu^\star) \ge 0$ を 双対ギャップという。

強双対定理：問題が凸かつ Slater 条件（ $f_i(x)<0$ を満たす内点が存在）が成り立てば、双対ギャップ＝0：

g(\lambda^\star,\nu^\star) = f_0(x^\star)

LP では無条件に強双対（線形計画の双対性）だったが、一般の凸では Slater のような制約想定が要る。強双対が成り立つとき、KKT 条件（不等式制約とKKT条件）が最適性の 必要十分条件になる。

Pythonで強双対と影の価格を確認

QP $\min (x-1)^2+(y-2)^2$ s.t. $x+y\le2,\ x,y\ge0$ を cvxpy で解き、制約の 双対変数（影の価格） を取り出す。

import numpy as np
import cvxpy as cp

x = cp.Variable(2)
obj = cp.Minimize(cp.sum_squares(x - np.array([1.0, 2.0])))   # (x-1)^2+(y-2)^2
cons = [x[0] + x[1] <= 2, x >= 0]
prob = cp.Problem(obj, cons)
prob.solve()

print(f"主問題 最適値 = {prob.value:.4f}  (x={x.value[0]:.3f}, y={x.value[1]:.3f})")
print(f"制約 x+y<=2 の双対変数(影の価格) = {cons[0].dual_value:.4f}")

実行結果：

主問題 最適値 = 0.5000  (x=0.500, y=1.500)
制約 x+y<=2 の双対変数(影の価格) = 1.0000

無制約最小 $(1,2)$ が制約 $x+y\le2$ に阻まれ、最適は $(0.5,1.5)$ 、最適値 0.5。制約の双対変数は 1.0 ── 「制約を $x+y\le2 \to 2+\epsilon$ と緩めると最適値が約 $1\cdot\epsilon$ 改善する」感度（等式制約とラグランジュ乗数の包絡線定理）。これが LP の影の価格（感度分析）と完全に同じ意味を持つ。

数式の直観的意味

双対関数 $g(\lambda)=\inf_x \mathcal{L}$ は「制約をペナルティ $\lambda$ で柔らかくしたときの最良値」。 $\lambda\ge0$ なら、実行可能点では $\lambda_i f_i\le0$ なので $\mathcal{L}\le f_0$ 、よって下限 $g\le f_0(x^\star)$ ── これが弱双対の1行証明。強双対（ギャップ0）が成り立つ幾何的理由は、凸問題では目的と制約が作る集合が凸で、最適値の点を支える 支持超平面が引けるから（分離定理）。Slater 条件はその超平面が「垂直でない（双対が有界）」ことを保証する。双対変数 $\lambda^\star$ は支持超平面の傾き＝制約の限界価値で、KKT の相補性は「効かない制約には傾き0」を表す。双対は、難しい主問題を凹最大化という解きやすい鏡像に映す ── これが最適化理論で双対が中心に座る理由。

⚠️ よくある誤解・落とし穴

弱双対は常に成立、強双対は条件付き：非凸では双対ギャップが残るのが普通。LP は例外的に無条件。
Slater 条件は十分条件：満たさなくても強双対が成り立つこともある（線形制約のみなら緩い条件で十分）。
双対は常に凸（凹最大化）：元が非凸でも双対は凸。だから双対値は計算しやすい下界になる。
双対変数の符号・スケールは定式化規約に依存。影の価格として読むときは符号を確認。