ラグランジュ緩和問題#

読み: らぐらんじゅかんわもんだい
英名: Lagrangian Relaxation Problem

元々の数理計画問題に対して，制約の一部を除去（緩和）し，除去した制約については，制約式の違反量に対して，一次のペナルティが課せられるように目的関数を修正した問題の事．この時のペナルティの乗数をラグランジュ乗数と呼ぶ．

例えば，次の数理計画問題

(108)#\[\begin{split}(P) \begin{array}{ll} \min & -2x-3y \\ \mathrm{s.t.} & x \ge 0 \\ & y \ge 0 \\ & x+y \le 1 \end{array}\end{split}\]

において，最後の制約を緩和したラグランジュ緩和問題は次のようになる．

(109)#\[\begin{split}(RP) \begin{array}{ll} \min & -2x-3y+\lambda(x+y-1) \\ \mathrm{s.t.} & x \ge 0 \\ & y \ge 0 \end{array}\end{split}\]

ラグランジュ緩和問題を解く際には，ラグランジュ乗数 \(\lambda\) は通常固定される．ラグランジュ緩和問題 (RP) は，通常元来の問題 (P) の下界値を求める為に解かれるが， (RP) が (P) の下界値を与えるようにするには，ラグランジュ乗数 \(\lambda\) に一定の条件を課す必要がある．この問題の場合，ラグランジュ乗数が \(\lambda \ge 0\) を満たす実数であれば， (RP) は (P) の下界値を与える．