KKT 条件

不等式制約 $g_{i} (x) \leq 0$ のついた最適化問題について、KKT 条件 $\nabla f + \sum μ_{i} \nabla g_{i} = 0$ , $μ_{i} \geq 0$ , $μ_{i} g_{i} = 0$ を立てられる。有効な制約で場合分けして、KKT 点と乗数 $μ_{i}$ を求められる

前提

ラグランジュの未定乗数法（大学数学微分積分）

この技能までの道筋（35 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
偏微分と全微分（大学数学微分積分）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
2 変数関数の極値（大学数学微分積分）
ラグランジュの未定乗数法（大学数学微分積分）

説明

KKT 条件を使うと、 $g_{i} (x) \leq 0$ のような不等式制約がついた最小化問題で、最小点の候補（KKT 点）を連立方程式と符号の条件から絞り込めます。ラグランジュの未定乗数法が扱えるのは等式制約だけですが、KKT 条件はこれを不等式制約に広げたものです。予算や容量に上限がある資源配分や、決められた領域の中での最適設計などで使います。

なぜそうしてよいのか

まず制約が 1 つの場合を考えます。 $g (x) \leq 0$ のもとで $f$ を最小にする点を $x^{*}$ とすると、可能性は 2 通りです。(i) $g (x^{*}) < 0$ （制約が効いていない）のとき、 $x^{*}$ の近くの点はすべて制約を満たすので、 $x^{*}$ は制約なしの極小点です。よって $\nabla f (x^{*}) = 0$ です。(ii) $g (x^{*}) = 0$ （境界上にあり、制約が効いている）のとき、曲線 $g = 0$ は許される領域に含まれるので、 $x^{*}$ はこの曲線上でも最小です。 $\nabla g (x^{*}) \neq = 0$ ならラグランジュの未定乗数法が使えて、ある実数 $μ$ について $\nabla f + μ \nabla g = 0$ が成り立ちます。

(ii) では $μ$ の符号も決まります。 $x^{*}$ から $- \nabla g$ の向きに $t > 0$ だけ少し動くと、 $g \approx g (x^{*}) - t ∣\nabla g ∣^{2} = - t ∣\nabla g ∣^{2} < 0$ となり、許される領域の内側に入ります。 $x^{*}$ は最小点なので、この向きに動いても $f$ は減ってはいけません。この向きの $f$ の変化率は $\nabla f \cdot (- \nabla g) = (- μ \nabla g) \cdot (- \nabla g) = μ ∣\nabla g ∣^{2}$ です。これが $0$ 以上で、しかも $∣\nabla g ∣^{2} > 0$ なので、 $μ \geq 0$ となります。(i) の場合も $μ = 0$ とおけば同じ式 $\nabla f + μ \nabla g = 0$ で書けます。2 つの場合は「 $μ = 0$ または $g = 0$ 」とまとめられます。これを式にしたものが相補性条件 $μg = 0$ です。

制約が複数ある場合も考え方は同じです。効いていない制約（ $g_{i} < 0$ ）は $x^{*}$ の近くでは関係しないので $μ_{i} = 0$ とします。効いている制約だけを等式制約とみなして未定乗数を付け、制約ごとに符号を調べると $μ_{i} \geq 0$ が出ます。ただし、等式制約が複数あるときの未定乗数法や、符号を 1 つずつ調べる議論にはもう少し準備が要ります。そこで複数制約の場合は、次の結果を紹介するにとどめます。効いている制約の勾配が一次独立（どの勾配も、他の勾配の定数倍の和、つまり一次結合では表せない）ならば、最小点では KKT 条件 $\nabla f + \sum μ_{i} \nabla g_{i} = 0$ , $μ_{i} \geq 0$ , $μ_{i} g_{i} = 0$ , $g_{i} \leq 0$ が成り立ちます。制約が 1 つのときは、この仮定は $\nabla g \neq = 0$ のことです。これは最小点が満たすべき必要条件です。したがって、KKT 点はあくまで最小点の候補です。

手順

問題を標準形に直す。最大化なら $- f$ の最小化にする。 $h (x) \geq c$ の形の制約は $c - h (x) \leq 0$ のように、すべて「 $g_{i} \leq 0$ 」の形にそろえる。
KKT 条件を書き出す： $\nabla f + \sum_{i} μ_{i} \nabla g_{i} = 0$ , $μ_{i} \geq 0$ , $μ_{i} g_{i} = 0$ , $g_{i} \leq 0$ 。
各制約ごとに「 $μ_{i} = 0$ （効いていない）」か「 $g_{i} = 0$ （効いている）」かで場合分けする（制約が $m$ 個なら $2^{m}$ 通り）。
各場合で、勾配の式と、等式になった制約を連立して解く。
得られた解が $μ_{i} \geq 0$ と $g_{i} \leq 0$ をすべて満たすか確かめ、満たすものだけを KKT 点として残す。
KKT 点は最小点の候補にすぎない。最小値を求めたいときは、候補（KKT 点のほか、効いている制約の勾配が一次独立でない点も含む）の $f$ の値を比べる。そのうえで、最小値が存在することを別に確かめる。

例題

制約 $x + y \leq 2$ のもとで $f (x, y) = (x - 2)^{2} + (y - 1)^{2}$ を最小にする問題を考える。KKT 点 $(x, y)$ と乗数 $μ$ を、組 $(x, y, μ)$ で求めよ。

例題の解答

【手順1】制約を $g (x, y) = x + y - 2 \leq 0$ とおく。最小化の問題なので、 $f$ はこのまま使える。
【手順2】 $\nabla f = (2 (x - 2), 2 (y - 1))$ 、 $\nabla g = (1, 1)$ である。KKT 条件は次のとおり。
$2 (x - 2) + μ = 0$ , $2 (y - 1) + μ = 0$ , $μ \geq 0$ , $μ (x + y - 2) = 0$ , $x + y \leq 2$ 。
【手順3】 $μ = 0$ の場合（場合 A）と、 $x + y = 2$ の場合（場合 B）に分ける。
【手順4】場合 A：勾配の式から $x = 2, y = 1$ となる。
場合 B：勾配の式から $x = 2 - \frac{μ}{2}$ , $y = 1 - \frac{μ}{2}$ である。これを $x + y = 2$ に代入すると $3 - μ = 2$ となり、 $μ = 1$ を得る。このとき $x = \frac{3}{2}$ , $y = \frac{1}{2}$ である。
【手順5】場合 A は $g (2, 1) = 1 > 0$ で制約を満たさないので捨てる。場合 B は $μ = 1 \geq 0$ 、 $g = 0 \leq 0$ で、どちらの条件も満たすので KKT 点である。なお $\nabla g = (1, 1) \neq = 0$ なので、勾配についての仮定も満たされている。
よって KKT 点と乗数はただ 1 組で、 $(x, y, μ) = (\frac{3}{2}, \frac{1}{2}, 1)$ 。

答え: $(\frac{3}{2}, \frac{1}{2}, 1)$

よくある誤り

制約 $x + y \geq 2$ をそのまま $g = x + y - 2$ として使ってしまう誤り。不等号の向きが逆なので、 $μ$ の符号条件が狂う。正しくは $g = 2 - x - y \leq 0$ と書き直してから、 $\nabla f + μ \nabla g = 0$ , $μ \geq 0$ を立てる。
$μ = 0$ の場合に出た点を、制約を確かめずに採用してしまう誤り。例題の $(2, 1)$ は $\nabla f = 0$ を満たすが、 $g (2, 1) = 1 > 0$ なので候補にならない。正しくは、必ず $g_{i} \leq 0$ を確認する。
$g = 0$ の場合に出た $μ$ が負でも採用してしまう誤り。例題の制約を $x + y \leq 4$ に変えると、 $g = 0$ の場合は $3 - μ = 4$ から $μ = - 1 < 0$ となるので、KKT 点ではない。正しくは、 $μ = 0$ の場合の $(2, 1)$ （ $g = - 1 \leq 0$ ）が KKT 点である。
KKT 点なら必ず最小点だと思い込む誤り。KKT 条件は必要条件にすぎない。例えば $x^{2} - 1 \leq 0$ のもとで $f (x) = - x^{2}$ を最小にする問題では、 $x = 0, μ = 0$ も KKT 条件 $- 2 x + 2 μx = 0$ , $μ \geq 0$ , $μ (x^{2} - 1) = 0$ を満たす。しかし $f (0) = 0$ はこの範囲での最大値である。もう 1 種類の KKT 点 $x = \pm 1$ （ $μ = 1$ ）では $f = - 1$ となり、こちらが最小点である。正しくは、候補の $f$ の値を比べて最小点を判断する。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

凸計画と KKT 条件の十分性（大学数学最適化・線形計画法）