不等式制約とKKT条件

← 数理最適化一覧

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

📎 前提：等式制約とラグランジュ乗数・最適性条件の地図　|　関連：凸最適化問題と双対理論

要点（BLUF）

KKT 条件は不等式制約付き最適化の 1次最適性条件。ラグランジュ乗数を不等式へ拡張したもの。
4本柱：停留性・原始実行可能性・双対実行可能性（ $\lambda \ge 0$ ）・相補性（ $\lambda_i g_i = 0$ ）。
一般には 必要条件だが、問題が凸なら 十分条件にもなり、KKT 点＝大域最適。

概念 ── 効く制約・効かない制約

不等式制約 $g_i(x) \le 0$ は、最適点で2通りに分かれる：

有効（active）： $g_i(x^\star)=0$ （境界にぴったり）。目的を下げたい力を実際に押し返している。
非有効（inactive）： $g_i(x^\star)<0$ （余裕あり）。最適点では無いも同然。

KKT 条件は「有効な制約だけがラグランジュ的に効く」を、相補性という形で表す。

KKT 条件

$\min f(x)$ s.t. $g_i(x)\le0\ (i=1..m),\ h_j(x)=0\ (j=1..p)$ 。ラグランジュ関数

\mathcal{L}(x,\lambda,\mu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \mu_j h_j(x)

に対し、最適点 $x^\star$ で（正則性条件のもと）乗数 $\lambda,\mu$ が存在して：

\begin{aligned} &\text{(1) 停留性：} && \nabla f(x^\star) + \sum_i \lambda_i \nabla g_i(x^\star) + \sum_j \mu_j \nabla h_j(x^\star) = 0 \\ &\text{(2) 原始実行可能性：} && g_i(x^\star) \le 0,\quad h_j(x^\star) = 0 \\ &\text{(3) 双対実行可能性：} && \lambda_i \ge 0 \\ &\text{(4) 相補性：} && \lambda_i\, g_i(x^\star) = 0 \end{aligned}

相補性（4）が肝： $g_i<0$ （非有効）なら $\lambda_i=0$ 、 $\lambda_i>0$ なら $g_i=0$ （有効）。だから「効いている制約だけが乗数を持つ」。双対実行可能性（3） $\lambda_i\ge0$ は「制約は片側からしか押し返さない」を表す（等式制約の $\mu$ は符号自由）。

具体例 ── 制約が解を動かす

$\min (x-2)^2 + (y-2)^2$ s.t. $x+y \le 2,\ x,y\ge0$ 。無制約なら最小は $(2,2)$ だが、これは $x+y=4>2$ で実行不能。制約 $x+y\le2$ が有効になり、最適は境界 $x+y=2$ 上。対称性から $x=y=1$ 。

KKT を確認：有効制約 $g=x+y-2=0$ 、 $\nabla f = (2(x-2),2(y-2)) = (-2,-2)$ 、 $\nabla g=(1,1)$ 。停留性 $\nabla f + \lambda \nabla g = 0$ より $-2 + \lambda = 0$ 、 $\lambda = 2 \ge 0$ （双対実行可能、OK）。相補性も $g=0$ で成立。

from scipy.optimize import minimize

# min (x-2)^2+(y-2)^2 s.t. x+y<=2, x,y>=0
res = minimize(lambda p: (p[0]-2)**2 + (p[1]-2)**2, x0=[0, 0],
               constraints={'type': 'ineq', 'fun': lambda p: 2 - p[0] - p[1]},  # 2-x-y>=0
               bounds=[(0, None), (0, None)])
print(f"数値解  x={res.x[0]:.4f}, y={res.x[1]:.4f}, f={res.fun:.4f}")
print(f"解析解  x=1, y=1, f=2, KKT乗数 lambda=2 (>=0, 制約は有効)")

実行結果：

数値解  x=1.0000, y=1.0000, f=2.0000
解析解  x=1, y=1, f=2, KKT乗数 lambda=2 (>=0, 制約は有効)

無制約最小 $(2,2)$ が制約に阻まれ、境界上の $(1,1)$ に押し戻された。乗数 $\lambda=2>0$ は制約が有効（押し返している）ことを示す。もし制約が $x+y\le10$ なら無制約最小 $(2,2)$ が実行可能で、 $\lambda=0$ （制約は効かない）になる。

凸なら必要が十分に変わる

一般に KKT は 必要条件（最適なら KKT を満たす、逆は不真）。だが $f$ と各 $g_i$ が凸、 $h_j$ が線形で、Slater 条件（狭義に実行可能な内点が存在）が成り立てば、KKT は十分条件にもなる ── KKT を満たす点は 大域最適。これは第1章の予告（最適性条件の地図）の回収であり、凸最適化（凸最適化問題と双対理論）が「KKT を解けば終わり」になる理由。

数式の直観的意味

停留性 $-\nabla f = \sum \lambda_i \nabla g_i + \sum \mu_j \nabla h_j$ （ $\lambda_i\ge0$ ）は、「目的を下げたい力 $-\nabla f$ が、有効制約の外向き法線 $\nabla g_i$ の 非負結合（凸錐） で打ち消されている」状態。下げたい方向はまだあるのに、それが全部「壁の外」を向いていて動けない ── これが制約付き最適の釣り合い。 $\lambda_i\ge0$ は壁が片側にしか押せないこと、相補性は「触れていない壁は押し返さない」ことを表す。等式制約（等式制約とラグランジュ乗数）では壁が両側を縛るので $\mu$ は符号自由。乗数は依然として感度（影の価格）の意味を保ち、双対変数（凸最適化問題と双対理論）として再登場する。

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

KKT は無条件に必要ではない：正則性条件（LICQ・MFCQ・Slater など制約想定）が要る。退化した制約では乗数が存在しないことも。
KKT 点＝最適とは限らない（非凸では）。凸性＋制約想定があって初めて十分条件。
相補性を見落とさない：非有効制約の乗数はゼロ。全制約に正の乗数を付けてはいけない。
不等式の向き・乗数の符号規約（ $g\le0$ で $\lambda\ge0$ ）を取り違えると条件が逆転する。