Karush–Kuhn–Tucker条件

同義語:KKT条件Kuhn–Tucker条件Karush–Kuhn–Tucker conditionsKarush-Kuhn-Tucker conditionsKKT conditions

概要

Karush–Kuhn–Tucker条件(Karush–Kuhn–Tucker conditions)とは、不等式 $g_i(x)\le0$ と等式 $h_j(x)=0$ のもとで $f$ を最小化する問題について、乗数 $\lambda_i\ge0$、$\mu_j$ による勾配の関係 $\nabla f+\sum_i\lambda_i\nabla g_i+\sum_j\mu_j\nabla h_j=0$ と相補性 $\lambda_ig_i=0$ を合わせた 1 次の条件で、KKT条件ともいう。Lagrangeの未定乗数法を不等式へ広げたもので、局所解は LICQ や凸な問題の Slater 条件などの制約想定のもとでこの条件を満たす。関数 $f,g_i$ が凸で $h_j$ が 1 次式なら、この条件は大域解の十分条件である。場合分けで解く手順や、反復法の解の判定に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Lagrangeの未定乗数法, 凸最適化, Farkasの補題

等式の条件のもとでの最小化なら、Lagrangeの未定乗数法 が使える。条件が不等式になると、最小点で不等式が等号になるのかどうかが事前に分からない。たとえば、領域 $y\ge x^2$、$x+y\le2$ の中で点 $(2,1)$ に最も近い点を探す。答えは 2 つの境界の交点 $(1,1)$ で、そこでは $-\nabla f=(2,0)$ が 2 つの境界の外向きの法線の $0$ 以上の係数の和になっている。
$$ (2,0)=\frac23(2,-1)+\frac23(1,1) $$
もし $-\nabla f$ がこの 2 本の法線の作る錐から外れていれば、領域の中に値を下げる向きが残るはずである。これを式にしたものが Karush–Kuhn–Tucker 条件(KKT 条件)である。乗数の符号が $0$ 以上であることと、等号にならない不等式の乗数は $0$ であること(相補性)が、Lagrange の条件に加わる。
この記事では、KKT 条件がいつ必要か、いつ十分かを表にまとめ、それを証明する。局所解が KKT 条件を満たすには 制約想定 という条件が要る。また、効いている条件で場合分けして解く手順を例題で示す。

定義と使える条件

$\mathbb{R}^n$ の内積を $a\cdot b$、長さを $\lvert x\rvert$ と書く。

問題の標準形

$f,g_i,h_j\colon\mathbb{R}^n\to\mathbb{R}$($i=1,\dots,m$、$j=1,\dots,p$)について、問題
$$ \text{(P)}\qquad\text{最小化 } f(x)\quad\text{条件 } g_i(x)\le0\ (i=1,\dots,m),\quad h_j(x)=0\ (j=1,\dots,p) $$
を考える。条件をすべて満たす点を 実行可能解、その全体を $X$ と書く。すべての $x\in X$ で $f(x^*)\le f(x)$ となる $x^*\in X$ を 大域解、ある $r>0$ について $\lvert x-x^*\rvert< r$ を満たす $x\in X$ でこの不等式が成り立つものを 局所解 という。$g_i(x)=0$ となる $i$ の全体を $\mathcal A(x)$ と書き、$x$ で 効いている 制約という。

$m=0$ や $p=0$ でもよい。これは 非線形計画法 の問題の書き方である。凸最適化 の記事の $f_0,f_i$ は、ここでの $f,g_i$ にあたる。

KKT 条件

$x^*\in\mathbb{R}^n$ で $f,g_i,h_j$ が微分可能とする。$L(x,\lambda,\mu):=f(x)+\sum_{i=1}^m\lambda_ig_i(x)+\sum_{j=1}^p\mu_jh_j(x)$ を Lagrange 関数 という。$x^*$ と $\lambda\in\mathbb{R}^m$、$\mu\in\mathbb{R}^p$ についての次の 4 つをあわせて Karush–Kuhn–Tucker 条件(KKT 条件)という。

  1. (主実行可能性)$g_i(x^*)\le0$、$h_j(x^*)=0$。
  2. (双対実行可能性)$\lambda_i\ge0$。
  3. (相補性)$\lambda_ig_i(x^*)=0$($i=1,\dots,m$)。
  4. (停留性)$\nabla f(x^*)+\sum_{i=1}^m\lambda_i\nabla g_i(x^*)+\sum_{j=1}^p\mu_j\nabla h_j(x^*)=0$。
    これらを満たす $(x^*,\lambda,\mu)$ を KKT 点、$\lambda,\mu$ を 乗数 という。

相補性は、$g_i(x^*)< 0$ なら $\lambda_i=0$ ということである。したがって停留性は、$-\nabla f(x^*)$ が $\nabla g_i(x^*)$($i\in\mathcal A(x^*)$)の $0$ 以上の係数の和と $\nabla h_j(x^*)$ の 1 次結合の和であることを述べている。$m=0$ なら Lagrangeの未定乗数法 の条件そのものである(等式の乗数は符号が自由なので、$\mu_j$ と $-\mu_j$ のどちらで書いても同じである)。
問題が標準形でないときは、次のように直す。乗数の符号は (P) の形についての約束である。

問題の形直し方結果
$f$ の最大化$-f$ を最小化する停留性は $\nabla f=\sum\lambda_i\nabla g_i+\sum\mu_j\nabla h_j$
$g(x)\ge0$$-g(x)\le0$ とする$L=f-\lambda g$、$\lambda\ge0$
$x_k\ge0$$-x_k\le0$ とする$\partial_kf\ge0$(他の条件がないとき)、$x_k\partial_kf=0$

どの $f$ についても局所解で KKT 条件が成り立つと言うには、制約の形についての条件が要る。これが制約想定である。$x^*\in X$ に対し
$$ \mathcal D(x^*):=\bigl\{d\in\mathbb{R}^n\ \big|\ \nabla g_i(x^*)\cdot d\le0\ (i\in\mathcal A(x^*)),\ \nabla h_j(x^*)\cdot d=0\ (j=1,\dots,p)\bigr\} $$
を 線形化錐 という。制約を $x^*$ で 1 次近似したときに許される向きの全体である。

制約想定

$x^*\in X$ で $g_i$ が微分可能、$h_j$ が $C^1$ 級とする。次の条件を 制約想定 という。

  1. LICQ:$\nabla g_i(x^*)$($i\in\mathcal A(x^*)$)と $\nabla h_j(x^*)$($j=1,\dots,p$)をあわせて線形独立である。
  2. MFCQ(Mangasarian–Fromovitz の条件):$\nabla h_j(x^*)$ が線形独立で、$\nabla h_j(x^*)\cdot v=0$(すべての $j$)、$\nabla g_i(x^*)\cdot v< 0$(すべての $i\in\mathcal A(x^*)$)を満たす $v$ がある。
  3. 線形の制約:$g_i$($i\in\mathcal A(x^*)$)と $h_j$ がすべて 1 次式(定数項があってもよい)である。
  4. Slater 条件:$g_i$ がすべて凸で $h_j$ がすべて 1 次式であり、$g_i(\tilde x)< 0$(すべての $i$)、$h_j(\tilde x)=0$(すべての $j$)を満たす $\tilde x$ がある。

この記事の定理を使う条件は次のとおりである。

  • (i) 関数は考える点で微分可能である。微分できない関数には勾配を 劣微分 に替えた別の形が要る(例:LASSO の最適性条件)。
  • (ii) 必要条件として使うには、制約想定を確かめる。
  • (iii) 十分条件として使うには、$f,g_i$ が凸で $h_j$ が 1 次式であることを確かめる。
  • (iv) 変数は連続の値をとる。

公式の表

問題の仮定制約想定言えること根拠
$x^*$ は局所解LICQKKT 条件を満たす乗数がただ 1 組あるcor-kkt-cq
$x^*$ は局所解MFCQ乗数があり、乗数の全体はコンパクトな凸集合thm-kkt-mfcq
$x^*$ は局所解線形の制約乗数があるcor-kkt-cq
$x^*$ は局所解Slater 条件乗数があるcor-kkt-cq
$x^*$ は局所解なしFritz John の条件($\nabla f$ の係数は $0$ かもしれない)prop-kkt-fritz-john
$f,g_i$ は凸、$h_j$ は 1 次式なしKKT 点の $x^*$ は大域解で、双対ギャップがないthm-kkt-sufficient
$C^2$ 級で、KKT 点なし臨界錐で正定値なら狭義の局所解非線形計画法 の定理「不等式を含む 2 次の十分条件」

$f,g_i$ が凸、$h_j$ が 1 次式で Slater 条件が成り立つなら、$x^*\in X$($f,g_i$ は $x^*$ で微分可能)が大域解であることと、KKT 条件を満たす乗数があることは同値である。大域解は局所解なので、上の表の 4 行目と 6 行目を合わせると分かる。

主定理と証明

乗数は Farkas の補題から出る

乗数の存在と線形化錐

$x^*\in X$ で $f,g_i,h_j$ が微分可能とする。KKT 条件を満たす乗数 $\lambda,\mu$ があるためには、
$$ \nabla f(x^*)\cdot d\ge0\qquad(d\in\mathcal D(x^*)) $$
が必要十分である。

必要性。 乗数があるとする。$d\in\mathcal D(x^*)$ について、停留性に $d$ を掛け、$i\notin\mathcal A(x^*)$ では $\lambda_i=0$ であることを使うと
$$ \nabla f(x^*)\cdot d=-\sum_{i\in\mathcal A(x^*)}\lambda_i\nabla g_i(x^*)\cdot d-\sum_j\mu_j\nabla h_j(x^*)\cdot d\ge0 $$
である。
十分性。 $M$ を、列が $-\nabla g_i(x^*)$($i\in\mathcal A(x^*)$)、$\nabla h_j(x^*)$、$-\nabla h_j(x^*)$ である行列とする。$M^{\mathsf T}d\ge0$ は $d\in\mathcal D(x^*)$ と同じである。よって仮定は、$M^{\mathsf T}d\ge0$、$\nabla f(x^*)\cdot d< 0$ となる $d$ がないことを意味する。Farkasの補題 の定理「Farkas の補題」により、$Mz=\nabla f(x^*)$、$z\ge0$ を満たす $z$ がある($M$ に列がないときは、仮定から $\nabla f(x^*)=0$ である)。$z$ の成分を順に $\lambda_i$($i\in\mathcal A(x^*)$)、$\mu_j^-$、$\mu_j^+$ と名づけ、$\mu_j:=\mu_j^+-\mu_j^-$、$i\notin\mathcal A(x^*)$ では $\lambda_i:=0$ とおくと、$\lambda\ge0$ で、停留性と相補性が成り立つ。$\square$

$x^*$ が局所解なら、$X$ の中に実際に動ける向きでは $f$ は減らない(最適化 の定理「接錐による 1 次の必要条件」)。問題は、$\mathcal D(x^*)$ の向きが本当に $X$ の中に動ける向きかである。1 次近似では許されても、実際には動けないことがある(反例の表の 1・2 行目)。制約想定はこの隔たりを埋める。

主定理:制約想定のもとでの必要性

MFCQ のもとでの必要性

$x^*$ を (P) の局所解とする。$f,g_i$ は $x^*$ で微分可能、$h_j$ は $C^1$ 級で、$x^*$ で MFCQ が成り立つとする。このとき KKT 条件を満たす乗数 $\lambda,\mu$ がある。さらに、乗数 $(\lambda,\mu)$ の全体はコンパクトな凸集合である。

prop-kkt-farkas により、$d\in\mathcal D(x^*)$ で $\nabla f(x^*)\cdot d\ge0$ を示せばよい。$v$ を MFCQ のベクトルとし、$\varepsilon>0$ について $d_\varepsilon:=d+\varepsilon v$ とおく。$\nabla h_j(x^*)\cdot d_\varepsilon=0$ で、$i\in\mathcal A(x^*)$ では $\nabla g_i(x^*)\cdot d_\varepsilon< 0$ である。
$\nabla h_j(x^*)$ は線形独立で $d_\varepsilon$ はそのすべてに直交するので、Lagrangeの未定乗数法 の補題「接ベクトルを速度にもつ曲線」により、$\gamma(0)=x^*$、$\gamma'(0)=d_\varepsilon$ で $h_j(\gamma(t))=0$(すべての $j$)を満たす微分可能な曲線 $\gamma$ がある($p=0$ なら $\gamma(t)=x^*+td_\varepsilon$ とする)。
$t>0$ が小さければ $\gamma(t)\in X$ である。実際、$i\in\mathcal A(x^*)$ なら $\frac d{dt}g_i(\gamma(t))\big|_{t=0}=\nabla g_i(x^*)\cdot d_\varepsilon< 0$ で $g_i(\gamma(0))=0$ なので $g_i(\gamma(t))< 0$ であり、$i\notin\mathcal A(x^*)$ なら $g_i(x^*)< 0$ と連続性による。$x^*$ は局所解なので $f(\gamma(t))\ge f(x^*)$ であり、$t\to+0$ の微分係数から $\nabla f(x^*)\cdot d_\varepsilon\ge0$ である。$\varepsilon\to+0$ とすると $\nabla f(x^*)\cdot d\ge0$ である。
乗数の全体。 乗数の全体は 1 次の等式と不等式で決まるので閉じた凸集合である。有界でないとすると、乗数の列 $(\lambda^k,\mu^k)$ で長さが $\infty$ に発散するものがある。長さで割って部分列をとると、長さ $1$ の $(\bar\lambda,\bar\mu)$ に収束し、$\bar\lambda\ge0$、$i\notin\mathcal A(x^*)$ で $\bar\lambda_i=0$ である。停留性を長さで割って極限をとると
$$ \sum_{i\in\mathcal A(x^*)}\bar\lambda_i\nabla g_i(x^*)+\sum_j\bar\mu_j\nabla h_j(x^*)=0 $$
である。$v$ との内積をとると $\sum_{i\in\mathcal A(x^*)}\bar\lambda_i\nabla g_i(x^*)\cdot v=0$ で、各項は $0$ 以下なので $\bar\lambda=0$ である。すると $\nabla h_j(x^*)$ の線形独立性から $\bar\mu=0$ で、長さ $1$ に反する。$\square$

ほかの制約想定

$x^*$ を (P) の局所解とし、$f,g_i$ は $x^*$ で微分可能、$h_j$ は $C^1$ 級とする。

  1. $x^*$ で LICQ が成り立つなら、KKT 条件を満たす乗数がただ 1 組ある。
  2. $x^*$ で線形の制約の条件が成り立つなら、乗数がある。
  3. Slater 条件が成り立つなら、乗数がある。

1。 勾配を行に並べた行列は行について線形独立なので、$\nabla g_i(x^*)\cdot v=-1$($i\in\mathcal A(x^*)$)、$\nabla h_j(x^*)\cdot v=0$ に解 $v$ があり、MFCQ が成り立つ。2 組の乗数の差は勾配の線形関係を与えるので $0$ である。
2。 $d\in\mathcal D(x^*)$ とする。$g_i$($i\in\mathcal A(x^*)$)と $h_j$ は 1 次式なので、$t>0$ で $g_i(x^*+td)=t\nabla g_i(x^*)\cdot d\le0$、$h_j(x^*+td)=0$ である。効いていない $g_i$ は連続性により $t$ が小さければ負である。よって $x^*+td\in X$ で、$f(x^*+td)\ge f(x^*)$ から $\nabla f(x^*)\cdot d\ge0$ である。prop-kkt-farkas を使う。
3。 $v:=\tilde x-x^*$ とする。$i\in\mathcal A(x^*)$ なら、$g_i$ は接平面より上にあるので(凸最適化 の補題「凸関数は接平面より上にある」)$\nabla g_i(x^*)\cdot v\le g_i(\tilde x)-g_i(x^*)=g_i(\tilde x)< 0$ である。$h_j$ は 1 次式なので $\nabla h_j(x^*)\cdot v=h_j(\tilde x)-h_j(x^*)=0$ である。$\nabla h_j(x^*)$ が線形独立なら MFCQ である。線形独立でないときは、$\nabla h_j$ のうち線形独立な極大の組を残す。残りの $h_j$ は、$X\ne\emptyset$ なので残した式の 1 次結合であり、取り除いても $X$ は変わらない。取り除いた式の乗数を $0$ とすればよい。$\square$

3 では $f$ の凸性を使っていない。$f$ も凸のときの 3 は 凸最適化 の定理「Karush–Kuhn–Tucker の定理」の 2 にあたる(そこでは等式の制約のない形を強双対性から導いている)。

凸な問題では十分である

凸な問題での十分性

$f,g_i$ を凸関数、$h_j$ を 1 次式とし、$f,g_i$ は $x^*$ で微分可能とする。$(x^*,\lambda,\mu)$ が KKT 点なら、$x^*$ は (P) の大域解である。さらに、$\theta(\lambda',\mu'):=\inf_{x\in\mathbb{R}^n}L(x,\lambda',\mu')$ とおくと、
$$ \theta(\lambda,\mu)=\max_{\lambda'\ge0,\ \mu'}\theta(\lambda',\mu')=f(x^*) $$
である。つまり $(\lambda,\mu)$ は Lagrange 双対問題の解で、双対ギャップはない。

$\lambda\ge0$ なので、$\varphi:=L(\cdot,\lambda,\mu)$ は凸関数で、$x^*$ で微分可能である。停留性は $\nabla\varphi(x^*)=0$ なので、凸最適化 の補題「凸関数は接平面より上にある」から、すべての $x$ で $\varphi(x)\ge\varphi(x^*)$ である。主実行可能性と相補性から $\varphi(x^*)=f(x^*)$ である。よって $\theta(\lambda,\mu)=f(x^*)$ である。
$x\in X$ と $\lambda'\ge0$、$\mu'$ について $L(x,\lambda',\mu')\le f(x)$ なので、$\theta(\lambda',\mu')\le f(x)$ である。$x=x^*$ とすると $\theta(\lambda',\mu')\le f(x^*)=\theta(\lambda,\mu)$ である。また、$\lambda'=\lambda$、$\mu'=\mu$ とすると $f(x^*)=\theta(\lambda,\mu)\le f(x)$($x\in X$)である。$\square$

関数の定義域が $\mathbb{R}^n$ 全体でなく、$X$ を含む開凸集合 $U$ の場合も、下限を $U$ の上でとれば同じ証明で成り立つ。

制約想定なしで言えること

Fritz John の条件

$x^*$ を (P) の局所解とし、$f,g_i$ は $x^*$ で微分可能、$h_j$ は $C^1$ 級とする。このとき、すべてが $0$ ではない $\lambda_0\ge0$、$\lambda\ge0$、$\mu$ で、相補性と
$$ \lambda_0\nabla f(x^*)+\sum_i\lambda_i\nabla g_i(x^*)+\sum_j\mu_j\nabla h_j(x^*)=0 $$
を満たすものがある。

狭義の降下の向きがないことに Gordan の定理を使う
証明を開く

$\nabla h_j(x^*)$ が線形従属なら、その関係を $\mu$ とし $\lambda_0=0$、$\lambda=0$ とする。線形独立とし、$K:=\{v\mid\nabla h_j(x^*)\cdot v=0\ (\forall j)\}$ とおく。$K=\{0\}$ なら $\nabla f(x^*)$ は $\nabla h_j(x^*)$ の 1 次結合なので $\lambda_0=1$、$\lambda=0$ でよい。以下 $K\ne\{0\}$ とする。$v\in K$ で $\nabla f(x^*)\cdot v< 0$、$\nabla g_i(x^*)\cdot v< 0$($i\in\mathcal A(x^*)$)となるものがあれば、thm-kkt-mfcq の証明と同じ曲線 $\gamma$ の上で $\gamma(t)\in X$、$f(\gamma(t))< f(x^*)$ となり、局所解であることに反する。$K$ の基底を列に並べた行列を $Z$ とする。$v=Zw$ と書くと、$w$ の連立不等式 $Z^{\mathsf T}\nabla f(x^*)\cdot w< 0$、$Z^{\mathsf T}\nabla g_i(x^*)\cdot w< 0$ に解がない。Farkasの補題 の系「Gordan の定理」により、すべてが $0$ ではない $\lambda_0\ge0$、$\lambda_i\ge0$($i\in\mathcal A(x^*)$)で、$a:=\lambda_0\nabla f(x^*)+\sum_i\lambda_i\nabla g_i(x^*)$ が $Z^{\mathsf T}a=0$ を満たすものがある。$a$ は $K$ に直交するので $\nabla h_j(x^*)$ の 1 次結合である。$i\notin\mathcal A(x^*)$ では $\lambda_i:=0$ とする。$\square$

$\lambda_0>0$ なら全体を $\lambda_0$ で割って KKT 条件になる。MFCQ のもとでは $\lambda_0=0$ が起きない。$\lambda_0=0$ の解は $f$ の情報を含まない。

計算の手順

  1. 標準形に書く:(P) の形に直し、Lagrange 関数を書く。
  2. 解の存在を確かめる:実行可能集合がコンパクトなど(最適化 の定理「最適解の存在」)。存在が分からないと、KKT 点の比較だけでは解と言えない。
  3. 制約想定を調べる:凸な問題なら Slater 条件を調べる。そうでなければ、LICQ が満たされない実行可能な点を求める。
  4. 効いている制約で場合分けする:$\mathcal A\subset\{1,\dots,m\}$ ごとに、$i\in\mathcal A$ で $g_i=0$、$i\notin\mathcal A$ で $\lambda_i=0$ とおく。不等式が $m$ 個なら場合は $2^m$ 個である。
  5. 連立方程式を解く:停留性、$g_i=0$($i\in\mathcal A$)、$h_j=0$ を解く。
  6. ふるいにかける:下の表のとおりである。
  7. 結論を出す:残った候補の値を比べる。
    調べて分かること扱い
    解が実行可能でない捨てる
    乗数に負の成分があるKKT 点でないので捨てる(制約想定が成り立つ点なら解でない)
    凸な問題で、すべての条件が通った大域解である(thm-kkt-sufficient)。残りの場合は調べなくてよい
    凸でない問題で、すべての条件が通った候補として残す
    制約想定が満たされない実行可能な点KKT 点でなくても候補に足す(ex-kkt-cusp)

例題

効いている制約で場合分けする

問い:最小化 $f(x,y)=(x-2)^2+(y-1)^2$、条件 $g_1=x^2-y\le0$、$g_2=x+y-2\le0$。
使う公式:def-kkt-conditions、thm-kkt-sufficient。
答え:解は $(1,1)$、乗数は $\lambda_1=\lambda_2=\frac23$、最小値は $1$ である。

途中の計算を開く

$f,g_1$ は凸、$g_2$ は 1 次式である。停留性は $2(x-2)+2\lambda_1x+\lambda_2=0$、$2(y-1)-\lambda_1+\lambda_2=0$ である。場合分けの結果は下の表のとおりである。$\mathcal A=\{1\}$ の場合は $\lambda_1=2(y-1)$ と $y=x^2$ から $2x^3-x-2=0$ となる。$\mathcal A=\{1,2\}$ の場合は $x^2+x-2=0$ より $x=1,-2$ である。$(1,1)$ で $\lambda\ge0$ なので、thm-kkt-sufficient によりこれが大域解である。

$\mathcal A$候補乗数判定
なし$(2,1)$$\lambda=(0,0)$$g_1=3>0$ で実行可能でない
$\{2\}$$(\frac32,\frac12)$$\lambda=(0,1)$$g_1=\frac74>0$ で実行可能でない
$\{1\}$$(1.16537,\ 1.35809)$$\lambda_1\approx0.71619$$g_2\approx0.52347>0$ で実行可能でない
$\{1,2\}$$(1,1)$$\lambda=(\frac23,\frac23)$すべて通る
$\{1,2\}$$(-2,4)$$\lambda=(-\frac{14}3,-\frac{32}3)$乗数が負

図: 放物線と直線で囲まれた領域と、目的関数の等高線。点 (1,1) で、目的関数の負の勾配が 2 つの制約の勾配の作る錐の中にある 図: 放物線と直線で囲まれた領域と、目的関数の等高線。点 (1,1) で、目的関数の負の勾配が 2 つの制約の勾配の作る錐の中にある

乗数は値の変化率

問い:$b>0$ について、最小化 $x^2+y^2$、条件 $b-x-y\le0$ を解き、最小値 $p(b)$ と乗数を比べる。
使う公式:thm-kkt-sufficient。
答え:$x=y=\frac b2$、$\lambda=b$、$p(b)=\frac{b^2}2$ で、$p'(b)=b=\lambda$ である。$b=2$ なら解は $(1,1)$、$\lambda=2$、$p(2)=2$ である。

途中の計算を開く

$\lambda=0$ なら $(0,0)$ で実行可能でない。$\lambda>0$ なら $x+y=b$ で、停留性 $2x-\lambda=2y-\lambda=0$ から $x=y=\frac b2$、$\lambda=b>0$ である。問題は凸なので大域解である。$b$ を増やすと条件は厳しくなり、最小値は $\lambda$ の割合で増える。等式の条件での一般の形は Lagrangeの未定乗数法 の命題「乗数は最適値の変化率」にある。

注水の問題

問い:$\alpha=(0.5,\ 1,\ 2)$ について、最小化 $-\sum_{i=1}^3\log(\alpha_i+x_i)$、条件 $x_i\ge0$、$x_1+x_2+x_3=1$(通信路への電力の配分。BV04 Example 5.2、pp. 245–246)。
使う公式:def-kkt-conditions、thm-kkt-sufficient。
答え:$x=(0.75,\ 0.25,\ 0)$、水位 $w=1.25$、$\mu=0.8$、$\lambda=(0,0,0.3)$、最小値は約 $-1.13943$ である。

途中の計算を開く

$g_i=-x_i$、$h=x_1+x_2+x_3-1$ とすると、停留性は $-\frac1{\alpha_i+x_i}-\lambda_i+\mu=0$ である。$x_i>0$ なら $\lambda_i=0$ で $\alpha_i+x_i=\frac1\mu=:w$ である。$x_i=0$ なら $\lambda_i=\mu-\frac1{\alpha_i}\ge0$ で、これは $w\le\alpha_i$ と同値である。よって $x_i=\max\{0,w-\alpha_i\}$ で、$w$ は和が $1$ になるように決まる。$w=1.25$ なら $0.75+0.25+0=1$ である。$\mu=\frac1w=0.8$、$\lambda_3=0.8-\frac12=0.3$ である。目的関数の定義域は $\mathbb{R}^3$ 全体でないが、thm-kkt-sufficient のあとの注意により大域解である。

分離の余裕を最大にする

問い:平面の点 $p_1=(1,1)$、$p_2=(2,2)$(ラベル $+1$)、$p_3=(0,0)$(ラベル $-1$)を直線 $w\cdot p+\beta=0$ で分ける。最小化 $\frac12\lvert w\rvert^2$、条件 $1-y_i(w\cdot p_i+\beta)\le0$ を解く($y=(1,1,-1)$、変数は $w\in\mathbb{R}^2$ と $\beta$)。
使う公式:def-kkt-conditions、thm-kkt-sufficient。
答え:$w=(1,1)$、$\beta=-1$、$\lambda=(1,0,1)$、最小値は $1$ である。効いている点 $p_1,p_3$ だけが解を決める。

途中の計算を開く

停留性は $w=\sum_i\lambda_iy_ip_i$、$\sum_i\lambda_iy_i=0$ である。$\lambda=(1,0,1)$ なら $w=(1,1)$、$\lambda_1-\lambda_3=0$ である。余裕は $y_i(w\cdot p_i+\beta)-1=0,\ 2,\ 0$ で、$p_2$ だけが効いていないので $\lambda_2=0$ と合う。問題は凸なので大域解である。

これはハードマージンの サポートベクターマシン の小さな場合である。一般の場合に KKT 条件から双対問題を導き、解が効いている点(サポートベクター)だけで決まることは、同記事の定理「双対問題とサポートベクター」で示す。

解が KKT 点でない問題

問い:最小化 $x$、条件 $g(x,y)=y^2-x^3\le0$。
答え:解は $(0,0)$ だが、KKT 点は 1 つもない。場合分けだけでは解を見落とす。

確認を開く

$x^3\ge y^2\ge0$ から $x\ge0$ なので、$(0,0)$ は大域解である。停留性は $1-3\lambda x^2=0$、$2\lambda y=0$ である。1 つ目から $\lambda\ne0$、2 つ目から $y=0$ で、相補性から $x=0$ となり、1 つ目に反する。$\nabla g(0,0)=0$ なので LICQ も MFCQ も満たされていない。実行可能集合に内点はあるが、$g$ は凸でないので Slater 条件は成り立たない。

使える条件と反例

各行は 1 つの条件だけを外している。

外す条件反例成り立たなくなること
制約想定最小化 $x$、条件 $x^2\le0$解 $x=0$ が KKT 点でない
Slater 条件の $g_i$ の凸性最小化 $-x_1$、条件 $x_2-(1-x_1)^3\le0$、$-x_2\le0$$(0,\frac12)$ で不等式は真に成り立つが、解 $(1,0)$ は KKT 点でない
LICQ(乗数の一意性)最小化 $y$、条件 $x-y\le0$、$-x-y\le0$、$-y\le0$原点の乗数が $\lambda=(t,t,1-2t)$($0\le t\le\frac12$)と 1 組に決まらない
十分性の $f$ の凸性最小化 $-x^2$、条件 $x-1\le0$、$-x-1\le0$KKT 点 $x=0$ は最大点である
十分性の $g_i$ の凸性最小化 $x$、条件 $1-x^2\le0$KKT 点 $x=1$($\lambda=\frac12$)は大域解でない
十分性の $h_j$ が 1 次式最小化 $x$、条件 $x^2+y^2-1=0$KKT 点 $(1,0)$($\mu=-\frac12$)は最大点である
乗数の符号最小化 $x^2$、条件 $x-1\le0$$x=1$ は $\lambda=-2$ で残りの 3 条件を満たすが解でない
相補性最小化 $x^2$、条件 $1-x\le0$$x=2$、$\lambda=4$ は残りの 3 条件を満たすが解でない(解は $x=1$)
表の反例の確かめ
各行の確かめを開く

1 行目:実行可能解は $0$ だけで、停留性は $1+2\lambda\cdot0=1\ne0$ である。線形化錐は $\mathbb{R}$ 全体だが、実際に動ける向きは $0$ だけである。Fritz John の条件は $\lambda_0=0$、$\lambda=1$ で成り立つ。

2 行目:$x_2\ge0$ と $x_2\le(1-x_1)^3$ から $x_1\le1$ なので、$(1,0)$ が大域解である。$(1,0)$ の勾配は $(0,1)$、$(0,-1)$ で、$\nabla f=(-1,0)$ はこれらの 1 次結合でない。$g_1$ は凸でない。

3 行目:原点で 3 つの制約がすべて効いており、勾配は $(1,-1)$、$(-1,-1)$、$(0,-1)$ である。$(0,1)+t(1,-1)+t(-1,-1)+(1-2t)(0,-1)=0$ である。$v=(0,1)$ で MFCQ は成り立つ。乗数の全体はコンパクトである。

5 行目:実行可能集合は $(-\infty,-1]\cup[1,\infty)$ で、$x=1$ は局所解だが、$f$ は下に有界でない。

6 行目:停留性は $1+2\mu x=0$、$2\mu y=0$ で、KKT 点は $(1,0)$($\mu=-\frac12$)と $(-1,0)$($\mu=\frac12$)である。$-1$ が最小値である。

よくある誤り

誤り正しくはなぜ
解なら必ず KKT 点だと思う制約想定が要るex-kkt-cusp
KKT 点なら解だと思う凸でなければ一般に解とは限らない反例の表の 4〜6 行目
$g\ge0$ の形のまま $L=f+\lambda g$、$\lambda\ge0$ とする$g\le0$ に直す。$g\ge0$ のままなら $L=f-\lambda g$def-kkt-conditions
等号が成り立たない制約にも乗数を残す効いていない制約の乗数は $0$相補性
乗数が $0$ なら制約は効いていない効いていて乗数が $0$ のこともあるexc-kkt-degenerate
等式を 2 つの不等式に分けてから Slater 条件を調べる分けると Slater 条件は必ず満たされない。等式のまま扱うdef-kkt-cq

演習

直線の上の原点に近い点

最小化 $x^2+y^2$、条件 $x+2y\ge5$ を KKT 条件で解け。

解答を開く

$g=5-x-2y$ とする。$\lambda=0$ なら $(0,0)$ で実行可能でない。$\lambda>0$ なら $x+2y=5$ で、停留性 $2x-\lambda=0$、$2y-2\lambda=0$ から $y=2x$、$x=1$、$y=2$、$\lambda=2$ である。問題は凸なので大域解で、最小値は $5$ である。$\square$

球の中の 1 次式

最小化 $x+y+z$、条件 $x^2+y^2+z^2\le3$ を解け。

解答を開く

$\lambda=0$ なら停留性 $(1,1,1)=0$ となり不可能である。$\lambda>0$ なら $x=y=z=-\frac1{2\lambda}$ で、制約が等号なので $\lambda=\frac12$、解は $(-1,-1,-1)$、最小値は $-3$ である。問題は凸なので大域解である。$\square$

効いていて乗数が 0 の制約

最小化 $x^2$、条件 $x\le0$ の解と乗数を求めよ。

解答を開く

解は $x=0$ で、制約は効いている。停留性 $2x+\lambda=0$ から $\lambda=0$ である。$\square$

補足

  • 名前:条件は Karush の 1939 年の未公刊の修士論文と、Kuhn と Tucker の 1951 年の論文にちなむ(BV04 第 5 章の文献案内、p. 272)。定義と凸の場合の必要十分性は同書 §5.5.3(pp. 243–244)にある。
  • 線形計画:目的関数と制約が 1 次式なら、線形の制約の場合にあたり、KKT 条件は 線形計画法 の定理「相補性条件」と同じものになる。
  • 2 次の条件:KKT 点が局所解かどうかは 1 次の条件では決まらない。非線形計画法 の定理「不等式を含む 2 次の十分条件」を使う。
  • 反復法:場合の数は $2^m$ なので、$m$ が大きければ手で解けない。内点法や逐次 2 次計画法は KKT 条件を反復で解く方法である(非線形計画法)。目的関数を 2 つの凸の項に分けて解く 交互方向乗数法 は Lagrange 関数の鞍点を探す反復法で、止める判定は鞍点の条件の残差で行う。

関連項目

参考文献

[1]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st ed., Cambridge University Press, 2004, §5.5.3 KKT optimality conditions(pp. 243–244)、Example 5.2 Water-filling(pp. 245–246)、第 5 章の文献案内(p. 272)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する