ラグランジュの未定乗数法#
制約条件付きの凸最適化を解析的に解く方法としてよく用いられる方法。
大まかには、以下の手続きで問題の制約を緩和して解く。
(1) 微分可能な凸関数
(2) ラグランジュ未定乗数という未知の値
を作る。
(3) ラグランジュ双対問題
を解いていく。
これを解いて最適解
用語#
ラグランジュ緩和#
以下のような最適化問題があるとする
この問題の制約を緩和して、もう少し簡単な問題にするアプローチの一つがラグランジュ緩和である。
例えば等式制約
ラグランジュ双対問題#
微分可能な凸関数
のラグランジュ双対問題とは、ラグランジュ未定乗数
を用いて、以下のように定義される。
図示#
『読んで理解する経済数学』#
https://tomoyatajika.notion.site/15-97eb29df07f94478ab0ce28dc2b991df
参考#
『言語処理のための機械学習入門』pp.14-19
https://twitter.com/ToshiMukoyama/status/1726788992438272438
リンクのpdf、英語だがいいかも