不求甚解學經濟-一些簡單的綫性規劃

一些簡單的綫性規劃

綫性規劃問題的表述

Standard 綫性規劃問題

給定係數矩陣 $A_{m\times n}$，相應的向量 $b_{m\times 1}$ 和 $c_{n\times 1}$，尋找 $x_{n\times 1}$ 和 $y_{m\times 1}$ 使得

最大化問題	最小化問題
$\max c^{T}x$	$\min b^{T}y$
s.t.$Ax\leq b$	s.t.$y\geq 0_{m\times 1}$
$x\geq 0_{n\times 1}$	$A^{T}y\geq c$

為一組對偶的 Standard 綫性規劃問題。

Canonical 綫性規劃問題

給定係數矩陣 $A_{m\times n}$，相應的向量 $b_{m\times 1}$ 和 $c_{n\times 1}$，尋找 $x_{n\times 1}$ 和 $y_{m\times 1}$ 使得

最大化問題	最小化問題
$\max c^{T}x$	$\min b^{T}y$
s.t.$Ax = b$	s.t.$y\text{free}$
$x\geq 0_{n\times 1}$	$A^{T}y\geq c$

為一組對偶的 Canonical 綫性規劃問題。

General 綫性規劃問題

給定係數矩陣 $A_{11},A_{12},A_{21},A_{22}$，相應的向量 $b_{1},b_{2}$ 和 $c_{1},c_{2}$，尋找 $x_{1},x_{2}$ 和 $y_{1},y_{2}$ 使得

最大化問題	最小化問題
$\max c_{1}^{T}x_{2}+c_{2}^{T}x_{2}$	$\min b_{1}^{T}y_{1}+b_{2}^{T}y_{2}$
s.t.$A_{11}x_{1}+A_{12}x_{2} \leq b_{1}$	s.t.$y_{1}\geq 0$
s.t.$A_{21}x_{1}+A_{22}x_{2} = b_{2}$	s.t.$y_{2}\text{free}$
$x_{1}\geq 0$	$A_{11}^{T}y_{1}+A_{21}^{T}y_{2}\geq c_{1}$
$x_{2}\text{free}$	$A_{12}^{T}y_{1}+A_{22}^{T}y_{2}= c_{2}$

為一組對偶的 Canonical 綫性規劃問題。

Standard 與 Canonical 問題的等價性

(暫時掠過)

綫性等式系統解的存在性

定理1

任意給定 $r$ 個實數 $\alpha_{1},...,\alpha_{r}$ 滿足 $( a_{1},...,\alpha_{r} )_{1\times r} \neq 0_{1\times r}$，給定 $\mathbb{R}^{n}$ 中的一組綫性無關的行向量 $a_{1\times n}(1),...a_{1\times n}(r)$ (這意味 $r\leq n$，因爲 $n$ 維空間中不會有 $m>n$ 個綫性無關的向量族)，總可以找到一個向量 $y_{n\times 1}$，使得 $a^{T}(i)_{n \times 1}y_{1\times n}=\alpha_{i},\forall i=1,..,r$。

證明：將 $r$ 個行向量 $a_{1\times n}(1),...a_{1\times n}(r)$ 堆叠成一個矩陣 $A_{r\times n}$，矩陣的行 rank 與列 rank 相同，由於這 $r$ 個行向量被假設為綫性無關，因此矩陣 A 的行 rank 與列 rank 均爲 $r$，從而可以找到矩陣 $A_{r\times n}$ 的 $r$ 個綫性無關的列向量 $a_{r\times 1}[1],...,a_{r\times 1}[r]$ 構成 $\mathbb{R}^{r}$ 的基。

既然列向量 $a_{r\times 1}[1],...,a_{r\times 1}[r]$ 構成 $\mathbb{R}^{r}$ 的基，那麽任何一個向量 $( a_{1},...,\alpha_{r} )_{1\times r}$ 都可以表示成 $a_{r\times 1}[1],...,a_{r\times 1}[r]$ 的綫性組合，即存在 $\eta_{1},...,\eta_{r}$ 使得

$$( a_{1},...,\alpha_{r} )_{1\times r}=\sum_{j=1}^{r}\eta_{j}\alpha_{r\times 1}[j]$$

則構造向量 $y_{1\times n}=(\eta_{1},...,\eta_{r},0,...,0)$ (共有 $n-r$ 個 0 )，這個向量就滿足

$$a^{T}(i)_{n \times 1}y_{1\times n}=\alpha_{i}+0=\alpha_{i},\forall i=1,..,r$$

定理2. 存在性：齊次綫性系統的解

定理3. 存在性：綫性等式系統的解

如下兩個問題，恰好有一個有解，不會都無解，也不會同時有解：

1. $A_{m\times n}x_{n\times 1}=b_{m\times 1}$

2. $A^{T}_{n\times m}y_{m\times 1}=0_{n\times 1},b^{T}_{1\times m}y_{m\times 1}=\alpha_{1\times 1},\alpha\neq 0_{1\times 1}$

證明：

(1) 假設這兩個問題同時有解，則對於問題 2 的某個解 $y_{m\times 1}$，將其乘在問題 1 上可得

$$y^{T}_{1\times m}A_{m\times n} x_{n\times 1}=y^{T}_{1\times m}b_{m\times 1}$$

根據 $y$ 是問題 2 的解，上式進一步變成

$$y^{T}_{1\times m}A_{m\times n} x_{n\times 1}=y^{T}_{1\times m}b_{m\times 1}=\alpha$$

但由於 $y$ 是問題 2 的解，左側

$$y^{T}_{1\times m}A_{m\times n} x_{n\times 1}=0^{T}_{1\times n}x_{n\times 1}=y^{T}_{1\times m}b_{m\times 1}=\alpha$$

但這就意味著

$$0^{T}_{n\times 1}x_{n\times 1}=0_{1\times 1}=\alpha_{1\times 1}\neq 0_{1\times 1}$$

這就矛盾了。因此，只剩下兩種可能：要麽兩個問題同時無解，要麽恰好有一個有解。

現在假設問題 1 無解。取 $A_{m\times n}$ 的一個基 $a_{1},...,a_{r}$，其中每個 $a_{i}$ 為 $m\times 1$。既然 $Ax=b$ 無解，那就意味著 $b$ 不在基 $a_{1},...,a_{r}$ 所張成的空間裏，即 $a_{1},...,a_{r},b$ 綫性無關。因此，根據定理 1，存在一個向量 $y_{m\times 1}$ 使得

$$\begin{align} a_{i}y=0&,&\forall i=1,...,r\\ b^{T}_{1\times m}y_{m\times 1}=\alpha&,&\text{對於某個}\alpha\neq 0 \end{align}$$

既然 $a_{1},...,a_{r}$ 是 $A$ 的一個基，則 $A$ 的任何一個列向量 $a_{k}$ 都可以表示爲 $a_{1},...,a_{r}$ 的綫性組合，即

$$\begin{align} a_{k}=&\sum_{i=1}^{r}\lambda_{i,k}a_{i},\forall k=1,...,n\\ y^{T}_{1\times m}a_{k}=&\sum_{i=1}^{r}\lambda_{i,k}(y^{T}_{1\times m}a_{i})=0_{1\times 1} \end{align}$$

因此 $y^{T}_{1\times m}A_{m\times n}=0_{1\times n}$ 以及 $b^{T}_{1\times m}y_{m\times 1}=\alpha$

但這就意味著問題 2 是有解的。這就説明這兩個命題不可能同時不成立。

綫性不等式系統解的存在性

Tucker’s Lemma

給定矩陣 $A_{m\times n}$，對偶系統

系統 I	系統 II
$A^{T}_{n\times m}y_{m\times 1}\geq 0_{n\times 1}$	$A_{m\times n}x_{n\times 1}=0_{m\times 1}$
-	$x_{n\times 1}\geq 0_{n\times 1}$

分別存在解 $y_{m\times 1}$ 和 $x_{n\times 1}$ 使得

$$a_{1\times m}^{T}y_{m\times 1}+x_{1}>0$$

其中 $a_{1\times m}^{\prime}$ 為矩陣 $A$ 的第一行的 transpose，$x_{1}$ 為解 $x$ 的第一個分量。

Farkas’ Lemma - version 1

給定矩陣 $A_{m\times n}$，給定向量 $b_{m\times 1}$；對於系統 $A^{T}_{n\times m}y_{m\times 1}\geq 0_{n\times 1}$，如果它的每個解 $y_{m\times 1}$ 都滿足 $b^{T}_{1\times m}y_{m\times 1}\geq 0$。那麽存在解 $x^{\star}$ 使得 $Ax^{\star}=b$ 和 $x^{\star}\geq 0$ 同時成立。

Farkas’ Lemma - version 2

給定矩陣 $A_{m\times n}$，給定向量 $b_{m\times 1}$，如下兩個命題恰好只有一個成立，不會都不成立，也不會都成立

系統 I	系統 II
$Ax=b$ 有非負解 $x\geq 0$	$y^{T}A\geq 0$ 且 $y^{T}b<0$ 有解 $y$ 可正可負

Farkas’ Lemma - version 3

$Ax=b$ 有非負解 $x\geq 0$ 當且僅當 $y^{T}A\geq 0$ 且 $y^{T}b\geq 0$ 有解 $y$ 可正可負。

推論 1

如果 $y^{T}b\geq 0$ 對於每個滿足 $y^{T}A\geq 0$ 的非負解 $y\geq 0$ 都成立，那麽存在非負向量 $x\geq 0$ 使得 $Ax\geq b$。

推論 2

定理 4：Tucker 第一存在定理

定理 5：Tucker 第二存在定理

推論 3

定理 6

定理 7

定理 8

定理 9

綫性規劃

綫性規劃解的性質

退化解

超平面

綫性不等式的幾何性質

凸性

分離超平面