9
大学数学基礎解説
文献あり

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

1176
0
$$$$

はじめまして,みるか( @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}

参考文献

[1]
非線形最適化の基礎, 福島雅夫
投稿日:20201113

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

みるか
みるか
17
4792

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中