2.2 线性规划

线性规划是最基本的优化问题，灵活运用线性规划在工作中非常重要。下面对本书经常使用的符号问题进行说明。对于具有若干分量的两个向量 a ， b ，当 a ≤ b 时，表明 a 的每个分量都不大于对应 b 的分量；当 a ≥ 0 时，表明 a 的每个分量都是非负值；当 a ≤ 0 时，表明 a 的每个分量都是非正值。

为了更好地理解线性规划，下面将列出欧几里得空间中的超平面和半空间相关定义。

定义2.1 对于给定的 ，定义的空间 的一个超平面是集合

超平面分割的空间称为半空间。任意一个半空间的表示如下

在空间中的半空间和超平面都属于一种更加广泛的集合。这种集合就是凸集的概念。

定义2.2 在空间 中的一个区域 Ω 称为凸集，如果满足任意 x，y ∈ Ω ，就有 λx +（1- λ ） y ∈ Ω 对于所有0＜ Ω ＜1都成立。

定义2.3 在空间 中的多面体就是有限个半空间的交集。

P ={ x | Ax ≤ b }

其中， A 是 m × n 的矩阵， b 是 n 维向量，所以 P 事实上是由 m 个半空间相交构成。

任何一个欧几里得空间的区域都有内点和边界点的区分。内点的定义是指该点的任意一个邻域内都有区域的其他点。而边界点的任何邻域都有属于这个区域的点，也有不属于这个区域的点。对于多面体，不仅可以定义内点、边界点，还可以将其区分得更加细致。接下来要讨论的多面体都是闭集合。

定义2.4 如果点 x 不能表示成为多面体 P 上两个不同的点的线性组合，则在这个多面体 P 上的点 x 称为极端点。

例如，在二维空间中，由若干半平面的交集构成一个凸多边形，这时，极端点就是这个多边形的顶点。无论是这个凸多边形的内点还是非顶点的边界点，都不是极端点。同理，可以定义极端方向。

定义2.5 在一个多面体 P 上的向量 d 称为一个方向，如果有点 x ∈ P ，使得 x + λ d ∈ P 对所有 λ＞ 0都成立。

例如，在二维空间中，如果若干半平面的交集是一个点和从这个点出发的两条射线构成的角度，那么从这个点出发的在角度内的直线都构成了方向。

定义2.6 如果一个多面体 P 上的方向 d 不能表示为两个方向的线性组合形式，我们就将其称为一个极端方向。

由上面的例子可知，从一个点出发的两条射线的夹角部分构成的凸集的极端方向就是两条射线方向。在这些定义下，可以从线性组合的角度来理解多面体内每个点的表示。正如三角形内的每个点都可以表示为三角形三个顶点的线性组合一样，这个性质对于一个空间的多面体也是成立的。

定理2.2 任何多面体 P 上的一个点 x 都有

其中， λ _i ，µ _j ＞0， x _i 都是极端点， d _j 都是极端方向，且

上述定理的证明并不困难，在任何一本凸分析的书籍中都应该有介绍。如果一个多面体是有界的，根据定义一定没有极端方向，从而有界多面体 P 上的一个点 x 退化成为

其中， x _i 是极端点，且

对于一个线性函数 ，在多面体的点 x 上的表示必然有

其中， λ _i 都是极端点。所以这个函数必然在极端点上达到最大或者最小。

有了上述准备工作，现在就可以陈述线性规划及其对偶问题。线性规划是最基础也是最重要的优化线性函数的方法。一般有一组实变量

x ₁ ，x ₂ ，··· ，x _n

根据需求，会面临下面的问题。在满足下面的一组关于 x _i 的约束条件下

需要优化函数

因为约束条件是线性的，而优化的函数也是线性的，所以称为线性规划。使用矩阵和向量的语言可以表述如下： 是一个固定向量， 是参变量， A 是一个 m × n 的矩阵， ，考虑下面的带有约束的优化问题

其中， Az ≤ b 是指对于向量的每个分量都成立。对于线性规划的一般描述，满足约束条件 Az ≤ b 的点 z 未必存在，如果存在，则是一个可行解。

线性规划的解如果存在，应该在多面体的极端顶点上寻找。在求解数值时要寻求高效的方法。

一般线性规划问题是可以利用软件包求解的，线性规划问题的解可以转化为凸优化问题，因为线性的约束条件构成的区域还是凸性的区域。为了进一步理解线性规划并叙述线性规划的对偶问题，现在列出线性规划的典范形式。通过增加一些变量把任意一个 x 表示为 x = x ⁺ - x ^- ，其中

在线性规划中的变量都可以看成是正值，从而典范形式可以写为

其中， x ≥ 0 表示任何一个分量都是非负值。写成上述形式后，就可以陈述其对偶问题，对偶问题的陈述也是一个线性规划，其形式为

关于原问题和其对偶问题之间的关系，有以下一系列定理。

定理2.3 如果原问题有任意可行解 x ，使得 z = a ^T x ，对偶问题有可行解 y ，使得 w = b ^T y ，那么 z ≤ w 成立。

证明 这是因为 z = a ^T x ≤ y ^T Ax ≤ y ^T b 。证毕

定理2.4 如果原问题是无上界的，那么对偶问题没有可行解。如果对偶问题是无下界的，那么原问题没有可行解。

证明 上面的不等式即证明了这一点。证毕

最后是原问题和对偶问题的一致性定理。

定理2.5 如果原问题和对偶问题都有可行解，同时解也是有界的，那么 z = w 。

这个定理的证明也可以在一般线性规划教科书中找到。其实这个定理是一般的Minimax定理的特殊形式。

至此，线性规划的核心问题都已经陈述完毕。线性规划不但可以解决上面的问题，也可以解决一些表面的非线性函数问题。例如

也可以转换为标准的线性规划问题。首先将上面的问题转换为

其次，对于任意实数 x 都有 u，v ≥0，使得

x =（ u - v ）/2，| x |=（ u + v ）/2

现在可以把上面的问题最终转换为

这就成了一个典型的线性规划问题。

使用线性回归也可以解决感知机的分类问题。从本质上说，是为了寻找 y _i （ w ^T x _i ）＞0的解。如果存在一个 w 使得对任意 i 都有 ，那么一定可以重新归一化，使得必然存在一个 w ，满足

y _i w ^T x _i ≥1

所以线性规划问题就成为一个没有目标函数，只有约束条件的问题。可以使用矩阵写法，令矩阵

约束条件最终为

- Bw ≤- l

的标准形式，使用标准线性规划算法就可以得到解答。

在上一节中感知机处理的问题是在点集完全可分的情况下提出的，但通常情况下，点集不是完全可分的，如图2.2所示。在点集不完全可分时，目标显然不能是使损失函数为零。

为此，需要改进目标函数。不能要求处处满足 y _i （ w ^T x _i ）≥1，但可以尝试满足

y _i （ w ^T x _i ）≥1- ξ _i

其中， ξ _i ≥0。这样的 ξ _i 虽然存在，但可能不唯一。而且 ξ _i 越大，得到的超平面就越没有意义。在所有的 ξ _i 中，其绝对值应尽可能小。这样就可以形成一个新的问题

为了转换为标准形式，还要使用矩阵语言。把向量 w 和 ξ 联合在一起成为一个维数更大的向量，同时使用上面定义的矩阵 B ，约束条件就可以写为

目标函数可以写为

这里的零矩阵是一个1× k 的向量。

至此，空间中不同颜色点集的分类问题便可以得到圆满解答。一种方法是使用感知机的逐步迭代，另一种方法是调用线性规划。其实，在线性规划的实现过程中也是通过逐步迭代来找到最优解的。以后还会采用其他的办法来解决分类问题，如逻辑回归、朴素贝叶斯估计等。 1O/D2v/ExyW8hlIWR2/brDsAlsFajkBHiwCoF+VLEPVumxt9ZJ1U3/gF5UgyAmbG