双対問題の作り方―LP の例―

双対問題の作り方

以下の最小化問題を考える:

\begin{align} (\text{P})\qquad\min_{x} &\quad f(x) \\ \text{subject to} &\quad g_i(x) \le 0 \quad (i=1,2,\dots,m). \end{align}

関数 $f,\,g_i$ に対する連続性や微分可能性は適当に性質の良いものを考えることにしておく．また，以下で min や max の操作を多用するが，それぞれの存在性を仮定しておく．

ラグランジュ関数 $L:\mathbb{R}^n\times\mathbb{R}^m\to\mathbb{R}$ を以下で定義する:

$$ L(x,\lambda) := f(x) + \sum_{i=1}^{m}\lambda_i g_i(x), \quad (\lambda \geq 0). $$

このとき，適当に $\lambda \ge 0$ を固定して元の問題 P に対する制約条件を "緩和" した次の最適化問題を考える:

\begin{align} (\text{P}(\lambda))\qquad\min_{x} &\quad L(x,\lambda) := f(x) + \sum_{i=1}^{m} \lambda_i g_i(x)\\ \text{subject to} &\quad x \in \mathbb{R}^n. \end{align}

この問題を問題 P に対する "ラグランジュ緩和問題" といい，P($\lambda$) で表すこととする．また，そのときの最適値関数を $L(\lambda)$ で表すこととする．すなわち，

$$ L(\lambda) := \min_x L(x,\lambda) $$

である．

問題 P に対する最適解を $x^\star$ とすると，$x^\star$ は問題 P の制約条件を満たすので

$$ f(x^\star) \ge f(x^\star) + \sum_{i=1}^{m} \lambda_i g_i(x^\star) = L(x^\star,\lambda) $$

を満たす．すなわち，最適化問題 P の最適値 $f(x^\star)$ は，ラグランジュ緩和問題 P($\lambda$) を解くことによってその下界値(ここでいうところの $L(x^\star,\lambda)$)を得ることができる．このとき，緩和に用いたラグランジュ乗数 $\lambda \ge 0$ によって得られる下界値が変わってくる．

そこで，最適なラグランジュ乗数 $\lambda^\star$ が何なのか気になってくる．どうすればよいかというと，ラグランジュ緩和問題の最適値関数 $L(\lambda)$ を $\lambda$ に関して最大化した問題を考えればよい．すなわち，以下の最大化問題:

\begin{align} (\text{D}(\lambda))\qquad\max_{\lambda} &\quad L(\lambda)\\ \text{subject to} &\quad \lambda \geq 0 \end{align}

を解いて得られる $\lambda$ が気になるわけであり，この D($\lambda$) が最適化問題 P に対する双対問題というわけである．

おまけ: LP の場合

標準的な LP に対するラグランジュ双対問題がどのように導出されるのか見てみよう．以下の LP を考える:

\begin{align} (\text{P})\qquad\min_{x} &\quad c^\top x \\ \text{subject to} &\quad Ax \ge b,\,x\ge 0. \end{align}

ラグランジュ関数 $L$ を以下で定義する:

$$ L(x,\lambda) := c^\top x + \lambda^\top(b-Ax), \quad (\lambda \geq 0). $$

ラグランジュ緩和問題は次のように書ける:

\begin{align} (\text{P}(\lambda))\qquad\min_{x} &\quad L(x,\lambda) := c^\top x + \lambda^\top(b-Ax) \\ \text{subject to} &\quad x \ge 0. \end{align}

ここで，$x$ に関する非負制約もラグランジュ関数に取り込んでラグランジュ緩和問題を $x$ に関する無制約問題としてもいいのだが，$x\ge 0$ を残しても同様の議論ができるのでこのまま進めることにする．さて，ラグランジュ緩和問題 P($\lambda$) の目的関数は $x$ の項と $\lambda$ の項について整理してあげると

$$ L(x,\lambda) = (c-A^\top \lambda)^\top x + b^\top\lambda $$

となり，$b^\top\lambda$ の部分は $x$ に依存しない．一方，$c-A^\top\lambda$ について，$(A^\top\lambda)_i < 0$ なる $i\in[m]$が存在すると，対応する $x_i$ の値を大きくすることで幾らでも目的関数値を改善することができてしまうので，$c-A^\top\lambda \ge 0$ であることが必要である．また，ラグランジュ緩和問題に対する最適値関数 $L(\lambda)$ は $L(\lambda):=\min\{L(x,\lambda)\mid x\ge 0\}$ で定義されるが，$\lambda$ に関する部分は $b^\top\lambda$ のみであることに注意すると，ラグランジュ双対問題は以下で定式化される:

\begin{align} (\text{D}(\lambda))\qquad\max_{\lambda} &\quad b^\top\lambda\\ \text{subject to} &\quad A^\top\lambda\le c,\,\lambda \geq 0. \end{align}