TAKEO

TAKEO

図で理解する最適化シリーズ 第3回 / 全3回

ラグランジュ未定乗数法とKKT条件 — 制約の境界にある最適解

第2回では、偏微分で山の頂上を探した。制約のない滑らかな関数なら、内部の極大点で通常は勾配がゼロになる。

しかし、進める場所が制限されたらどうだろう？

例えば「円周の上しか歩いてはいけない」場合、円周上で最も高い地点でも、山そのものの勾配はゼロとは限らない。

今回はその違いを、ラグランジュ未定乗数法とKKT条件で理解する。

1. 制約があると「勾配ゼロ」が使えない

次の問題を考えよう。

最大化：f(x,y)=x+y制約条件：x2+y2=1\begin{aligned} \text{最大化：}\quad &f(x,y)=x+y\\ \text{制約条件：}\quad &x^2+y^2=1 \end{aligned}

目的関数は単なる平面 z=x+yz=x+y。ところが、動ける場所は xyxy 平面上の半径1の円周だけだ。

∇f=(1,1)\nabla f=(1,1)

この勾配はどこでもゼロではない。それでも円周上には、最大値をとる点が存在する。

インタラクティブ

円に触れる直線と、平行になる勾配

最大化 f = x + y ／ 制約 g = x² + y² − 1 = 0

直線を動かして、円周に触れたまま取れる最大の k を探しましょう。円の内側は今回の制約には含まれません。

単位円と等値線、円周上の点での勾配k=0.849。円と2点で交わる。角度45度での目的関数の勾配は(1,1)、制約の勾配は(1.414,1.414)。xy1−11−1選択点
  • 青の破線：x + y = k
  • 黒い矢印：∇f = (1, 1)
  • 茶色の太い破線矢印：∇g = (2x, 2y)
円周と2点で交わっています

円周上の f の値域は −√2〜√2 です。スライダーと「最大の接点」ボタンで、交わる位置と接する位置を比べてください。

選択点の f = 1.414、∇g = (1.414, 1.414)。2つの勾配は平行です。λ = 1/√2。平行になる候補には最大点と最小点があります。

矢印は同じ倍率で描画しています。黒い矢印と茶色の矢印が重なるときは、方向が揃っていることを表します。直線の k と円周上の選択点は独立に操作できます。

2. なぜ勾配が平行になるのか

制約条件を

g(x,y)=x2+y2−1=0g(x,y)=x^2+y^2-1=0

と書こう。∇g\nabla g は、円周に対する法線方向を向く。

一方、∇f\nabla f は目的関数を最も急速に増やす方向だ。

最適な接点では、円周に沿って少し動いても ff を増やせない。つまり、目的関数の勾配に、円周に沿った成分（接線方向の成分）がない。

したがって、接点では

∇f=λ∇g\boxed{\nabla f=\lambda\nabla g}

が成り立つ。λ\lambda は勾配の大きさの違いを吸収する実数で、ラグランジュ乗数と呼ぶ。

この関係が、ラグランジュ未定乗数法の核心である。

※ 制約曲線が滑らかで ∇g≠0\nabla g\ne\mathbf{0} といった正則性を仮定している。どんな制約式でも無条件に使えるわけではない。

3. ラグランジュ未定乗数法で解いてみる

ラグランジュ関数を

L(x,y,λ)=x+y−λ(x2+y2−1)L(x,y,\lambda)=x+y-\lambda(x^2+y^2-1)

と置く。

x,y,λx,y,\lambda について微分すると、

{∂L∂x=1−2λx=0∂L∂y=1−2λy=0∂L∂λ=−(x2+y2−1)=0\begin{cases} \frac{\partial L}{\partial x}=1-2\lambda x=0\\ \frac{\partial L}{\partial y}=1-2\lambda y=0\\ \frac{\partial L}{\partial\lambda}=-(x^2+y^2-1)=0 \end{cases}

最初の2式から x=yx=y と分かる。これを円の式に代入すると、

2x2=1⟹(x,y)=(12,12),(−12,−12)2x^2=1\quad\Longrightarrow\quad (x,y)=\left(\frac1{\sqrt2},\frac1{\sqrt2}\right), \left(-\frac1{\sqrt2},-\frac1{\sqrt2}\right)

候補は2点。それぞれの目的関数の値は 2\sqrt2 と −2-\sqrt2 だ。

したがって、

fmax⁡=2,(x,y)=(12,12)\boxed{f_{\max}=\sqrt2,\qquad (x,y)=\left(\frac1{\sqrt2},\frac1{\sqrt2}\right)}

偏微分で「勾配がゼロの点」を探したのに対して、今回は「2つの勾配が平行な点」を探したという違いがある。

4. 不等式の制約では何が変わる？

ここまでは g(x,y)=0g(x,y)=0 という等式制約だった。

実際の最適化には、x+y≤3x+y\leq3 のような不等式制約もよく現れる。

次の問題を考える。

最大化：f(x,y)=10−(x−2)2−(y−2)2制約条件：x+y≤3x≥0,y≥0\begin{aligned} \text{最大化：}\quad &f(x,y)=10-(x-2)^2-(y-2)^2\\ \text{制約条件：}\quad &x+y\leq3\\ &x\geq0,\quad y\geq0 \end{aligned}

制約がなければ、山の頂上は (2,2)(2,2) で最大値は 1010。しかし、(2,2)(2,2) は 2+2=4>32+2=4>3 なので実行可能領域の外だ。

実行可能領域は、(0,0),(3,0),(0,3)(0,0),(3,0),(0,3) を頂点とする三角形。その中で最も高い点を探す必要がある。

インタラクティブ

制約を動かすと、最適解はどこへ移る？

最大化 f = 10 − (x − 2)² − (y − 2)² ／ x + y ≤ b、x,y ≥ 0

記事の制約は b = 3。上限 b を緩めたり厳しくしたりして、領域外の山頂と制約付き最適解の位置を比べましょう。

三角形の実行可能領域と円形の等高線制約上限b=3。最適解は(1.5,1.5)、最大値9.500。山頂(2,2)は領域の外。選んだ等高線の高さは9。山頂 (2, 2)最適解 (1.50, 1.50)01122334455xy
  • 緑の三角形：実行可能領域
  • 黒い円：高さ k の等高線
  • 緑の点：最適解
  • 黒い矢印：最適解での ∇f
制約付き最大値 9.500 ／ λ = 1.0

この高さの等高線は実行可能領域と交わります。最適解は斜めの境界上。勾配はゼロではなく、λ(1,1) と釣り合います。

現在の最適解でのKKT条件（α = β = 0）
条件確認
実行可能性x + y − b = 0.00 ≤ 0、x,y > 0 ✓
乗数の非負性λ = 1.0 ≥ 0、α = β = 0 ✓
停留条件∇f − λ(1,1) = (0,0) ✓
相補性λ(x+y−b) = 0、αx = βy = 0 ✓

判定は図の標本点ではなく、最適解 x = y = min(2, b/2) と最大値の式に基づきます。この凹関数と凸な領域ではKKT条件が大域的最適性を保証します。b < 4 では、斜めの境界の法線 ∇g₁ = (1,1) と ∇f が同じ向きです。

5. KKT条件の4つのルール

不等式制約に対する代表的な考え方が、KKT条件（Karush–Kuhn–Tucker条件）だ。

ここでは、最大化問題で制約を gi(x,y)≤0g_i(x,y)\leq0 と書き、

L=f−∑iλigi,λi≥0L=f-\sum_i\lambda_i g_i,\qquad\lambda_i\geq0

という符号の約束を使う。

KKT条件は主に4つで構成される。

条件意味
実行可能性 gi(x,y)≤0g_i(x,y)\leq0制約を破っていない
乗数の非負性 λi≥0\lambda_i\geq0不等式の乗数の符号をそろえる
停留条件 ∇f−∑iλi∇gi=0\nabla f-\sum_i\lambda_i\nabla g_i=0境界の法線方向との釣り合い
相補性条件 λigi(x,y)=0\lambda_i g_i(x,y)=0制約に余裕があれば、その乗数はゼロ

最後の相補性条件が特に重要だ。

  • 制約に余裕がある（gi<0g_i<0）なら、λi=0\lambda_i=0。
  • 乗数が正（λi>0\lambda_i>0）なら、その制約は境界で等号（gi=0g_i=0）になる。
  • 境界で等号でも、乗数がゼロの場合はあり得る。

この「今、本当に効いている制約はどれか」を区別する仕組みが、不等式制約を扱う鍵になる。

KKT条件は、適切な正則性条件の下で最適解が満たす必要条件。常に十分条件になるわけではない。今回のように目的関数が凹で、実行可能領域が凸な最大化問題では、KKTを満たせば大域的最適解といえる。

6. KKT条件で実際に解く

制約をすべて gi≤0g_i\leq0 の形にそろえる。

g1=x+y−3≤0,g2=−x≤0,g3=−y≤0g_1=x+y-3\leq0,\quad g_2=-x\leq0,\quad g_3=-y\leq0

対応する乗数を λ,α,β≥0\lambda,\alpha,\beta\geq0 とすると、

L=10−(x−2)2−(y−2)2−λ(x+y−3)+αx+βyL=10-(x-2)^2-(y-2)^2 -\lambda(x+y-3)+\alpha x+\beta y

停留条件は、

{−2(x−2)−λ+α=0−2(y−2)−λ+β=0\begin{cases} -2(x-2)-\lambda+\alpha=0\\ -2(y-2)-\lambda+\beta=0 \end{cases}

相補性条件は、

λ(x+y−3)=0,αx=0,βy=0\lambda(x+y-3)=0,\qquad \alpha x=0,\qquad \beta y=0

ここでは、最適解が斜めの辺 x+y=3x+y=3 の内部、つまり x>0,y>0x>0,y>0 にあると予想して解いてみよう。

このとき α=β=0\alpha=\beta=0 で、x+y=3x+y=3。停留条件は

−2(x−2)=λ,−2(y−2)=λ-2(x-2)=\lambda,\qquad -2(y-2)=\lambda

となるため、x=yx=y。よって、

x=y=32\boxed{x=y=\frac32}

さらに λ=1≥0\lambda=1\geq0 と分かるので、KKTの符号条件も満たす。目的関数の値は、

f(32,32)=10−(−12)2−(−12)2=192=9.5\begin{aligned} f\left(\frac32,\frac32\right) &=10-\left(-\frac12\right)^2-\left(-\frac12\right)^2\\ &=\boxed{\frac{19}{2}=9.5} \end{aligned}

実際に x,y>0x,y>0 なので、最初の予想とも矛盾しない。目的関数は厳密に凹で、制約領域は凸だから、この解がただ1つの大域的最大解である。

この点での勾配を比較すると、

∇f(32,32)=(1,1),∇g1=(1,1)\nabla f\left(\frac32,\frac32\right)=(1,1),\qquad \nabla g_1=(1,1)

つまり、目的関数の勾配と、有効な制約境界の法線が釣り合っている。等式制約のラグランジュ未定乗数法で見た幾何学が、ここでも登場した。

7. 3つの解法はどうつながるのか

題材幾何学的な見方代表的な解法
線形目的関数＋線形制約直線を動かして多角形に最後に触れる点を探す頂点の比較・線形計画法
滑らかな関数＋制約なし曲面の上で勾配がゼロになる候補を探す偏微分・ヘッセ行列
滑らかな関数＋制約あり動ける方向を考え、境界の法線との釣り合いを調べるラグランジュ未定乗数法・KKT条件

最適化を通して一貫しているのは、「今いる点から、値をさらに改善できる方向が残っているか？」 という問いだ。

制約がなければ、すべての方向へ動ける。制約があれば、動ける方向が絞られる。その違いが、偏微分からKKT条件への発展につながっている。

まとめ

  • 制約なしの滑らかな最適化では、内部の最適解で ∇f=0\nabla f=0 が基本になる。
  • 等式制約では、正則な最適点で ∇f=λ∇g\nabla f=\lambda\nabla g が成り立つ。
  • 不等式制約では、境界で効いている条件と、余裕のある条件を区別する必要がある。
  • KKT条件の相補性条件が、その区別を数式にしている。
  • 局所的な候補が大域的な答えなのかは、凸性・凹性なども確認する。

高校数学の「直線を動かす」という素朴な発想は、実は大学数学の最適化理論までつながっている。

連載を通して見てきた図形は違っていても、 「これ以上よくなる方向がない場所を探す」　という目的は、最初から最後まで同じなのだ。

ホームへ