线性问题和简单形法

啥是线性优化问题

pending

优化问题的标准表示形式

pending

基本（可行）解

对于$x \in \mathbb{R}^n$，如果不存在$y \in \mathbb{R}^n$,在点$x$的每一个紧约束，同时紧约束$y$，则$x$是一个基本解。若$x$在可行域$P$内，则$x$为基本可行解。

对于约束$Ax = b, A \in \mathbb{R}^{m \times n}$，可以看作以下形式：

$$b = x_1A_1 + x_2A_2 + \cdots + x_nA_n$$

其中$A_i$表示矩阵$A$的第$i$列，也就是说，$A$的每一列$A_j \in \mathbb{R}^m$是一个"方向向量",$x_j$是它的系数。

由于$n > m$，用$n$个向量去凑$m$维的$b$，有无穷多解。我们可以从$A$中选取$m$个线性无关的列，构成一个基（basis）$A_B$。其对应一个基本解$x_B$，使得$A_Bx_B = b$。用数学语言描述如下：

$$\textbf{Def.}: \text{A basis } B \subseteq \{1,\cdots,n\}, \text{basis means: }rank(A_B) = |B| = m.$$

$\textbf{Obs.}: \exist$ $x_B = A_B^{-1}b$ and $x_j = 0$ for $j \notin B$

需要注意，$A_B$的每一列要求线性无关，这意味这不是任意选取$m$列向量，都对应一个基本解。且当$x_B > 0$，基本解$x_B$才可行。这也是$\text{simplex}$算法的要求之一。

那矩阵$A$是否保证一定有至少一个基本解呢？答案是肯定的。对于优化问题的标准型表示来说，$A$确保行线性无关，即$rank(A) = m$，行秩等于列秩。所以$A$的$n$列中必定能找出$m$列线性无关 —— 至少一个基是保证存在的。

Simplex(简单形法)

$\text{Simplex}$算法简单描述就是，对于优化目标$\min c \cdot x$，计算每一个基本可行解的目标值。遍历出最小值为止。

//算法take one伪代码

算法通过列替换的方式，寻找下一个basis。新的基本解$y$可视为$y = x + \theta d$。$d$为从$x$到$y$的方向向量，维度为$n$。根据所对应矩阵$A$的列向量的划分，$d$包括：

$$d = \big(\underbrace{d_B}_{m\text{维，基变量}},\ \underbrace{d_j}_{=1,\text{进基变量}},\ \underbrace{0,\dots,0}_{\text{其余非基变量}}\big)$$

几何上可解释为，往组合里新增一单位（$d_j$）列向量$A_j$，同时为了保持$Ay = b$对原$A_B$的代偿（$d_B$）。由于最终与$x$相加的结果受$\theta$控制，我们不妨设置$d_j = 1$，则有：

$$y_i = x + \theta = \theta$$ $$y_{b_i} = x_{b_i} + \theta d_{b_i}$$ $$d_B = -A_B^{-1}A_j$$

几何上，$d_B$ 就是沿这条棱走时各个基变量的变化率（斜率），而它的符号决定了后面所有的事：

$d_{b_i}$ 的符号	含义	后果
$d_{b_i} < 0$	$x_{b_i}$ 在递减	迟早触到 0，是离基候选，限制 $\theta$ 的上界
$d_{b_i} \geqslant 0$	$x_{b_i}$ 不减	永远不会触零，对 $\theta$ 没有约束
全部 $d_{b_i} \geqslant 0$	没人拦得住	$\theta$ 可以取到 $\infty \rightarrow$ 线性规划无界

我们需要保证$x_{b_i} + \theta d_{b_i} > 0$，且我们希望引入$d$的结果是原$A_B$的某一列被抵消为0。因此$d_{b_i} < 0$的部分是我们求解$\theta$的重要参考，则有：

$$\forall d_{b_i} < 0 : \theta \le -\frac{x_{b_i}}{d_{b_i}}$$ $$\theta^* = \min_{b_i \in B : d_{b_i} < 0} -\frac{x_{b_i}}{d_{b_i}}$$ $$\theta = \theta^*$$

因此，对于计算$c \cdot y - c \cdot x$有：

$$\begin{aligned} c \cdot y - c \cdot x &= c_j y_j + c_B \cdot y_B - c_B \cdot x_B \\ &= c_j y_j + c_B \cdot (y_B - x_B) \\ &= c_j y_j + c_B \cdot \theta d_B \\ &= c_j \theta - c_B \cdot \theta A_B^{-1} A_j \\ &= \theta (c_j - c_B \cdot A_B^{-1} A_j) = \theta \bar{c}_j \end{aligned}$$

$\bar{c}_j = (c_j - c_B \cdot A_B^{-1} A_j)$被称为列替换$j$的reduced cost，只有当$\bar{c}_j < 0$时，基本解$y$才是更优的。

$$\begin{aligned} \text{引理 }\textbf{Lem.: } &\text{Let B a basis such that} \\ &1. x_B = A_B^{-1}b > 0 \\ &2. \bar{c}^T = c^T - c_B^T A_B^{-1} A \ge 0. \\ &\text{Then the basic feasible solution induced by B is optimal} \end{aligned}$$

补充：初始基本解假设

为什么需要它：$\text{simplex}$是"从一个顶点走到下一个顶点"，所以必须先站在某个顶点上。可对一般的$Ax = b, x ≥ 0$，随便挑一个基$B$算出的$A_B^{-1}b$很可能有负分量，甚至整个可行域可能是空的。"找到第一个基本可行解"本身就是个难题，跟"找最优解"难度相当。

$\text{auxiliary linear program}$的思路是：既然找不到入口，那就先造一个入口。

造法：添加人工变量

$$\min \sum_{j=1}^{m} y_j \quad \text{s.t.} \quad Ax + y = b, \, x \ge 0, \, y \ge 0$$

这里的 $y \in \mathbb{R}^m$ 叫人工变量（artificial variables）。关键设计有两点：

1. 初始基白送。约束矩阵是 $[A \mid I]$，$y$ 对应的加 $m$ 列构成单位阵，天然线性无关。取 $B = y$ 的下标集，则 $A_B = I$, $x = 0, y = b$。这就是一个现成的基本可行解——而且不用算。（前提是 $b \ge 0$，若某行 $b_i < 0$，把该行整行乘 $-1$ 即可，等式两边同乘不改变约束。）

2. 它永远有解。辅助问题一定可行（上面那个点），且目标 $\sum y_j \ge 0$ 有下界，所以永不无界——单纯形法跑它必然正常终止。

几何上可以这样想：我们把问题抬升到了 $\mathbb{R}^{n+m}$ 中。原来的可行域 $\{x : Ax = b, x \ge 0\}$ 就是新可行域与超平面 $y = 0$ 的交集。加人工变量相当于给了一个 "悬在半空中" 的容易找到的起点，然后用目标函数 $\sum y$ 把它往下压：

• 最优值 $= 0$：说明能降到底，$y = 0$，此时 $Ax = b$ 且 $x \ge 0$——落点正是原问题的一个基本可行解。它对应的基（去掉退化残留的 $y$ 下标、按 $\text{rank}(A) = m$ 补齐后）就是 Phase 2 要的初始基。
• 最优值 $> 0$：说明无论怎么调 $x$ 都至少要作弊那么多，即 $\{x : Ax = b, x \ge 0\} = \varnothing$——原问题不可行，直接报告，无需进入 Phase 2。

(关于$\text{simplex}$的另外两个假设，无界假设不满足直接终止算法，非退化基假设需引入额外规则，有兴趣我再补充)