---
lang: ja
tags: OptMech-2021, lecture
---

# 2021年度 知的システム<br>第4回：線形計画問題(3) 双対定理
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：
<code style="font-size:20pt">https://hackmd.io/@nagae/OptMech_2021-Ch03</code>

</div>

# 用語の整理
**主問題(primal)**
$$
\text{(P)} \max_{\mathbf{x}} \left\{\left.
\mathbf{c}^{\top} \mathbf{x}
\right| \mathbf{A} \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}
\right\}
$$

**双対問題(dual)**
$$
\text{(D)} \min_{\mathbf{y}} \left\{\left.
\mathbf{y}^{\top} \mathbf{b}
\right| \mathbf{y}^{\top} \mathbf{A} \geq \mathbf{c}^{\top}, \mathbf{y} \geq \mathbf{0} \right\}
$$

- **標準最大化問題** の未知変数$\mathbf{x}$ が制約条件 $\mathbf{A} \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}$ を満たしている時や，**標準最小化問題** の未知変数$\mathbf{y}$ が制約条件 $\mathbf{y}^{\top}\mathbf{A} \leq \mathbf{c}^{\top}, \mathbf{y} \geq \mathbf{0}$ を満たしている時，これらを ==**許容/実行可能**== (feasible) であるという．**許容** な未知変数を ==**許容解/実行可能解**== (feasible solution)という．
- **許容解** の集合を ==**許容領域/実行可能集合**== (feasible set) という．
- 線形計画問題の **許容領域** が空でないなら,この問題は ==**許容/ 実行可能**== (feasible) であるといい, そうでなければ ==**不能/実行不可能**== (infeasible) であるという.
- **許容** な **標準最大化問題**(もしくは**標準最小化問題**)の目的関数をどこまでも大きく (あるい小さく) できる時, その問題は ==**無界/非有界**== (unbounded) であるといい, そうでなければ ==**有界**== (bounded) であるという.
- **許容** かつ **有界** な **標準最大化問題** の **許容解** $\mathbf{x}$ の中で目的関数 が最も大きいものをこの問題の ==**最適解**== (optimal solution) と 呼び, $\mathbf{x}^{\ast}$ で表す. 同様に，**標準最小化問題**の **許容解** $\mathbf{y}$ の中で 目的関数が最も小さいものを, この問題の ==**最適解**== と呼び, $\mathbf{y}^{\ast}$ で表す. これらの**最適解**における目的関数の値 $\mathbf{c}^{\top} \mathbf{x}^{\ast}$, ${\mathbf{y}^{\ast}}^{\top} \mathbf{b}$ を, ==**最適値**== (value) と呼ぶ.
- **未知変数**,**実行可能性**,**許容領域**,**最適解**などを**主問題**もしくは**双対問題**について区別するとき, 主問題に関する諸概念は, ==**主変数**== (primal variables), ==**主実行可能**== (primal feasible), ==**主最適解**== (primal optimal solution) のように ==**主—**== (primal —) といい, 双対問題のこれらは ==**双対変数**== (dual variables), ==**双対実行可能**== (dual feasible) や ==**双対最適解**== (dual optimal solution) のように ==**双対—**== (dual —) という.

# 双対問題に関する各種定理
## 基本定理
:::success
**実行可能** で **有界** な線形計画問題は **最適解** を持つ.
:::

## 弱双対定理
:::success
$\text{(P)}$および$\text{(D)}$ の任意の **許容解** $\mathbf{x}, \mathbf{y}$ に対して，*$\text{(P)}$の目的関数値は $\mathbf{(D)}$ の目的関数値を超えない*：
$$
\mathbf{A} \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0} \text{ and }
\mathbf{y}^{\top} \mathbf{A} \geq \mathbf{c}^{\top}, \mathbf{y} \geq \mathbf{0}
\rightarrow
\mathbf{c}^{\top} \mathbf{x} \leq \mathbf{y}^{\top} \mathbf{b}
$$
:::

## 双対定理
:::success
$\text{(P)}$または$\text{(D)}$が **最適解** を持つならば，他方も最適解を持ち，その **最適値** は等しい:
$$
\mathbf{c}^{\top} \mathbf{x}^{\ast} =
{\mathbf{y}^{\ast}}^{\top} \mathbf{b}
$$
:::

## 相補性定理
:::success
$\text{(P)}$および$\text{(D)}$のそれぞれの **許容解** $\mathbf{x}$ および$\mathbf{y}$ がともに **最適解** であるための ==**必要十分条件**== は，以下の2つの条件がともに成立することである：
$$
\mathbf{x}^{\top} \left(
\mathbf{c} - \mathbf{A}^{\top} \mathbf{y}
\right) = 0
\qquad
\left(\mathbf{A} \mathbf{x} - \mathbf{b}\right)^{\top} \mathbf{y} = 0
$$
:::
上記2つの条件を合わせて ==**相補性条件**== (complementarity condition)と呼ぶ． なお， ==**相補性条件**== は以下のように展開表示できる：
\begin{align*}
\mathbf{x}^{\top}\left(\mathbf{c} - \mathbf{A}^{\top} \mathbf{y}\right) = 0
&\Leftrightarrow
\sum_{i=1}^{N} x_{i} \left(c_{i} - \sum_{j=1}^{M} a_{ij} y_{j}\right) = 0\\
&\Leftrightarrow
x_{i} \left(c_{i} - \sum_{j=1}^{M} a_{ij} y_{j}\right) = 0, \quad \forall i = 1, \cdots, N\\
&\Leftrightarrow
\begin{cases}
x_{i} > 0 &\rightarrow
\sum_{j=1}^{M} a_{ij} y_{j} = c_{i} \\
x_{i} = 0 &\leftarrow
\sum_{j=1}^{M} a_{ij} y_{j} > c_{i}
\end{cases}
\quad & i = 1, \cdots, N\\
\end{align*}
$$
\begin{align*}
\begin{cases}
y_{j} > 0 &\rightarrow
\sum_{i=1}^{N} a_{ij} x_{i} = b_{j} \\
y_{j} = 0 &\leftarrow
\sum_{i=1}^{N} a_{ij} x_{i} < b_{j}
\end{cases}
\quad & j = 1, \cdots, M\\
\end{align*}
$$

# 弱双対定理の証明
$\mathbf{x}, \mathbf{y}$ を主許容解および双対許容解とすれば，
$$
\begin{align*}
\mathbf{c}^{\top} \mathbf{x} &\leq
\left(\mathbf{y}^{\top} \mathbf{A}\right) \mathbf{x}
&& \text{[} \mathbf{y}^{\top} \mathbf{A} \geq \mathbf{c}^{\top}, \mathbf{x} \geq \mathbf{0} \text{より]} \\
&= \mathbf{y}^{\top} \mathbf{A} \mathbf{x} \\
& \leq \mathbf{y}^{\top} \mathbf{b} &&\text{[} \mathbf{A}\mathbf{x} \leq \mathbf{b}, \mathbf{y} \geq \mathbf{0}\text{より]}
\end{align*}
$$
(証明終わり)．

## 弱双対定理の系
**弱双対定理**より，以下の系が直ちに導かれる．

### 系(1)
$\text{(P)}$ または $\text{(D)}$ が **無界** ならば，他方は **不能** である．

### 系(2)(目的関数が一致する→最適解)
**主許容解**$\mathbf{x}$ および**双対許容解**$\mathbf{y}$ の*目的関数値が一致する*：
$$
\mathbf{c}^{\top} \mathbf{x} = \mathbf{b}^{\top} \mathbf{y}
$$

ならば，これらは，それぞれ，主問題および双対問題の **最適解** である．

# Farkas の補題
**双対定理**の証明に入る前に, ==**Farkas の補題**== を紹介しておこう．

## Farkasの補題(Farkas' lemma)
$M$ 本の$N$次元ベクトル$\mathbf{a}_{1}, \cdots, \mathbf{a}_{M}$と$N$次元列ベクトル$\mathbf{c}$に対して，以下の ==**いずれか一方のみ**== が常に成り立つ：
1. $\sum_{j=1}^{M} \mathbf{a}_{j} y_{j} = \mathbf{c}$ なる$M$個の **非負の実数** $y_{1}, \cdots, y_{M}$ が存在する;
2. 任意の$j=1, \cdots, M$に対して $\mathbf{a}_{j}^{\top} \mathbf{x} \geq 0$ かつ $\mathbf{c}^{\top}\mathbf{x} < 0$なる$N$次元列ベクトル$\mathbf{x}$が存在する．

これらは$M\times{}N$行列$\mathbf{A} = \begin{bmatrix}\mathbf{a}_{1}^{\top} \\ \vdots \\ \mathbf{a}_{M}^{\top}\end{bmatrix}$を用いて以下のようにも表現できる：
1. $\mathbf{A}^{\top} \mathbf{y} = \mathbf{c}, \mathbf{y} \geq \mathbf{0}$なるベクトル$\mathbf{y} \in \mathcal{R}^{M}$が存在する;
2. $\mathbf{A}\mathbf{x} \geq \mathbf{0}$かつ$\mathbf{c}^{\top} \mathbf{x} < 0$ なるベクトル$\mathbf{x} \in \mathcal{R}^{N}$が存在する.

## Farkasの補題の幾何学的イメージ
$N=2$, $M=3$の場合を考え， 3つのベクトル$\mathbf{a}_{1}, \mathbf{a}_{2}, \mathbf{a}_{3}$から生成される凸錐(cone)を $\mathcal{C}$ とする．

■ $\mathbf{c}\in\mathcal{C}$ の場合 (たとえば$\mathbf{c}=\mathbf{c}_{1}$)
このとき，$\mathbf{c}$は$\mathbf{a}_{1}, \mathbf{a}_{2}, \mathbf{a}_{3}$の**線形結合**で表される:
$$
\mathbf{c} = \mathbf{a}_{1} y_{1} + \mathbf{a}_{2} y_{2} + \mathbf{a}_{3} y_{3}, \quad
y_{1}, y_{2}, y_{3} \geq 0
$$
このことは，上述の1が成立することを意味する:
$$\exists \mathbf{y} \in \mathcal{R}^{M}: \mathbf{A}^{\top}\mathbf{y} = \mathbf{c}, \mathbf{y} \geq \mathbf{0}.$$

■ $\mathbf{c}\not\in\mathcal{C}$ の場合(たとえば$\mathbf{c}=\mathbf{c}_{2}$)
このとき，凸錐 $\mathcal{C}$ とベクトル $\mathbf{c}$ を**分離する超平面**(図の破線)が(無数に)存在し， そうした分離超平面の中で，法線ベクトル$\mathbf{x}$ が $\mathbf{x}^{\top} \mathbf{c}<0$ なるものを選べば，$\mathbf{a}_{1}^{\top}\mathbf{x} \geq 0, \mathbf{a}_{2}^{\top}\mathbf{x} \geq 0,\mathbf{a}_{3}^{\top}\mathbf{x} \geq 0$が成り立つ． このことは，上述の2が成立することを意味する:
$$\exists \mathbf{x} \in \mathcal{R}^{N}:
\mathbf{A}\mathbf{x} \geq \mathbf{0} \text{ and } \mathbf{c}^{\top} \mathbf{x} < 0
$$

# 双対定理の証明
背理法を用いて証明する．$\text{(P)}$が最適解$\mathbf{x}^{\ast}$をもつとしよう．このとき，$\text{(D)}$が${\mathbf{y}^{\ast}}^{\top} \mathbf{b} \leq \mathbf{c}^{\top} \mathbf{x}^{\ast}$ となる許容解を持てば，**弱双対定理**とその **[系(2)](https://hackmd.io/QgXgc9XqRNmAiGB-D1QDzQ?both#%E7%B3%BB2%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%E3%81%8C%E4%B8%80%E8%87%B4%E3%81%99%E3%82%8B%E2%86%92%E6%9C%80%E9%81%A9%E8%A7%A3)** より$\mathbf{y}^{\ast}$は**双対最適解**となる． ここでは，*そのような$\mathbf{y}^{\ast}$が存在しないとして，矛盾を導く*．

まず，${\mathbf{y}^{\ast}}^{\top} \mathbf{b} \leq \mathbf{c}^{\top} \mathbf{x}^{\ast}$ なる$\text{(D)}$ の**許容解**，すなわち
$$
\mathbf{y}^{\top} \mathbf{b} \leq \mathbf{c}^{\top} \mathbf{x}^{\ast}, \quad
\mathbf{A}^{\top} \mathbf{y} \geq \mathbf{c}, \quad \mathbf{y} \geq \mathbf{0}
$$
を満足する ***$\mathbf{y}$が存在しない**と仮定する*．これは，
$$
\begin{bmatrix}
\mathbf{b}^{\top} &\mathbf{0}^{\top} &1 \\
-\mathbf{A}^{\top} & \mathbf{I} & \mathbf{0}
\end{bmatrix}\begin{bmatrix}
\mathbf{y} \\ \mathbf{u} \\ v
\end{bmatrix}
=\begin{bmatrix}
\mathbf{c}^{\top} \mathbf{x}^{\ast} \\
-\mathbf{c}
\end{bmatrix}, \quad \begin{bmatrix}
\mathbf{y} \\ \mathbf{u} \\ v
\end{bmatrix} \geq \mathbf{0}
$$
を満たす ***$(\mathbf{y}, \mathbf{u}, v) \in \mathcal{R}^{M+N+1}$が存在しない*** ことと等価である．
なお，上の2つの式が等価であることは， 上式を
$$
\begin{cases}
\mathbf{b}^{\top} \mathbf{y} + v = \mathbf{c}^{\top} \mathbf{x}^{\ast} \\
-\mathbf{A}^{\top} \mathbf{y} + \mathbf{u} = - \mathbf{c} \\
\mathbf{y}, \mathbf{u}, v \geq \mathbf{0}
\end{cases}
$$
と展開すれば明らか．

このとき，**Farkasの補題**より，以下を満足する$(w, \mathbf{z}) \in \mathcal{R}^{1+N}$が存在する:
$$
\begin{bmatrix}
\mathbf{b} & -\mathbf{A} \\
\mathbf{0} & \mathbf{I} \\
1 & \mathbf{0}^{\top}
\end{bmatrix}\begin{bmatrix}
w \\ \mathbf{z}
\end{bmatrix} \geq \mathbf{0} \text{ and }
\left(\mathbf{c}^{\top} \mathbf{x}^{\ast} \right) w - \mathbf{c}^{\top}\mathbf{z} < 0.
$$
すなわち，
$$
\mathbf{A}\mathbf{z} \leq \mathbf{b}w, \qquad
\left(\mathbf{c}^{\top} \mathbf{x}^{\ast} \right) w < \mathbf{c}^{\top}\mathbf{z}
$$
を満たす非負の変数$w, \mathbf{z}$ が存在する．以降，$w=0$の場合と$w>0$の場合のそれぞれで矛盾を導く．

■ $w=0$ の場合
$\mathbf{z}$は$\mathbf{A}\mathbf{z} \leq \mathbf{0}, \mathbf{z}\geq \mathbf{0}$かつ$\mathbf{c}^{\top} \mathbf{z} > 0$を満たすため，任意の正の数$\lambda$に対して， $\mathbf{x}^{\ast} + \lambda \mathbf{z}$ は
$$
\mathbf{A}\left(\mathbf{x}^{\ast} + \lambda \mathbf{z} \right) \leq \mathbf{b}, \qquad \mathbf{x}^{\ast} + \lambda \mathbf{z} \geq \mathbf{0}, \qquad \mathbf{c}^{\top} \left(\mathbf{x}^{\ast} + \lambda \mathbf{z}\right) > \mathbf{c}^{\top} \mathbf{x}^{\ast}
$$
を満たす(i.e. $\mathbf{x}^{\ast}+\lambda \mathbf{z}$は主実行可能かつ$\mathbf{x}^{\ast}$よりも高い目的関数を実現する)． これは$\mathbf{x}^{\ast}$が$\text{(P)}$の最適解であるという仮定に ==**矛盾する**==.

■ $w>0$の場合
$\mathbf{z}/w$は$\text{(P)}$の許容解であり，かつ$\mathbf{c}^{\top} (\mathbf{z}/w) > \mathbf{c}^{\top} \mathbf{x}^{\ast}$ となるため，やはり$\mathbf{x}^{\ast}$ が最適解であるという仮定に ==**矛盾する**==．

以上のことから，$\text{(P)}$が最適解$\mathbf{x}^{\ast}$を持つとき， $\text{(D)}$は
$${\mathbf{y}^{\ast}}^{\top} \mathbf{b} \leq \mathbf{c}^{\top} \mathbf{x}^{\ast}$$
満たす許容解$\mathbf{y}^{\ast}$を持つ． **[弱双対定理](https://hackmd.io/@nagae/MTNS_2020-Ch03#%E5%BC%B1%E5%8F%8C%E5%AF%BE%E5%AE%9A%E7%90%86)** ($\mathbf{c}^{\top}\mathbf{x} \leq \mathbf{y}^{\top} \mathbf{b}$)より，このとき
$$
{\mathbf{y}^{\ast}}^{\top} \mathbf{b} = \mathbf{c}^{\top} \mathbf{x}^{\ast}
$$
が成り立つから， $\mathbf{y}^{\ast}$ は$\text{(D)}$ の最適解に他ならない． (証明終わり)

# 相補性定理の証明
[弱双対定理](https://hackmd.io/@nagae/MTNS_2020-Ch03#%E5%BC%B1%E5%8F%8C%E5%AF%BE%E5%AE%9A%E7%90%86)と[双対定理](https://hackmd.io/@nagae/MTNS_2020-Ch03#%E5%8F%8C%E5%AF%BE%E5%AE%9A%E7%90%86)より，$\text{(P)}$および$\text{(D)}$の許容解$\mathbf{x}$および$\mathbf{y}$が最適解であるための ==**必要十分条件**== は，
$$
\mathbf{c}^{\top} \mathbf{x} = \mathbf{y}^{\top} \mathbf{b}
$$
なので，これを示す．$\mathbf{x}$と$\mathbf{y}$は許容であるから，
$$
\mathbf{y}^{\top} \mathbf{b} \geq \mathbf{y}^{\top} \left(\mathbf{A}\mathbf{x}\right)
= \left(\mathbf{y}^{\top} \mathbf{A} \right) \mathbf{x} \geq \mathbf{c}^{\top} \mathbf{x}
$$
が成り立つ．

$\mathbf{c}^{\top} \mathbf{x} = \mathbf{y}^{\top} \mathbf{b}$ となるための必要十分条件は，上式の2つの不等式で等号が成り立つ，すなわち，
$$
\begin{cases}
\mathbf{y}^{\top} \mathbf{b} = \mathbf{y}^{\top}\left(\mathbf{A}\mathbf{x}\right) \\
\left(\mathbf{y}^{\top}\mathbf{A}\right)\mathbf{x} = \mathbf{c}^{\top} \mathbf{x}
\end{cases}
\Leftrightarrow
\begin{cases}
\mathbf{y}^{\top} \left(
\mathbf{b} - \mathbf{A}\mathbf{x}\right) =0\\
\left(\mathbf{y}^{\top}\mathbf{A}-\mathbf{c}^{\top}\right)\mathbf{x} = 0
\end{cases}
$$
が満たされることである．これは相補性条件に他ならない．
(証明終わり)