ラグランジュ未定乗数法

制約付きの極値問題を、制約なしの問題に変換する手法。

$$ℒ(x,\lambda )=f(x)+\sum _i{\lambda }_i{h}_i(x)$$

等式制約 $h_i(x)=0$ のもとで $f$ を最適化するとき、 ${\nabla }_xℒ=0$ と ${\nabla }_{\lambda }ℒ=0$ を解く。

幾何的な意味#

最適点では、目的関数の勾配が制約の勾配と平行になる。

$$\nabla f=-\sum _i{\lambda }_i\nabla h_i$$

もし平行でなければ、制約面に沿って $f$ を減らす方向が残っている。 つまり最適ではない。平行になったときに初めて、 制約面上でこれ以上進めなくなる。

乗数の意味#

${\lambda }_i$ は制約を 1 単位緩めたときの目的関数の改善量。 経済学ではシャドープライス、 LP の双対変数と同じもの。

制約が最適解にどれだけ効いているかを定量的に示す。 ${\lambda }_i=0$ なら、その制約は実質的に効いていない。

不等式制約への拡張#

不等式 $g_i(x)\le 0$ を含む場合は KKT 条件になる。 「制約が効いているかどうか」で場合分けが要るのが違い。

参考文献#

• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.（全文公開） https://web.stanford.edu/~boyd/cvxbook/
• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5