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 次式なら、この条件は大域解の十分条件である。場合分けで解く手順や、反復法の解の判定に使う。
前提知識: 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$ にあたる。
$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 条件)という。
相補性は、$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$ 級とする。次の条件を 制約想定 という。
この記事の定理を使う条件は次のとおりである。
| 問題の仮定 | 制約想定 | 言えること | 根拠 |
|---|---|---|---|
| $x^*$ は局所解 | LICQ | KKT 条件を満たす乗数がただ 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 行目を合わせると分かる。
$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 行目)。制約想定はこの隔たりを埋める。
$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。 勾配を行に並べた行列は行について線形独立なので、$\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$ の上でとれば同じ証明で成り立つ。
$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
$$
を満たすものがある。
$\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$ の情報を含まない。
| 調べて分かること | 扱い |
|---|---|
| 解が実行可能でない | 捨てる |
| 乗数に負の成分がある | 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 つの制約の勾配の作る錐の中にある
問い:$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 条件から双対問題を導き、解が効いている点(サポートベクター)だけで決まることは、同記事の定理「双対問題とサポートベクター」で示す。
問い:最小化 $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$
最小化 $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$
最小化 $x^2$、条件 $x\le0$ の解と乗数を求めよ。
解は $x=0$ で、制約は効いている。停留性 $2x+\lambda=0$ から $\lambda=0$ である。$\square$
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する