雑記： KKT条件の話 - クッキーの日記

お気付きの点がありましたらご指摘いただけますと幸いです。全体的にきちんとした証明を欠きます。

参考文献

機械学習のための連続最適化 (機械学習プロフェッショナルシリーズ) | 金森敬文, 鈴木大慈, 竹内一郎, 佐藤一誠 |本 | 通販 | Amazon
- 162ページに KKT 条件が出てくる（1次独立制約想定での証明がある）。
Convex Optimization – Boyd and Vandenberghe
- ウェブで読める凸最適化の本で、263ページに Farkas の補題がある。
https://www.jstage.jst.go.jp/article/ieejeiss1987/109/4/109_4_178/_pdf
- ウェブに落ちていた PDF で、183 ページにバナッハ空間かつ制約想定を課さないときの KKT 条件（KKT 条件ではないが）が出てくる。
KKT 条件 - 数理計画用語集
工学基礎最適化とその応用 (新・工科系の数学) | 矢部博 |本 | 通販 | Amazon

注意（2019-07-16 追記）

この記事では適当な制約想定を課してから Farkas の補題によって KKT 条件を得る流れを紹介していますが、KKT 条件を得る流れは他にもたくさんあります。例えば、
- 先に Fritz John の定理を示し、それに適当な制約想定を課して KKT 条件とする（参考文献5. ）。
- 一次独立制約想定を課し、最適解が有効制約について等式制約付き最適化問題の最適解にもなっていることを利用して KKT 条件を得る（参考文献1. ）。
- 強双対性を課し、強双対性から示す（サポートベクターマシンの文脈でよくみられるはず；下記）。
サポートベクターマシンの文脈でみられる（＝強双対性を課した下での）の KKT 条件は、「が存在する」だけでなく、「が存在し、かつこれが双対問題の最適解である」というもっと強いことをいっています（ので、最適化問題を解く代わりにその双対問題を解いてもよい、ということになります）。それは強双対性が満たされている場合にのみ成り立つ話なのでご注意ください。サポートベクターマシンの文脈に絞った KKT 条件を知りたい方は、この記事を読んでも得るものが少ないので、強双対性の下で KKT 条件を示している文献を参照されるのがよいと思います。例えば、以下の書籍の付録Bがそうです。
- カーネル法入門―正定値カーネルによるデータ解析 (シリーズ多変量データの統計科学) | 福水健次 |本 | 通販 | Amazon
この記事は冒頭でサポートベクターマシンに言及していますが、サポートベクターマシンの文脈での最適化問題を想定しているわけではありませんのでご注意ください。

※ キャラクターは架空のものです。

f:id:cookie-box:20190101155733p:plain:w60

サポートベクターマシンの本を読んでいくと、突如として KKT 条件というのが出てきて戸惑いませんか？急に見知らぬ変数と不等式が増えますし、KKT という名前もどこの株式会社かといった感じですし…。

f:id:cookie-box:20190101160814p:plain:w60

Karush–Kuhn–Tucker 条件は不等式制約付きの最適化問題の局所最適解が満たす必要条件だね。

定理．Karush–Kuhn–Tucker（KKT）条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, g_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であり，かつ，ある条件（例えばこの中のどれか）が満たされているものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; g_i(x) \leqq 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $\lambda^\ast \in \mathbb{R}^m$ が存在する．

$\begin{cases} \displaystyle \nabla f (x^\ast) + \sum_{i=1}^m \lambda^\ast_i \nabla g_i (x^\ast) = \vec{0} \\[5pt] g_i(x^\ast) \leqq 0 \; \; (i = 1, \cdots, m) \\[5pt] \lambda^\ast_i g_i (x^\ast) = 0 \; \; (i = 1, \cdots, m) \\[5pt] \lambda^\ast_i \geqq 0 \; \; (i = 1, \cdots, m) \end{cases}$

Wikipedia によると最初はこの条件を発表した Kuhn と Tucker にちなんで呼ばれていたみたいだけど、後に彼らの発表の 12 年前に Karush が修士論文でこの条件を主張していたのが見つかって、彼の名も冠してこの名前になったのかな？

なんと、それで KKT というのですか…研究成果を12年前に修士論文で導出していましたといわれるのもなかなかショックですね。Karush 氏ももっとツイッターで自身の結果を宣伝しておくとよかったのでは？

1939年にツイッターはないからね。

さておき、なぜサポートベクターマシンの本で急に KKT 条件が出てくるのでしょう？ $\lambda^\ast$ （これは $\alpha^\ast$ かもしれないしお手元の本によります）という知らないベクトルが存在するといわれても反応に困るんですが。 $\lambda^\ast$ って何なんです？そしてなぜそのような不等式たちが成り立つんです？そもそも、「最適解はこのような条件たちを満たす」といわれても、だから何なんです？式が増えてかえってややこしくなった気がするんですが…。

$\lambda$ は KKT 乗数ともよばれる、等式制約付き最適化でいうラグランジュ乗数に相当するものだね。それが何なのかというのは、なぜ KKT 条件が成り立つのかを証明する過程で得ないといけないかな。先に、KKT 条件を満たすから何なのかというのは、どこにあるかまるで見当もつかない「最適解」について、「このような条件を満たす」という情報が得られること自体がありがたいんじゃないのないかな？ KKT 条件があるお陰で、これをつかって最適解に向かうアルゴリズムを構築することができる（実際多くのアルゴリズムが KKT 条件を解いていると解釈できるらしい）けど、これがなかったら定義域の1点1点を「不等式制約を満たすか」「これまで探索した点より小さいか」をあてもなく探索しないといけなくて、途方もないよ？それにサポートベクターマシンの場合は、KKT 条件から「限られた一部のデータ（サポートベクター）のみが解となる分離超平面を形づくっている」という重要な事実が直接的にわかるからね。最適解の必要条件がわかることは強力だよ？

うーん、そういわれてみれば最適解について重要な手がかりを与えてくれているような気はしてきましたが…しかし、なぜ最適解では KKT 条件が成り立つんでしょう？どのように考え始めればいいやら…。

そうだな…まず、制約がない場合をイメージしてみると、局所最適解ってどんな点かな？あ、 $x^\ast$ が局所最適解っていうのは、その点 $x^\ast$ を中心にしたある半径 $\delta > 0$ の開球 $B(x^\ast; \delta)$ の中でその点が最小 $\forall x \in B(x^\ast; \delta), \; f(x^\ast) \leqq f(x)$ って意味ね。局所最適解であっても大域最適解とは限らないけど、大域最適解は必ず局所最適解だから、大域最適解がどんな点か調べるのに局所最適解がどんな点かを考えてもいい。

制約がない場合に局所最適解はどんな点かといわれても…制約がないんだったらもう単純に $f(x)$ が一番小さい点でしかないですよね？

うん。言い換えると、 $x^\ast$ からどんな向きに進んでも $f$ の値が「より小さくなる」ことはないよね？

そうですね、もし最適解が平らな場所にあったら、少し進んでも $f$ の値が変わらない（最適解から少し進んでも最適解という状態）ということはあるかもしれませんが、 $f$ の値が小さくなることは絶対にないです。もし小さくなるなら、そこはもはや最適解ではないですから。

「より小さくなることはない」を言い換える。「 $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」。

《注意》この言い換えは $f(x^\ast + s)$ が $f(x^\ast + s) \approx f(x^\ast) + \nabla f(x^\ast)^\top s$ と一次近似できるほど $x^\ast$ に十分近いところでは」のようなイメージで理解できると思いますが、近似的でなくても成り立ちます。が、証明はここでは割愛します。

え、えっと？ $\nabla f(x)$ は $f(x)$ の勾配といって、ヤコビ行列の転置なのですね。

$\nabla f(c)^\top = Df(c) = \displaystyle \left( \frac{\partial f}{\partial x_1}(c) \;\; \cdots \;\; \frac{\partial f}{\partial x_n}(c) \right)$ ならば $\nabla f(x^\ast)^\top$ は $f$ の $x^\ast$ におけるヤコビ行列そのもので、 $\nabla f(x^\ast)^\top s$ は $f$ の起点 $x^\ast$ における増分 $s$ の微分ですね…この微分が負になるような増分は存在しない、ということは…起点 $x^\ast$ からどんな方向付きステップ $s$ だけ進んでも、より小さくなることはない、ということですね。

だから、どんな $s$ でも $\nabla f(x^\ast)^\top s \geqq 0$ でないといけないし、一方、 $-s$ に対しても $-\nabla f(x^\ast)^\top s \geqq 0$ でないといけない。結局、任意の $s$ に対して $\nabla f(x^\ast)^\top s = 0$ でないといけない。であれば、 $\nabla f(x^\ast) = \vec{0}$ でないといけない。制約がないバージョンの「KKT条件」はこれで終わりだ。

定理．制約がないときの1次の必要条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f$ は $x^\ast$ で微分可能であるものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x)$

このとき，以下が満たされる．

$\; \nabla f (x^\ast) = \vec{0}$

これだけですか？ $\lambda^\ast$ などは出てこないんですね。KKT 条件の最初の式のもっとシンプルなのだけ、といった感じでしょうか。

あくまで必要条件だから、 $\nabla f(x) = \vec{0}$ なら $x$ が局所最適解というわけではないからね。…じゃあ等式制約 $h_i(x) = 0 \, (i = 1, \cdots, m)$ がある場合はどうだろう？最適解 $x^\ast$ は依然として「どんな向きに進んでも $f$ の値がより小さくなることはない」点だろうか？

等式制約がある場合は…等式制約を満たす範囲で $f$ が最小の点を探さなければなりませんね。 $x$ が2次元の場合でイメージすると、制約がない場合は2次元平面全体から解を探していたのが、 $h(x)=0$ という制約があるとこれを満たす曲線上でだけ解を探すといった感じです。この場合の $x^\ast$ も「どんな向きに進んでも $f$ の値がより小さくなることはない」点になっているかといわれると…違いますね。 $x^\ast$ はあくまで曲線 $h(x)=0$ 上で一番小さい点です。この曲線をはみ出す向きに進むならば $f(x)$ は小さくならないとは限りません。

つまり、「 $\nabla h(x^\ast)^\top s = 0$ かつ $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」かな？

《注意》というには「このような $s$ が存在するならば $x^\ast$ が局所最適解であることに矛盾」をきちんと示さないといけないですが、 $f, \, h$ が $x^\ast$ で微分可能で $\nabla h(x^\ast) \neq 0$ ならば結果的には大丈夫だと思うんですが、あんまりイメージでものをいうのはよくないと思います。

今度は $h$ の微分も出てきましたね… $\nabla h(x^\ast)^\top s = 0$ とは $x^\ast$ から $s$ だけ進んでも $h$ の値が変わらないということですよね。…なるほど、最適解 $x^\ast$ は「 $h$ の値を変えずに $f$ を減らすような方向付きステップ $s$ が存在しない」点だといいたいのですね？

だから、さっきと同様の議論により、 $\nabla h(x^\ast)^\top s = 0$ を満たす $s$ では $\nabla f(x^\ast)^\top s = 0$ でないといけない（ここで $\nabla h(x^\ast) = 0$ となるような局所最適解 $x^\ast$ については考えないことにする； $h(x) = 0$ 上にこういう点があったら別途調べることにしよう）。ということは、 $\nabla h(x^\ast)$ と $\nabla f(x^\ast)$ って平行でないといけない。 $\nabla h(x^\ast)$ に直交する任意の $s$ が $\nabla f(x^\ast)$ に直交しないといけないからね。

え、直交？ああ、2つのベクトルの内積がゼロということは、直交するということでしたね。

だから、等式制約が1つのバージョンの「KKT条件」はこうなる。

定理．等式制約が1つあるときの1次の必要条件

$x^\ast$ を $\nabla h(x^\ast) = 0$ ではない問題（P）の局所最適解とする．但し， $f, \, h$ は $x^\ast$ で微分可能とする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; h(x) = 0$

このとき，以下を満たす $\lambda^\ast \in \mathbb{R}$ が存在する．

$\begin{cases} \nabla f (x^\ast) + \lambda^\ast \nabla h (x^\ast) = \vec{0} \\[5pt] h(x^\ast) = 0 \end{cases}$

2つ目の条件式の $h(x^\ast) = 0$ は $x^\ast$ が問題（P）の局所最適解だから等式制約を満たしているって当然の話だけど、普通これも合わせてかくね。

あ、今度は $\lambda^\ast$ が出てきましたね…この $\lambda^\ast$ が存在することは $\nabla h(x^\ast)$ と $\nabla f(x^\ast)$ が平行であるための必要十分条件ですね。では KKT 条件の $\lambda^\ast$ も同じ意味なんでしょうか…ってあれ？いまは等式制約が1つのみの場合の条件を考えたんですね。KKT 条件を目標とするなら、等式制約が複数の場合についても考えた方がよいのではないでしょうか。その場合、「 $h_1, \cdots, h_m$ の値を変えずに $f$ を減らすような方向付きステップ $s$ が存在しない」のですよね。なので、 $\nabla h_i(x^\ast)^\top s = 0 \, (i = 1, \cdots, m)$ をすべて満たす $s$ では $\nabla f(x^\ast)^\top s = 0$ でもなければならないということになりますが、これは $\nabla f(x^\ast)$ が $\nabla h_i(x^\ast) \, (i = 1, \cdots, m)$ たちと同じ超平面内にあるというイメージです。とすると、 $\nabla f(x^\ast)$ が $\nabla h_i(x^\ast) \, (i = 1, \cdots, m)$ の線形和でかければよく、上の1つ目の条件式が $\nabla f (x^\ast) + \sum_{i=1}^m \lambda_i^\ast \nabla h_i (x^\ast) = \vec{0}$ と修正されるのではないでしょうか？あ、こうすれば KKT 条件の1つ目の条件式と同じ形になりますね！

その条件式でいいケースと駄目なケースがあるかな。

え？

3次元空間内での等式制約付き最適化を考えてみよう。 $xy$ 平面上にトーラスを置く。このトーラスの表面が $h(x)=0$ だとする。 $h(x)$ はトーラスの外側に向かうほど大きくなる関数とでもしよう。このとき、 $g(x)=0$ の下で $f(x, y, z) = x$ を最小化する点は、トーラスの表面上で $x$ 座標が一番小さい点だよね。この点ではトーラス上の勾配は $x$ 軸のマイナス方向を向いている。他方、 $f(x, y, z) = x$ の勾配は空間内のどこでも $x$ 軸のプラス方向を向いている。確かに2つの勾配は平行になっている。

文章だとわかりづらいですね…絵でも描いてくださいよ…。

じゃあ等式制約をもう1つ増やそう。ドーナツの上にドーナツを重ねるようにトーラスの上にもう1つトーラスを置こう。制約を満たす領域（よく実行可能領域というね）は曲面から曲線になる。2つのトーラスが接する円周上になるからね。

いや、日常でドーナツの上にドーナツを重ねませんよ…。

このとき制約下で $f(x, y, z)=x$ を最小化する点は円周上で $x$ 座標が一番小さい点だけど、この点で $f$ の勾配は、トーラス（下側）の勾配とトーラス（上側）の勾配の線形和になるかな？

あれ、ならないですね。 $f$ の勾配は $-x$ 方向を向いている一方で、トーラスたちの勾配は $+z$ 方向と $-z$ 方向です。これらでは $f$ の勾配をつくれません…。

トーラスどうしが少しでもめり込んでいたらそうならないんだけどね。「どっちのトーラスの勾配にも垂直な向き」がちゃんと「すべての制約からはみ出さない向き」になるから。でも、トーラスどうしが接していると「どっちのトーラスの勾配にも垂直な向き」が「すべての制約からはみ出さない向き」にならないんだよね。勾配どうしが平行になっちゃってるせいで「どっちのトーラスの勾配にも垂直な向き」じゃ制約の中に閉じ込められないって感じかな。

《注意》ドーナツの例が文章で伝わらなかった方は、参考文献1. の 148 ページの例 9.2 が同じ趣旨だったのでこれをご参照ください。

だからもう、制約付き最適化の局所最適解の必要条件を考えるとき、こういうケースは除外しちゃう。

ええ…。

よく仮定されるのがこの中の LICQ（Linear Independence Constraint Qualification）だね。局所最適解 $x^\ast$ では全ての制約の勾配が線形独立であるとするって仮定。

定理．等式制約があるときの1次の必要条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, h_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であり，かつ，LICQ が満たされているものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; h_i(x) = 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $\lambda^\ast \in \mathbb{R}^m$ が存在する．

$\begin{cases} \displaystyle \nabla f (x^\ast) + \sum_{i=1}^m \lambda^\ast_i \nabla h_i (x^\ast) = \vec{0} \\[5pt] h_i(x^\ast) = 0 \; \; (i = 1, \cdots, m) \end{cases}$

上には LICQ とかいたけど、例えば LICQ の1つ上にある LCQ（Linearity Constraint Qualification）を仮定してもいいよ。こっちは全ての制約が線形関数という仮定だね。全ての制約が線形なら「ちょうど局所最適解のところでだけ接する」なんてことにならないからね。ただ LCQ は LICQ よりずっと強い仮定になるね。LICQ や LCQ のような仮定は制約想定（constraint qualification；CQ）といわれるよ。LICQ より下の方の仮定は MFCQ は等式制約のみの場合は LICQ と同じだし、SC は LCQ と同じだけど、それ以外はちょっとよくわかってないや。そもそもこれらの制約想定が不等式制約もある場合のものだけど。

そうです、考えたかったのは不等式制約の場合です。早速そちらを考えていきましょう。これまでと同じように考えると…あれ？えっと、どう考えればいいのでしょう？？

例えば2次元平面内での最適化だったら、等式制約 $h(x)=0$ は実行可能領域をある曲線上に絞り込むようなイメージだけど、不等式制約 $g(x) \leqq 0$ は曲線で囲まれた領域に絞り込むイメージだね。それで、不等式制約付き最適化の場合は、考える局所最適解 $x^\ast$ が、領域の境界上にある場合も、領域の内部にある場合もある。不等式制約が複数ある場合は一般に、 $x^\ast$ はある不等式制約たちについては領域の境界上だけど、その他の不等式制約たちについては領域の内部って感じになる。前者の制約では $g_i(x^\ast) = 0$ で、後者の制約では $g_i(x^\ast) < 0$ だね。この前者の $g_i(x^\ast) = 0$ となる制約を「有効」な制約ということが多いよ。まあそれで、不等式制約付き最適化問題の局所最適解 $x^\ast$ は、「有効な $g_i$ を大きくしないままに $f$ を小さくする向きが存在しない」点といえる。

なるほど、「不等式を満たしながら最適化せよ」という問題ですから、「余裕で満たされる」制約もあれば、「ぎりぎり満たされる」制約もありますね。ある制約が余裕で満たされている場合は、その制約は局所最適解が満たす条件に関わってこないということですね。確かに、局所的にはそんな制約は最初からなかったも同然ですもんね。では、「有効なすべての $g_i$ に対して $\nabla g_i(x^\ast)^\top s \leqq 0$ であって、かつ $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」といった感じになるでしょうか？

それだとドーナツ重ね問題が発生するんだよね。ドーナツの内部が負のとき、2つのドーナツが接する円周上が実行可能領域になるけど、この円周上の最適解 $x^\ast$ から $-x$ 方向に向かうベクトル $s$ は $\nabla g_1(x^\ast)^\top s = 0$ も $\nabla g_2(x^\ast)^\top s = 0$ も $\nabla f(x^\ast)^\top s = 0$ も満たしちゃうからね。

では、すべての有効な制約の勾配に LICQ を仮定すればいいですね。

それでもいいけど、もっと弱い仮定もあるよ。この中の LICQ の下にある MFCQ が例えばそう。表の下に LICQ ⇒ MFCQ ってあるよね。MFCQ は $\exists d \in \mathbb{R}^n, \, \nabla g_i(x^\ast) ^\top d < 0$ for all active inequality constraints ―つまり、「すべての有効な制約について $g_i(x^\ast)$ を同時に減らす方向 $d$ が存在する」って感じかな。ドーナツを2つ重ね置きした場合のドーナツが接する円周上にそんな点はないよね。同時に2つのドーナツの内部に向かうベクトルはないからね。

へえ。しかし、なぜその仮定で大丈夫なんです？

まず MFCQ を課さずに以下の上の定理が示せて、それに MFCQ を課すと下の定理が示せるんだよね。あ、 $I(x^\ast)$ は $x^\ast$ において有効な制約の添え字を集めた集合ね。

定理．不等式制約があるときの1次の必要条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, h_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であるものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; g_i(x) \leqq 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $s \in \mathbb{R}^n$ は存在しない．但し， $I(x) = \{i \, | \, g_i(x) = 0\}$ とする．

$\begin{cases} \displaystyle \nabla f (x^\ast) ^\top s < 0 \\[5pt] \nabla g_i (x^\ast) ^\top s < 0 \; \; (i \in I(x) \, ) \end{cases}$

定理．不等式制約があるときの1次の必要条件（MFCQ下）

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, h_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であり，かつ，MFCQ が満たされているものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; g_i(x) \leqq 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $s \in \mathbb{R}^n$ は存在しない．但し， $I(x) = \{i \, | \, g_i(x) = 0\}$ とする．

$\begin{cases} \displaystyle \nabla f (x^\ast) ^\top s < 0 \\[5pt] \nabla g_i (x^\ast) ^\top s \leqq 0 \; \; (i \in I(x) \, ) \end{cases}$

どちらも同じにみえるんですが…あ、よくみると、下の定理では2つ目の条件式にイコールが付いているんですね。というか、下の定理はよくみるとさっき直感的に考えた「有効なすべての $g_i$ に対して $\nabla g_i(x^\ast)^\top s \leqq 0$ であって、かつ $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」と同じですね。イコールがない上の場合は MFCQ は要らないんですか？

うん。もしこのような $s \in \mathbb{R}^n$ が存在したら、 $g_i(x^\ast + ts) < 0$ かつ $f(x^\ast + ts) < f(x^\ast)$ を満たす $t \in \mathbb{R}$ がとれるからね。 $x^\ast$ が局所最適解であることに矛盾する。

では、MFCQ が課された場合は、つまり、 $\exists d \in \mathbb{R}^n, \, \nabla g_i(x^\ast) ^\top d < 0, \, \forall i \in I(x^\ast)$ が成り立つ場合はどうなるんでしょう？

下の定理の場合は、もしこのような $s \in \mathbb{R}^n$ が存在したら、 $s$ を少しずらした $\hat{s}$ が存在して $\nabla f(x^\ast) ^\top \hat{s} < 0, \, \nabla g_i(x^\ast) ^\top \hat{s} < 0, \, \forall i \in I(x^\ast)$ となるようにできる。これに上の定理を用いると $x^\ast$ が局所最適解であることに矛盾する。もし下の定理の2つ目の条件がイコールで成り立っていたら上の定理を適用できないけど、MFCQ ですべての有効な $g_i(x^\ast)$ が減る方向が存在することを仮定しているから、 $s$ を少しずらせばイコールがとれるんだよね。

説明が雑ですね…しかし、下の定理が示せたにしろ、冒頭の KKT 条件とだいぶ違いませんか？いま、「なぜ最適解では KKT 条件が成り立つのか」を知りたいんですが。

この下の定理と KKT 条件は同値だよ。

え、同値なんですか？そうはみえないんですが…。

次の補題をつかう。ここで（１）の $Ax \leqq \vec{0}$ はベクトルの各成分がゼロ以下って意味ね。

補題．Farkas’ lemma

$A \in \mathbb{R}^{m \times n}$ と $c \in \mathbb{R}^n$ に対して次の（１）または（２）が成り立つ．しかし同時に（１），（２）が成立することはない．

（１）　 $\exists x \in \mathbb{R}^n, \; Ax \leqq \vec{0}, \; c^\top x < 0$

（２）　 $\exists y \in \mathbb{R}^m, \; A^\top y + c = \vec{0}, \; y \geqq 0$

どちらか一方が成立し、同時に成立することはない、ですか。不思議な定理ですね。

Farkas の二者択一定理ともいうみたいだね。この（１）の $c$ を $\nabla f(x^\ast)$ に読み替えて、 $A$ を有効な制約について横ベクトル $\nabla g_i(x^\ast)^\top$ を縦に並べた行列に読み替えると、（１）が主張する「このような $x$ が存在する」は、不等式制約があるときの1次の必要条件（MFCQ下）の「このような $s$ は存在しない」の否定になっているよね？

えっと、そのように $c$ と $A$ を読み替えれば、（１）は確かに先ほどの定理を否定のようですね。先ほどの定理では存在しないといったものを存在するといっている。…否定じゃ駄目なんじゃないですか？

さっきの定理を仮定すると（１）が否定される。ということは、必ず（２）が成り立つ。二者択一定理だからね。そして、（２）が成り立つならば、 $y$ が存在する。この $y$ を $\lambda^\ast$ とかき換えるとどうだろう。

（２）の $y$ を $\lambda^\ast$ とかき換えて、 $c$ と $A$ もかき換えると、こうですね。…これ、KKT 条件の1番目と4番目の条件式ですね！

$\begin{cases} \displaystyle \nabla f (x^\ast) + \sum_{i \in I(x)} \lambda^\ast_i \nabla g_i (x^\ast) = \vec{0} \\[5pt] \lambda^\ast_i \geqq 0 \; \; (i = 1, \cdots, m) \end{cases}$

…でもよくみると、1番目の条件式の和が制約が有効な $i$ についてだけになってしまっていますね。それに、2番目と3番目の条件式も足りませんし。

KKT 条件の2番目の条件式は $x^\ast$ が局所最適解であることからただちにしたがうからさっきの定理から示す必要はないよ。そして残りの問題は、制約が有効でない $i$ で $\lambda_i^\ast = 0$ とすれば全部解決するかな。

力尽きた