单纯形法的复杂性、椭球法与内点法

单纯形法在实践中通常很快，但“通常快”不等于“最坏情形是多项式时间”。复杂性分析衡量的是输入位数增长时，算法最多需要多少基本运算。

输入规模不是变量个数

线性规划的输入由有理数系数构成。一个整数 $a$ 的二进制编码长度约为 $\log_2(1+|a|)$ ，因此问题规模不仅取决于 $m,n$ ，也取决于系数需要多少位表示。

若算法运行时间被输入编码长度的某个多项式控制，称为多项式时间算法。若复杂度只对数值大小呈多项式、却对编码长度呈指数，则称伪多项式而非真正多项式。

Klee–Minty 立方体通过精心扰动普通立方体，使某些单纯形进基规则沿几乎所有 $2^n$ 个顶点走一遍。课程中的递推约束例子展示：即使约束数和变量数线性增长，迭代次数也可能达到 $2^n-1$ 。

因此：

\boxed{\text{单纯形法不是已知的多项式时间算法。}}

这不否定它的工程价值。现代实现配合预处理、稀疏线性代数和良好定价规则，在大量实际 LP 上非常高效，还能直接给出基与灵敏度信息。

椭球法不沿多面体边移动，而是维护一个包含候选解的椭球。每次取椭球中心：

椭球体积按固定比例下降，结合有理解的位数界，可在多项式次数内判断可行或逼近最优。它第一次证明一般线性规划属于多项式可解，但实际常数和数值表现通常不如单纯形或内点法。

考虑已有严格内点的标准形线性规划

\min c^Tx,\qquad Ax=b,\qquad x>0.

假设 $A\in\mathbb R^{m\times n}$ 满行秩，即

\operatorname{rank}(A)=m.

在第 $k$ 次迭代，把当前点各坐标的大小收进对角矩阵

D_k=\operatorname{diag}(x_1^{(k)},\ldots,x_n^{(k)}), \qquad y=D_k^{-1}x.

这样当前点被缩放为全 1 向量 $e$ ，而等式约束变成 $AD_ky=b$ 。在缩放空间中，到 $\ker(AD_k)$ 的正交投影为

P_k=I-D_kA^T(AD_k^2A^T)^{-1}AD_k.

因为 $x^{(k)}>0$ ， $D_k$ 可逆；再结合 $A$ 满行秩， $AD_k^2A^T$ 正定，所以上式中的逆存在。

把目标梯度 $D_kc$ 投到等式约束的切空间，再取负方向，映回 $x$ 空间：

\boxed{d_x^{(k)}=-D_kP_kD_kc}.

定义步长前必须先检查

q_k=P_kD_kc.

若 $q_k=0$ ，则投影梯度与搜索方向都为零。此时 $D_kc$ 属于 $(AD_k)^T$ 的值域，等价于存在 $y$ 使 $c=A^Ty$ ；当前严格可行点满足 LP 的最优性条件，算法应直接停止，不能继续代入步长公式造成除零。

仅当 $q_k\ne0$ 时，课件采用的步长是

\alpha_k=\frac{1}{\lVert q_k\rVert} =\frac{1}{\lVert P_kD_kc\rVert}, \qquad x^{(k+1)}=x^{(k)}+\alpha_kd_x^{(k)}.

这里有两个必须会解释的性质：

若更新后某个坐标恰好为零，按课件中的定理可判该迭代点最优；否则新的点仍在内部，重新构造 $D_{k+1}$ 与 $P_{k+1}$ 。仿射尺度法的直觉是：每一步都把当前内点周围“拉成近似球形”，再沿投影后的负梯度走到这个局部球的边界。

内点法在可行域内部移动，不追逐极点。对不等式约束加入障碍项，例如

\min_x c^Tx-\mu\sum_i\log s_i,\qquad Ax+s=b,\quad s>0.

当 $\mu$ 逐渐减小时，障碍问题的解沿中心路径接近原 LP 最优解。每一步通常需要解 Newton 线性方程组，但迭代次数具有多项式界，且适合大规模稀疏问题。