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

• 制約条件があり，目的凸関数を解析的に解く場合に使える方法

等式制約の場合

• 目的関数$f({\bold x})$を複数の制約条件$g\_i({\bold x})=0 (i=0\cdots n)$の下で最大化する
• 制約$g_0({\bold x}) = 0, \cdots, g_n({\bold x}) = 0$に対して，それぞれラグランジュ乗数$\lambda_i$を考える
• $n$個のラグランジュ乗数を並べたベクトル${\bold \lambda}$と，$g_i({\bold x})$を$n$個並べたベクトル${\bold g}({\bold x})$
• ラグランジュ関数は$L({\bold x}, \lambda) = f({\bold x}) + {\bold \lambda} \cdot {\bold g}({\bold x})$
• 次の連立方程式を解けば良い
  • $\nabla_{{\bold x}} L = \nabla_{{\bold x}} f({\bold x}) + \nabla_{{\bold x}} ({\bold \lambda} \cdot {\bold g}({\bold x})) = 0$
  • ${\bold g}({\bold x}) = 0$

不等式制約の場合

• 目的関数$f({\bold x})$を制約条件$g_i({\bold x}) \geq 0 (i=0\cdots n)$の下で最大化する
  • ラグランジュ関数$L$は等式制約の場合と同じだが$\lambda \geq 0$とする
  • 制約を満たす${\bold x}$を優遇して$L$をより大きくするため
• 凸関数では，鞍点$({\bold x}^\*, \lambda^\*)$が最適解を与える
  • 鞍点とは，${\bold x}$に関しては最大値となり，$\lambda$に関しては最小値となるような点
  • $L({\bold x}, \lambda^\*) \leq L({\bold x}^\*, \lambda^\*) \leq L({\bold x}^\*, \lambda)$

• 双対問題: 制約が$\lambda \geq 0$のみなので，しばしば問題が解きやすくなる
  1. $L({\bold x}, \lambda)$を最大化する${\bold x}$を求める．それは${\bold x}$を$\lambda$に依存する形${\bold x}^\* (\lambda)$で表される．
  2. $L({\bold x}^\* (\lambda), \lambda)$を$\lambda$について最小化する
  3. $\lambda^\*$が得られ，さらに最適解${\bold x}^\*$が得られる

参考文献

• ラグランジュの未定乗数法 - wikipedia