线性规划-内点法初探

参考：最优化理论与算法（第2版）（陈宝林）

书中首先介绍了将一般线性规划问题转化为Karmarkar标准问题求解，为简化计算，Karmarkar等人又给出了内点法以求解线性规划问题，此部分在书中为*号引申内容，介绍较为简略，此处也是对书中内容做简要的补充。

考虑如下线性规划问题
$$\begin{array}{ll}\max & {\mathbf{c}}^{\mathrm{T}}\mathbf{x}\\ \text{ s. t. }& \mathbf{A}\mathbf{x}⩽\mathbf{b}\end{array}$$
其中：$\mathbf{c},x\in {\mathbb{R}}^n$，$\mathbf{A}\text{ 是 }m\times n\text{矩阵, }m⩾n\text{. }$
算法的基本思想,是从内点 ${\mathbf{x}}^{(0)}$ 出发,沿可行方向求出使目标函数值上升的后继点,再从得到的内点出发, 沿另一个可行方向求使目标函数值上升的内点。

将问题进行松弛：
$$\begin{array}{ll}\max & {\mathbf{c}}^{\mathrm{T}}\mathbf{x}\\ \text{ s. t. }& \mathbf{Ax}+\mathbf{v}=\mathbf{b},\\ & \mathbf{v}⩾0.\end{array}$$
对于第k轮迭代，即有
$${\mathbf{v}}^{(k)}=\mathbf{b}-\mathbf{A}{\mathbf{x}}^{(k)}$$

• 随后进行Affine Scaling，这是因为：当 ${\mathbf{x}}^k$ 是非常接近边界又不是最优解时, 步长将被迫选得非常小, 到最优解的收敛将非常慢。
• 故：若当前解 ${\mathbf{x}}^k$ 不是很靠近 “中心”, 需要将坐标重新拉伸 (re-scale), (仿射) 变换到靠近 “中心”的位置。
• 如何定义一个可行域的中心：
  若 ${\mathbf{x}}^k=\mathbf{e}$, 则
  (1) ${\mathbf{x}}^k$ 距离边界 1 个单位.
  (2) 因此只要步长 ${\alpha }^k<1$, 则可确保 ${\mathbf{x}}^{k+1}>0$.

故可以定义对角矩阵：${\mathbf{D}}_k=\mathrm{diag}(\frac{1}{v_1^{(k)}},\cdots ,\frac{1}{v_m^{(k)}}$