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

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

等式制約の場合

  • 目的関数$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}^*$が得られる

参考文献