線型計画問題に対する双対問題の導出

はじめまして，みるか（ @mirucaaura ）です．

本記事では，線型計画問題（Linear Programming Problem; LP）に対する双対問題（Dual Problem）を導出することを目的とします．

注意

本記事を通して変数がベクトルであっても太字で表記しません．

本論

一般的に議論を進めるために，以下で記述される非線形最適化問題を考えます．

\begin{align}[\mathrm{P}]\quad \begin{split} \min_{x\in\mathbb{R}^n} \quad &f(x) \\ \mathrm{s.t.} \quad &g_i(x) \leqq 0 \quad \; (i=1,2,\dots,m) \end{split} \end{align}

ここで，$f:\mathrm{R}^n\to\mathrm{R}$，$g_i:\mathrm{R}^n\to\mathrm{R}\,(i=1,2,\dots,m)$とします．

問題$[\mathrm{P}]$に対して，次式で定義される関数を Lagrange 関数（Lagrangian）といいます：

\begin{eqnarray} L_0(x,\lambda) := \left\{ \begin{array}{l} \displaystyle f(x) + \sum_{i=1}^{m} \lambda_ig_i(x) \quad &(\lambda \geqq 0) \\ -\infty \quad &(\lambda < 0) \end{array}. \right. \end{eqnarray}
ここで，$\lambda = (\lambda_1, \lambda_2, \dots, \lambda_m) \in \mathbb{R}^m$は Lagrange 乗数と呼ばれるベクトルです．
上記で定義した関数$L_0$を用いて，関数$\theta:\mathbb{R}^n\to (-\infty, \infty]$および$\omega_0:\mathbb{R}^m\to[-\infty, \infty)$をそれぞれ次のように定義します：

\begin{align} \theta(x) &:= \sup \{ L_0(x, \lambda) \mid \lambda \in \mathbb{R}^m \}, \\ \omega_0(\lambda) &:= \inf \{ L_0(x, \lambda) \mid x \in \mathbb{R}^n \}. \end{align}
関数$\theta$は標示関数（indicator function）を用いることによって，次のようにも表すことができます：
\begin{eqnarray} \theta(x) &= f(x) + \delta_S (x). \end{eqnarray}
ここで，$S \subseteqq \mathbb{R}^n$は問題$[\mathrm{P}]$の実行可能領域であり，次のように表されます：
\begin{eqnarray} S = \{ x\in\mathbb{R}^n \mid g_i(x) \leqq 0 \quad (i=1,2,\dots,m) \}. \end{eqnarray}
ちなみに，標示関数は与えられた集合に含まれるときは$0$を返し，それ以外は$+\infty$を返すような関数で，次のように定義されます：
\begin{eqnarray} \delta_S(x) := \left\{ \begin{array}{l} 0 \quad & (x \in S) \\ +\infty \quad & (x \notin S) \end{array}. \right. \end{eqnarray}
以上を踏まえると，元の問題$[\mathrm{P}]$は，次の無制約最適化問題と等価であることが分かります：
\begin{align}[\mathrm{P}_0]\quad \min_{x\in\mathbb{R}^n} \quad \theta(x). \end{align}
一方，関数$\omega_0$を最大化する問題：
\begin{align}[\mathrm{D}_0]\quad \max_{\lambda\in\mathbb{R}^m} \quad \omega_0(\lambda) \end{align}
は問題$[\mathrm{P}_0]$に対する Lagrange 双対問題（Lagrangian dual problem）と呼ばれます．また，元の問題$[\mathrm{P}_0]$は主問題（primal problem）と呼ばれます．一般に「双対問題」と呼ばれるのはこれのことです．ここで，問題$[\mathrm{D}_0]$は見かけ上は制約を含まない最適化問題に見えますが，実際には Lagrange 関数の定義より，$\lambda < 0$のときに$\omega_0(\lambda) = -\infty$となるので，実質的に$\lambda \geqq 0 $を制約に含んでいることに注意されたいです．

さて，以上を踏まえて，線型計画問題に対する Lagrange 双対問題を導出しましょう．線型計画問題は様々な標準形式がありますが，本記事では次式で定義される問題を考えましょう：

\begin{align} \begin{split} \min_{x\in\mathbb{R}^n} &\quad c^\top x \\ \mathrm{s.t.} &\quad Ax \geqq b \end{split} \end{align}

先述した定義に従って Lagrange 関数を書き下すと，次式のようになります：

\begin{eqnarray} L_0(x,\lambda) := \left\{ \begin{array}{l} \displaystyle c^\top x + \lambda^\top(b - Ax) &\quad (\lambda \geqq 0) \\ -\infty &\quad (\lambda < 0) \end{array}. \right. \end{eqnarray}

したがって，双対問題の目的関数は$\lambda \geqq 0$のときに，

\begin{align} \omega_0(\lambda) &= \inf \{ c^\top x + \lambda^\top(b - Ax) \mid x \in \mathbb{R}^n \} \\ &= \lambda^\top b + \inf \{ (c-A^\top\lambda)^\top x \mid x \in \mathbb{R}^n \} \\ &= \left\{ \begin{array}{l} \lambda^\top b &\quad (c - A^\top \lambda = 0) \\ -\infty &\quad (c - A^\top \lambda \neq 0) \end{array} \right. \end{align}
となります．ただし，$\lambda \ngeqq 0$のときは$\omega_0(\lambda)=-\infty$なので，導出すべき双対問題は次のように表すことができます：

\begin{align} \max_{\lambda\in\mathbb{R}^m} \quad &b^\top \lambda \\ \mathrm{s.t.} \quad &A^\top \lambda = c ,\\ & \lambda \geqq 0. \end{align}

結論

線型計画問題：
\begin{align}[\mathrm{LP}]\quad \begin{split} \min_{x\in\mathbb{R}^n} &\quad c^\top x \\ \mathrm{s.t.} &\quad Ax \geqq b \end{split} \end{align}

に対する（Lagrange）双対問題は，
\begin{align}[\mathrm{DLP}]\quad \max_{\lambda\in\mathbb{R}^m} \quad &b^\top \lambda \\ \mathrm{s.t.} \quad &A^\top \lambda = c ,\\ & \lambda \geqq 0. \end{align}
となります．

練習問題

以下の線型計画問題に対する Lagrange 双対問題を導出しましょう．
\begin{align}[\mathrm{LP}]\quad \begin{split} \min_{x\in\mathbb{R}^n} &\quad c^\top x \\ \mathrm{s.t.} &\quad Ax = b,\, x\geqq 0. \end{split} \end{align}