Motzkin’s Theorem of the Alternative

Alternative Theorem
定理

$A \neq 0$とすると、以下の線形不等式系のいずれか一方のみが解を持つ。
1. $A x > \boldsymbol{0}, \ B x \geq \boldsymbol{0}, \ C x = \boldsymbol{0}, \ x \in \mathbb{R}^{n}$
2. $A^{T} y_1 + B^{T} y_2 + C^{T} y_3 = \boldsymbol{0}, \ y_1 \gneq \boldsymbol{0}, \ y_2 \geq \boldsymbol{0}$

証明

（1.が成立するなら、2.が成立しない。）

\begin{aligned} 0 & = (Ax)^{T} y_1 + (Bx)^{T} y_2 + (Cx)^{T} y_3 \\ & \ge (Ax)^{T} y_1 \\ & > 0 \end{aligned}

より示される。

（1.が成立しないなら、2.が成立する。）
1.と同値な線形不等式系1'.： $A x \ge \eta \boldsymbol{1}, \ B x \geq \boldsymbol{0}, \ C x = \boldsymbol{0}, \ \eta > 0$を考える。
$A x \ge \eta \boldsymbol{1} > \boldsymbol{0}$であるため、1.を満たす$x$が存在することと、1.'を満たす$x, \eta$は存在することは同値である。逆に、1.を満たさないことと、1.を満たさないこととは同様に同値である。

ここで1'.の不等式系を次のように表現する。

\begin{aligned} \begin{bmatrix} A & -\boldsymbol{1} \\ B & \boldsymbol{0} \\ C & \boldsymbol{0} \\ -C & \boldsymbol{0} \end{bmatrix} \begin{bmatrix} x \\ \eta \end{bmatrix} \ge \begin{bmatrix} \boldsymbol{0} \\ \boldsymbol{0} \\ \boldsymbol{0} \\ \boldsymbol{0} \end{bmatrix} , \quad \langle (\boldsymbol{0}, -1), (x, \eta) \rangle < 0 \end{aligned}

Farkas' Lemmaより、1'.が解を持たないならば、次の線形不等式系が解を持つ。

\begin{aligned} \begin{bmatrix} A^{T} & B^{T} & C^{T} & -C^{T} \\ -\boldsymbol{1} & \boldsymbol{0} & \boldsymbol{0} & \boldsymbol{0} \end{bmatrix} \begin{bmatrix} y_1 \\ y_2\\ z_1 \\ z_2 \end{bmatrix} = \begin{bmatrix} \boldsymbol{0} \\ -1 \end{bmatrix} , \quad \begin{bmatrix} y_1 \\ y_2\\ z_1 \\ z_2 \end{bmatrix} \ge 0 \end{aligned}

は解を持つ。この線形不等式系は、

\begin{aligned} A^{T} y_1 + B^{T} y_2 + C^{T} (z_1 - z_2) = \boldsymbol{0}\\ \langle \boldsymbol{1}, y_1 \rangle = 1 \\ y_1 \ge 0, y_2 \ge 0 \end{aligned}

と記述でき、2.を満たす解を持つ。よって示された。

参考文献

Berkovitz, Leonard D. Convexity and optimization in Rn. John Wiley & Sons, 2003.