「ラグランジュの未定乗数法」の大枠
「ラグランジュの未定乗数法を理解している人よりも、ラグランジュの未定乗数法を理解していないって言ってる人のほうがバリバリTensorFlowを使ってシステムを作っている……」という身近な闇は置いておいて。
なにはともあれ「ラグランジュの未定乗数法」の大枠を解説していきましょう。
以下の3つに絞りました。
逆に今回はKKT条件、双対性理論、鞍点定理に深入りしません。
1.ラグランジュ関数のイメージを掴む
まずはラグランジュ関数のイメージを掴みましょう。
もともと主問題として
1.目的関数
2.制約条件
があるのを、非負の「ラグランジュ未定乗数」（書籍によっては「ラグランジュ乗数」「双対変数」）を使って、
ラグランジュ関数 ＝
目的関数 ＋ 「ラグランジュ未定乗数」を掛けた制約条件の関数
と、目的関数と制約条件をひとまとめにしているわけです。
で、制約条件が複数になっても、
ラグランジュ関数 ＝
目的関数 ＋ 「ラグランジュ未定乗数」を掛けた制約条件の関数
＋ 「（それぞれの制約に合わせた）別のラグランジュ未定乗数」を掛けた制約条件の関数
というふうにしてひとくくりにすることができる。
これにより、「制約問題」を「極値を求める問題」に変換しちゃえ！というのが「ラグランジュの未定乗数法」の大枠です。
この変換された問題を「主問題」に対し「双対問題」と言います。
2.「双対問題」を作る利点を理解する
次は、「双対問題」を作る利点を知りましょう。
双対問題にすることによって何がうれしいかというと、主問題f(x)の最小値を求める場合、
1.ラグランジュ関数を作る。
2.（条件を満たせば）「ラグランジュ未定乗数」だけでラグランジュ関数を表現できる。
3.2の関数が最大となる「ラグランジュ未定乗数」の最適解を計算する。
4.主問題が最小となるxの最適解を計算する。
というルートで計算ができるようになります。
こうすると、直接主問題のx最適解を求めるより解きやすくなることが多い。
「なんて便利なんだ！」という話ですが「なぜこれが最適解になるのか」という証明がまた大変。
この証明に出てくる鬼門がKKT(カルーシュ・クーン・タッカー)条件です。ここで詰まる。
『自然言語処理のための機械学習入門』なんか途中で説明せず潔く最後の「付録」に突っ込んでますからね。
対して『はじめてのパターン認識』では
1.サポートベクトルマシンで線形分離可能な場合のKKT条件
2.サポートベクトルマシンで線形分離可能でない場合のKKT条件
3.ν-サポートベクトルマシンのKKT条件
と、対応するKKT条件を3つに分けて丁寧に解説しています。それでも厳密性は足りていない。
今回は大枠ですので、ここではKKT条件の解説はしません。
更に、主問題が最小値を求める問題であれば、双対問題は最大値を求める問題になることに注意してください。
この証明をしようと思うと双対性理論（「相対性理論」じゃないよ！）と鞍点定理の話に入っていってややこしい。
で、各書籍ではだいたいこのあたりの解説を端折るかチラッとだけ見せることになります。
3.「ラグランジュ未定乗数」が非負であることを忘れない
あとひとつ重要なのが、「ラグランジュ未定乗数」が非負であるという条件です。
おそらくどの書籍でもしれっと非負条件が書かれていますが、さりげなく書かれているわりにいろいろな場所でこの条件が大きな役割を果たします。
これはまた様々な証明に関わってきますので詳しくは書きませんが、「ラグランジュ未定乗数」が非負であるということだけは覚えておいてください。
まとめますと、
「制約条件のある主問題を解くために、非負の『ラグランジュ未定乗数』を使って解きやすい双対問題となるラグランジュ関数を作る」というのが「ラグランジュの未定乗数法」の大枠になります。
そして、より深く理解したければKKT条件や双対性理論、鞍点定理について学んでいってください。
