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^Tx，对偶问题有可行解y，使得w=b^Ty，那么z≤w成立。

证明　这是因为z=a^Tx≤y^TAx≤y^Tb。　　　　　　　　　　证毕

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

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

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

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

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

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

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

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

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

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

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

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

y_iw^Tx_i≥1

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

约束条件最终为

−Bw≤−l

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

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

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

y_i（w^Tx_i）≥1−ξ_i

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

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

目标函数可以写为

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

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

习题

（1）生成20个在中的数据，并显示这些数据，同时显示最初的分割线，然后运行迭代算法，观察收敛情况。不可分点集如图2.3所示。

（2）生成100个数据，并显示这些数据，同时显示最初的分割线，然后运行迭代算法，观察收敛情况。

（3）生成1000个数据，并显示这些数据，同时显示最初的分割线，然后运行迭代算法，观察收敛情况。

（4）生成1000个在中的数据，然后运行迭代算法，观察收敛情况。

（5）修改迭代过程

重新完成上面的问题。

（6）在平面上列出200个点（或者若干点），其中100个点聚在一个区域，另外100个点聚在另一个区域，但在中间互有相交。使用线性规划的方法找出一个分类的超平面。

（7）线性规划中对于分类问题的优化函数的设定是否有问题？是否可以重新改变优化函数，使得分类更加有意义？

（8）计算分类的错误度或者损失函数。给出点集（x₁，y₁），（x₂，y₂），···，（x_n，y_n），其中，，y_i∈{−1，1}。定义

那么错误度或者损失函数就是|A|/n。如果优化的目标是使这个错误度最小，试利用Python的优化包重新设计算法，寻找，使得上述损失达到最小，并观察这种方法的优缺点。

（9）利用命令

     from sklearn import datasets
     from sklearn.datasets import load_breast_cancer
     sklearn.datasets.load_breast_cancer
     data = load_breast_cancer（）

调取数据，同时对数据进行分类，完成Breast Cancer的诊断。

（10）使用给出的Default of Credit Card数据来进行分析，试做出分类。