线性规划问题

定义

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

$$ \begin{aligned} \mathrm{minimize} \quad & c^Tx+d \\ \mathrm{subject\ to} \quad & Gx \preceq h \\ \quad & Ax=b \end{aligned} $$

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

几何意义

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

线性规划的标准形式和不等式形式

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

$$ \begin{aligned} \mathrm{minimize} \quad & c^Tx \\ \mathrm{subject\ to} \quad & Ax=b \\ \quad & x \succeq 0 \end{aligned} $$

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

$$ \begin{aligned} \mathrm{minimize} \quad & c^Tx \\ \mathrm{subject\ to} \quad & Ax \leqslant b \end{aligned} $$

将线性规划转化为标准形式

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

$$ \begin{aligned} \mathrm{minimize} \quad & c^Tx+d \\ \mathrm{subject\ to} \quad & Gx+s=h \\ \quad & Ax=b \\ \quad & s \succeq 0 \end{aligned} $$

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

$$ \begin{aligned} \mathrm{minimize} \quad & c^Tx^+-c^Tx^-+d \\ \mathrm{subject\ to} \quad & Gx^+-Gx^-+s=h \\ \quad & Ax^+-Ax^-=b \\ \quad & x^+ \succeq 0, x^- \succeq 0, s \succeq 0 \end{aligned} $$

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

线性分式规划

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

$$ \begin{aligned} \mathrm{minimize} \quad & \frac{c^Tx+d}{e^Tx+f} \\ \mathrm{subject\ to} \quad & Gx \preceq h \\ \quad & Ax = b \end{aligned} $$

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

转化为线性规划

如果可行集

$$ \{ x \mid Gx \preceq h, Ax=b, e^Tx+f > 0 \} $$

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

$$ \begin{aligned} \mathrm{minimize} \quad & c^Ty+dz \\ \mathrm{subject\ to} \quad & Gy-hz \preceq 0 \\ \quad & Ay-bz=0 \\ \quad & e^Ty + fz = 1 \\ \quad & z \geqslant 0 \end{aligned} $$

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

Previous
Next