ラグランジュの未定乗数法#

制約条件付きの凸最適化を解析的に解く方法としてよく用いられる方法。

大まかには、以下の手続きで問題の制約を緩和して解く。

(1) 微分可能な凸関数f(x)に対する制約付き最小化問題があるとする。

minxf(x)subject tog(x)0

(2) ラグランジュ未定乗数という未知の値λ0を用いて、ラグランジュ関数ラグランジアン

L(x,λ)=f(x)+λ(g(x)0)=f(x)+λg(x)

を作る。

(3) ラグランジュ双対問題

maxλL(x,λ)subject toλ0

を解いていく。L(x,λ)xで微分してゼロとおき、

0=Lx=fx+λgx

これを解いて最適解λ,xを得る。この解xは元の最小化問題(主問題)の解と一致することが知られている。

用語#

ラグランジュ緩和#

以下のような最適化問題があるとする

minimize f(x)subject to gi(x)=bi(i=1,...,k)hj(x)bj(j=1,...,l)

この問題の制約を緩和して、もう少し簡単な問題にするアプローチの一つがラグランジュ緩和である。

例えば等式制約gi(x)=biを適当な数値βi倍して目的関数に入れる。

ラグランジュ双対問題#

微分可能な凸関数fi(x),(i=0,...,m)に対する制約付き最小化問題

minxf0(x)subject tofi(x)ai(i=1,...,m)

のラグランジュ双対問題とは、ラグランジュ未定乗数λiとラグランジュ関数(ラグランジアン)

L(x,λ)=f0(x)+i=1mλi(fi(x)ai)

を用いて、以下のように定義される。

maxλinfxL(x,λ)subject toλ0

図示#

『読んで理解する経済数学』#

https://tomoyatajika.notion.site/15-97eb29df07f94478ab0ce28dc2b991df

https://twitter.com/tmytjk/status/1726772898235625921

参考#