线性规划

Linear Programming 的一般形式

我们通常使用矩阵形式进行表示：

\begin{array}{rlllll} \min & f(\bold{x})=\bold{c}^T\bold{x} \\ \text{s.t.} & \bold{Ax=b} \\ & \bold{x}\ge 0\\ \text{where} & \bold{x}=\begin{bmatrix} x_1\\x_2\\\vdots\\x_n \end{bmatrix}, & \bold{b}=\begin{bmatrix} b_1\\b_2\\\vdots\\ b_m \end{bmatrix}\ge 0, & \bold{c}=\begin{bmatrix} c_1\\c_2\\\vdots\\c_n \end{bmatrix}\\ \text{and} & \bold{A}=\begin{bmatrix} a_{1,1} & a_{1,2} & \dots & a_{1,n}\\ a_{2,1} & a_{2,2} & \dots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n} \end{bmatrix} \end{array}

如果存在不等式约束，那么我们可以通过加减 slack variable 的方式将不等式变成等式（然后将 slack variable 加入 design variable 中）.
若变量存在上下界，如 $x_i\ge l, x_i\le r$ ，则可令 $x_i'=x_i-l$ 或者 $x_i''=r-x_i$ .
若 $x_i$ 无界，则可令 $x_i=x_a-x_b,\quad\text{s.t. }\quad x_a\ge 0, x_b\ge 0$ .

Convexity 凸性

Function $f(x)$ is convex iff

f\bigg( (1-\rho)\bold{x}^{(1)} + \rho \bold{x}^{(2)} \bigg)\le (1-\rho) f(\bold{x}^{(1)}) + \rho f(\bold{x}^{(2)})

我们也可以通过检查 $f$ 的 Hessian 检查 $f$ 是否 convex. 如果 Hessian of $f$ 是 positive-semidefinite 或者 positive-definite，则 $f$ 为 convex.

所有线性规划都是 Convex 的

如果函数 $g(\bold{x})$ is convex, 那么由 $g(\bold{x})\le c$ 可以定义出 convex region (其中 $c$ 是任意常数).
而显然，多个 convex region 的交集也是 convex 的.
由多条 linear equality/inequality 框住的区域也是 convex 的.
由于 LP 里，约束和优化目标都是 linear 的，所以所有 LP 都是 Convex Programming Problem.
而对于 CP 来说，K-K-T 条件就是充分必要条件，因而我们不需要再验证 second order sufficient conditions.

Geometry of LP Problems

我去，这不就是半平面交吗（

多个半平面在平面上交出来的区域称为 Polyhedral Set 或者 Polyhedron (二维平面情况下，也可以称为 Polygon). 如果这个 Polyhedron 是有界的，则称为 Polytope.

所有满足一个线性方程的 $n$ 维空间中的点的集合，称为超平面。所以从这个角度看，超平面是一个 $n-1$ 维的实体，将一个 $n$ 维的空间划分成两部分。

What is Simplex ?

A simplex in a $n$ -dimensional space is the convex hull of any $n+1$ points which do not lie in the same hyperplane.

考虑在二维平面的情况下，多个线性约束条件在平面上围成 Polyhedron. 而目标函数 $f(\bold{x})=c$ 画在平面上，如果和这个 polyhedron 有交点 $\bold{x}_k$ ，那么就说明 $\bold{x}_k$ 是可行解。所以，我们所希望的就是使 $c$ 尽量小，同时和 polyhedron 有交点. 而通常，当 $c$ 取最小的时候 $f(\bold{x})=c$ 与 polyhedron 交于某个 vertex (extreme point).

这个思想可以拓展到 $n$ 维空间中。平面 $\to$ $n$ 维空间，直线 $\to$ Hyperplane.

Canonical Form

先前我们知道线性规划的约束可以描述为 $\bold{Ax=b}$ . 如果 $\bold A$ 是 full rank 的 ( $\text{rank}(\bold{A})=n$ )，那么通过高斯消元，可以化为 Canonical Form

1x_1 + 0x_2 + \dots + 0x_n = b'_1 \\ 0x_1 + 1x_2 + \dots + 0x_n = b'_2 \\ \dots \\ 0x_1 + 0x_2 + \dots + 1x_n = b'_n

Basic Solutions

通常来说，约束的条件个数 $m$ 少于变量的个数 $n$ ( $m\le n$ ). 设系数矩阵 $\text{rank}(\bold{A})=m$ ，经过消元后，我们可以让 $m$ 个变量化成 Canonical Form，其余 $n-m$ 个变量为非 Canonical Form.

\begin{array}{r|ll} 1x_1 + 0x_2 + \dots + 0x_m &+ a_{1,m+1}x_{m+1} + a_{1,m+2}x_{m+2}+\dots+a_{1,n}x_n &= b'_1 \\ 0x_1 + 1x_2 + \dots + 0x_m &+ a_{2,m+1}x_{m+1} + a_{2,m+2}x_{m+2}+\dots+a_{2,n}x_n &= b'_2 \\ \dots \\ 0x_1 + 0x_2 + \dots + 1x_m & + a_{m,m+1}x_{m+1} + a_{m,m+2}x_{m+2}+\dots+a_{m,n}x_n & = b'_m \\ \hline \text{Canonical Form} & \text{Non-Canonical Form} \end{array}

所以从上面的方程组来看，我们可以得出一个显而易见的解：

\boxed{ \bold{x}=x_i=\begin{cases} b'_i, &\text{if } i\in [1,m]\\ 0, &\text{if }i\in[m+1, n] \end{cases}}

我们称 $x_i, i\in [1,m]$ 为 basic variables， $i\in[m+1, n]$ 为 non-basic variables. 并且，原始 $\bold{A}$ 矩阵中，与这 $m$ 个 basic variable 相关的行构成 $m$ 维空间里的线性基.

如果这个 basic solution 的所有 basic variable 都有非负值，那么这个 basic solution 已经是 feasible solution 了，被称为 basic feasible solution.

我们一共会有 $\binom{n}{m}$ 个可能的 basic solution，而我们也可以从一个 basic solution 得出另一个 basic solution: 我们可以通过消元，把一个 non-basic variable 转化为 basic variable，同时把另一个 basic variable 转化为 non-basic variable.

Simplex Method

Geometric Interpolation of Basic Solutions

每一个 basic feasible solution 对应 polyhedron 上的一个 extreme point.

一个可行的思路是检查 polyhedron 上所有的 extreme point. 代数上的等价思路是 operate on canonical form of the equality constraints set, 从一个 basic feasible solution 移动到另一个 basic feasible solution 上.

Problems with Only $\le$ Type Inequality Constraints and Non-Negative RHS Values

我们从任意一个 basic feasible solution 出发，同时把目标函数 $f(\bold{x})$ 表示为仅含 non-basic variable 的形式.

我们应该怎么选择 non-basic variable 呢？假设当前的 basic feasible solution 中 non-basic variable 为 $x_i$ ，且其在 $f(\bold{x})$ 的系数为 $a_i$ . 我们总是选择 $x_i$ 使得 $a_i\lt 0$ 并且 $a_i$ 的绝对值最大，然后把这个 $x_i$ 换进 basic variable，直到我们找不到这样的 $x_i$ .

接着，我们需要选一个 basic variable 把它移入 non-basic variable. 我们为每一行定义 ratio test：当前行的 RHS value 除以那一列 (即将移入 basic 的 variable) 的系数. 我们选一个最小 ratio 的那一行进行替换（不替换已经替换过的行）