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

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

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

注意

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

本論

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

$$\begin{array}{r}[\mathrm{P}]\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{min}& f(x)\\ \mathrm{s}.\mathrm{t}.& g_i(x)\leqq 0(i=1,2,\dots ,m)\end{array}\end{array}$$

ここで，$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{array}{r}{L}_0(x,\lambda ):=\{\begin{array}{ll}{\displaystyle f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)}& (\lambda \geqq 0)\\ -\mathrm{\infty }& (\lambda <0)\end{array}.\end{array}$$
ここで，$\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_m)\in {\mathbb{R}}^m$は Lagrange 乗数と呼ばれるベクトルです．
上記で定義した関数$L_0$を用いて，関数$\theta :{\mathbb{R}}^n\to (-\mathrm{\infty },\mathrm{\infty }]$および${\omega }_0:{\mathbb{R}}^m\to [-\mathrm{\infty },\mathrm{\infty })$をそれぞれ次のように定義します：

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

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

$$\begin{array}{r}\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{min}& c^{\mathrm{\top }}x\\ \mathrm{s}.\mathrm{t}.& Ax\geqq b\end{array}\end{array}$$

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

$$\begin{array}{r}{L}_0(x,\lambda ):=\{\begin{array}{ll}{\displaystyle c^{\mathrm{\top }}x+{\lambda }^{\mathrm{\top }}(b-Ax)}& (\lambda \geqq 0)\\ -\mathrm{\infty }& (\lambda <0)\end{array}.\end{array}$$

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

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

$$\begin{array}{rl}\underset{\lambda \in {\mathbb{R}}^m}{max}& b^{\mathrm{\top }}\lambda \\ \mathrm{s}.\mathrm{t}.& A^{\mathrm{\top }}\lambda =c,\\ & \lambda \geqq 0.\end{array}$$

結論

線型計画問題：
$$\begin{array}{r}[\mathrm{LP}]\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{min}& c^{\mathrm{\top }}x\\ \mathrm{s}.\mathrm{t}.& Ax\geqq b\end{array}\end{array}$$

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

練習問題

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