线性规划问题 --- Linear Program Problem

线性规划问题 — Linear Program Problem

作者：Alex Hu
博客：https://blog.****.net/m0_37204267
转载请注明作者和出处。

---

1. LP问题的一般形式

当目标函数和约束函数都是放射时， 问题称作线性规划（LP）。一般线性规划具有以下形式：

其中 G∈Rm×n,A∈Rp×n，⪯$G\in {\mathbb{R}}^{m\times n},A\in {\mathbb{R}}^{p\times n}，⪯$ 表示广义不等号。

线性规划也是凸优化问题。它的可行集是一个多边形。几何解释如下：

---

2. LP的两种特殊形式

LP问题的以下两种形式已被深入研究。

• 标准形式线性规划
  
  minimizesubject tocTxAx=bx⪰0$$\begin{array}{rlr}& \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& c^{T}x\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& Ax=b\\ & & x⪰0\end{array}$$
• 不等式形式线性规划
  
  minimizesubject tocTxAx⪯b$$\begin{array}{rlr}& \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& c^{T}x\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& Ax⪯b\end{array}$$

---

3. 将一般形式转换为标准形式

将一般形式转化为标准形式的目的是：为了使用标准形式线性规划的算法。
这些转化技巧可以用来将很多问题构造为线性规划。
一般转化步骤为：

1. 引入松弛变量si$s_i$，得到
   
   minimizesubject tocTx+dGx+s=hAx=bs⪰0$$\begin{array}{rl}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& c^{T}x+d\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& Gx+s=h\\ & Ax=b\\ & s⪰0\end{array}$$
2. 将变量x$x$表示成两个非负变量x+$x^{+}$和x−$x^{-}$的差，即 x=x+−x−$x=x^{+}-x^{-}$ ，其中 x+,x−⪰0$x^{+},x^{-}⪰0$ ，从而得到问题
   
   minimizesubject tocTx+−cTx−+dGx+−Gx−+s=hAx+−Ax−=bx+⪰0,x−⪰0,s⪰0$$\begin{array}{rl}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& c^T{x}^{+}-c^T{x}^{-}+d\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& G{x}^{+}-G{x}^{-}+s=h\\ & A{x}^{+}-A{x}^{-}=b\\ & x^{+}⪰0,x^{-}⪰0,s⪰0\end{array}$$
   
   这是标准形式的线性规划，其优化变量为x+,x−和s$x^{+},x^{-}和s$。

---

4. 线性分式规划

在多面体上极小化仿射函数之比的问题被称为线性分式规划：

的目标函数由

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

转换为线性规划

可行集非空时，线性分式规划可转换为等价的线性规划

优化变量为x,z$x,z$。
为了显示这个等价性，如果x$x$是原始形式的可行解，那么

是转换后的可行解，并且具有相同的目标函数值cTy+dz=f0(x)$c^{T}y+dz=f_0(x)$。

---

参考文献

[1] Stephen Boyd, et al. Convex Optimization. Cambridge university press, 2004.
[2] 王书宁, 等. 凸优化. 清华大学出版社, 2013.