线性规划问题

定义

当目标函数和约束函数都是仿射函数时，问题称为线性规划（Linear Program, LP）。线性规划问题的定义如下：

\begin{aligned} minimize & c^{⊤} x + d \\ subject to & G x ⪯ h \\ A x = b \end{aligned}

其中 $G \in R^{m \times n}$ 并且 $A \in R^{p \times n}$ 。显然，线性规划问题是凸优化问题。

可行域 $P$ 是一个多面体（图中蓝色六边形），目标函数 $c^{⊤} x$ 是线性的，所以其等位曲线是与 $c$ 正交的超平面（如虚线所示）。点 $x^{⋆}$ 是最优的，它是 $P$ 中在方向 $- c$ 上最远的点。

在标准形式线性规划中仅有的不等式都是分量的非负约束 $x ⪰ 0$

\begin{aligned} minimize & c^{⊤} x \\ subject to & A x = b \\ x ⪰ 0 \end{aligned}

如果线性规划问题没有等式约束，则成为不等式形式线性规划

\begin{aligned} minimize & c^{⊤} x \\ subject to & A x ⩽ b \end{aligned}

有时我们需要将一般的线性规划转化为标准形式。第一步是为不等式引入松弛变量 $s_{i}$ ，得到

\begin{aligned} minimize & c^{⊤} x + d \\ subject to & G x + s = h \\ A x = b \\ s ⪰ 0 \end{aligned}

第二步是将变量 $x$ 表示为两个非负变量 $x^{+}$ 和 $x^{-}$ 的差，即 $x = x^{+} - x^{-}$ ， $x^{+}, x^{-} ⪰ 0$ ，从而得到问题

\begin{aligned} minimize & c^{⊤} x^{+} - c^{⊤} x^{-} + d \\ subject to & G x^{+} - G x^{-} + s = h \\ A x^{+} - A x^{-} = b \\ x^{+} ⪰ 0, x^{-} ⪰ 0, s ⪰ 0 \end{aligned}

这是标准形式的线性规划，其优化变量是 $x^{+}$ 、 $x^{-}$ 和 $s$ 。

在多面体上极小化仿射函数纸币的问题称为线性分式规划

\begin{aligned} minimize & \frac{c^{⊤} x + d}{e^{⊤} x + f} \\ subject to & G x ⪯ h \\ A x = b \end{aligned}

这个函数是拟凸的（事实上是拟线性的），因此线性分式规划是一个拟凸优化问题。

如果可行集

{x ∣ G x ⪯ h, A x = b, e^{⊤} x + f > 0}

非空，则线性分式规划可以转换为等价的线性规划

\begin{aligned} minimize & c^{⊤} y + d z \\ subject to & G y - h z ⪯ 0 \\ A y - b z = 0 \\ e^{⊤} y + f z = 1 \\ z ⩾ 0 \end{aligned}

其优化变量为 $y$ 和 $z$ 。