第43章凸集，锥，H多面体

43.1什么是线性规划？

什么是线性规划？乍一看，人们可能会认为这是某种类型的计算机编程。毕竟，有命令式编程、函数式编程、面向对象编程等。线性编程这个术语有点误导，因为它实际上是指一种带有线性约束的规划方法，或者更准确地说，是一种优化方法，在这种方法中，目标和目标都是NCtion和约束是线性的。

线性规划是在20世纪40年代末创建的，其中一个关键的参与者是发明了simplex算法的George Dantzing。早在1939年，Kantorovitch就在线性编程方面做了一些开创性的工作。线性规划这一术语具有军事内涵，因为在20世纪50年代早期，它被用作训练部队、后勤供应、资源分配等计划或时间表的同义词。不幸的是，线性规划这一术语已经很好地建立起来，我们一直坚持使用它。

有趣的是，尽管线性规划最初大部分应用于经济学和工业工程领域，但线性规划已成为理论计算机科学和算法理论中的一个重要工具。实际上，线性规划通常是设计近似算法以解决困难问题（通常是NP困难问题）的有效工具。线性规划也是凸规划的“婴儿版”，是近年来备受关注的一种非常有效的方法。

我们在这些笔记中的目标是呈现线性规划的数学基础，特别是如果线性规划是可行和有界的，最优解的存在性，以及线性规划中的对偶定理，这是这一领域最深的成果之一。线性规划中的对偶定理也有重要的算法含义，但我们这里不讨论这个问题。我们提出了单纯形算法、双单纯形算法和原对偶算法。我们还描述了舞台形式主义

一千四百一十一

用于运行simplex算法及其变体。Tableau形式主义的一个特别好的特点是，可以使用基本行操作来更新Tableau，这与将矩阵缩减为行的梯队形式（rref）过程中使用的操作相同。不同的是选择轴的标准。

但是，我们不讨论其他方法，如椭球法或内点法。对于更多的算法问题，我们向读者介绍线性规划的标准文本。在我们看来，是最清晰的（也是最简洁的！）马托塞克和加德纳[120]；契瓦塔[40]和施里伊弗[144]是经典之作。Papadimitriou和Steiglitz[130]在组合优化的更广泛的背景下提供了非常清晰的介绍，Bertsimas和Tsitiklis[21]和Vanderbei[175]非常完整。

线性规划必须与最大化线性成本函数c1x1+·····+cnxn有关形式的m“线性”不等式。

ai1x1+·····+ainxn≤bi。

这些约束可以组合成一个m×n矩阵a=（aij），并更简洁地写为

ax≤b。

由于稍后出现的技术原因，通常最好在i＝1，n，n上加上非负乘积Xi±0，写x＝0。很容易看出，每一个线性程序都等价于另一个满足约束x≥0的程序，而代价是添加新的变量，这些变量也被约束为非负的。设p（a，b）为线性规划的可行解集，由

p（a，b）=x∈rn ax≤b，x≥0。

然后有两个基本问题：

(1) p（a，b）是非空的，也就是说，我们的线性规划有机会得到一个解吗？

(2) 目标函数c1x1+·····+cnxn在p（a，b）上有最大值吗？

这两个问题的答案都可以是否定的，但如果p（a，b）是非空的，并且目标函数在p（a，b）上有界，则可以证明，c1x1+······+cnxn的最大值是由x∈p（a，b）得到的。这种解称为最优解。也许令人惊讶的是，这个结果并不那么容易证明（除非有人使用单纯形方法作为处理方法）。我们将详细证明这一结果（见提案44.1）。

线性约束之所以如此重要，是因为潜在最优解P（A，B）的域是凸的。实际上，p（a，b）是一个凸多面体，它是仿射超平面截取的半空间的交集。线性的目标函数是凸的，这也是一个重要的事实。因此，我们研究了凸集，特别是那些由仿射形式定义的不等式解产生的凸集，同时也研究了凸锥。

43.2。仿射子集、凸集、超平面、半空间

我们简要介绍了这些主题。作为奖励，我们提供了几个标准来检验一个不平等系统是否

ax≤b，x≥0

是否有关于法卡斯引理的解决方案（见命题49.3和46.4）。然后我们给出了线性规划强对偶定理的完全证明（见定理46.7）。我们还讨论了互补松弛条件，并证明了它们可以用来设计一种同时使用原问题和对偶问题的线性规划求解算法。这种被称为原始对偶算法的算法，尽管目前没有被广泛使用，但它一直是一类近似算法（也被称为原始对偶算法）的灵感来源。

我们希望这些笔记将成为学习更多线性规划、凸优化以及凸几何的动力。凸面优化中的“圣经”是Boyd和Vandenberghe[29]，凸面几何的最佳来源之一是Ziegler[189]。这是一个相当高级的文本，因此读者可能希望从Gallier开始[74]。

43.2仿射子集、凸集、仿射超平面、半空间

我们认为RN由列向量（n×1矩阵）组成。与往常一样，行向量表示线性形式，即线性映射，如果所有x∈r n的行向量y（a 1×n矩阵）表示线性形式，则表示线性形式。我们用（rn）表示线性形式（行向量）的空间。

回想一下，RN中向量的线性组合是一个表达式

λ1x1+····+λmxm

其中，X1，…，XM*Rn，其中，La 1，…，Lm m是R中的任意标量，给定一个向量序列S＝（x1，…，xm），其中，S中的向量的所有线性组合的集合是包含S的线性跨度的S的最小（线性）子空间，并表示跨度（S）。RN的线性子空间是线性组合下封闭的RN的任何非空子集。RN中向量的仿射组合是一个表达式。

λ1x1+····+λmxm

式中，x1，…，xm∈rn，式中，λ1，…，λm是满足条件的r中的标量。

λ1+····+λm=1.

给定一个向量序列s=（x1，…，xm）的序列，在XS中，S中所有向量的仿射组合集合是包含S的仿射壳的最小仿射子空间，并表示为AFF（S）。

（a）（b）

图43.1：（a）凸集；（b）非凸集

定义43.1.RN的仿射子空间A是仿射组合下封闭的RN的任何子集。

如果a是rn的非空仿射子空间，则可以证明va=a−b a，b∈a是rn的线性子空间，称为a的方向，并且

a=a+va=a+v v∈va

对于任意a∈a，非空仿射子空间a的维数是其方向va的维数。

凸组合是满足i=1，…，m时λi≥0的附加条件的仿射组合。

定义43.2.Rn的一个子集v是凸的，如果对于任意两点a，b∈v，对于每一点c=（1−λ）a+λb，我们有c∈v，其中0≤λ≤1（λ∈r）。对于任意两点a，b，符号[a，b]通常用于表示a和b之间的线段，即，

[a，b]=c∈rn c=（1−λ）a+λb，0≤λ≤1，

因此，当任意两点a，b∈v（a=b）允许时，集合v是凸的。凸集V的维数是它的仿射壳aff（a）的维数。

空集是平凡的凸集，每一个点集a是凸集，整个仿射空间rn是凸集。

显然，任何凸集族（有限或无限）的交集都是凸的。

定义43.3.给定RN的任何（非空）子集，包含s的最小凸集用conv（s）表示，称为s的凸壳（它是包含s的所有凸集的交集）。

43.2。仿射子集、凸集、超平面、半空间

不仅要对conv有很好的理解，而且要有很好的计算方法。我们有以下简单但关键的结果。

命题43.1.pλi a i（其中对于任何家族i∈iλi=1sand=（aλi）ii≥∈i 0of points in）是凸的hullrn，s=（ai）i∈i的setconv（v of凸包combi-）。

国家I∈I

很自然地会想，43.1命题是否可以在两个方向上进行锐化：（1）是否可以在凸组合中涉及的点的数量上有一个固定的界限？（2）是否有必要考虑所有点的凸组合，或仅考虑具有特殊性质的子集？

在这两种情况下，答案都是肯定的。在案例1中，Carath’Eodory定理断言它足以考虑n+1点的凸组合。例如，在平面r2中，一组点的凸壳是所有三角形（包括内部点）与S中顶点的结合。在案例2中，Krein和Milman的定理断言，也紧凑的凸集是其极值的凸壳（给定凸集s，如果S−A也是凸的，则点A∈S是极值。

我们不会在这里证明这些定理，但我们邀请读者咨询Gallier[74]或Berger[12]。

凸集也作为仿射超平面切出的半空间出现。

定义43.4.一个仿射式，由一些线性形式c∈（rn）和一些标量β∈r定义，因此

⑨（x）=cx+β，所有x∈rn。

如果c=06，由（c，β）指定的仿射式瓒定义仿射超平面（对于短超平面）h（瓒），由

h（）=x∈rn （x）=0=x∈rn cx+β=0，

两个（封闭的）半空间

.

当β=0时，我们称H为线性超平面。

H+（_）和H−（）均为凸形，H=H+（）H−（）。

例如，：r2→r，其中（x，y）=2x+y+3是一个仿射形式，定义了方程y=−2x−3给出的直线。仿射形式的另一个例子是：:r3→r，其中（x，y，z）=x+y+z−1；该仿射形式定义了方程x+y+z=1给出的平面，即通过点（0,0,1）、（0,1,0）和（1,0,0）的平面。这两个超平面如图43.2所示。

I.I.

图43.2：图1.说明了图2所示的超平面h（）对于（x，y）=2x+y+3。说明了（x，y，z）=x+y+z-1的超平面h（）。

对于x＝（x1，…，xn）和y＝（y1，…，yn）的任意两个向量x，y[r] rn，我们写x＝y y ff Xiωy，i＝1，…，n，x x y y y y y y×x，特别是x＝0，i＝i＝0，i＝1，…，n。

某些特殊类型的凸集称为锥和H多面体起着重要作用。线性规划的可行解集是H多面体，锥在44.1命题的证明和Farkas-Minkowski命题（命题）中起着至关重要的作用。

46.2）。

43.3锥体、多面体锥体和H多面体

锥体和多面体锥体定义如下。

定义43.5.给定一个非空子集s rn，由s横跨的圆锥体c=圆锥体是凸集。

锥体，（

从S来的向量的正组合。如果S由一组有限的向量组成，则C=锥称为多面体锥。图43.3显示了多面体圆锥体。

注意，如果某个非零向量u属于一个锥c，那么对于所有的λ≥0，则λu∈c，也就是说，射线λuλ≥0属于c。

注：定义43.5的锥体（和多面体锥体）总是凸的。因此，我们使用了更简单的术语“锥”而不是“凸锥”。然而，有更多非凸的圆锥（例如多面体圆锥的联合）

图43.3：设s=（0,0,1），（1,0,1），（1,1,1），（0,1,1）。多面体圆锥体，圆锥体，是一个实心“金字塔”，其顶点位于原点，横截面为正方形。

或者由图43.4中的曲线生成的线性圆锥），如果我们处理这些，我们将把定义43.5中的圆锥称为凸锥。

定义43.6.H多面体，简称多面体，是定义为有限个闭半空间Ci的交集的任何子集。一个例子

如图43.6所示，有一个闭球多面体的艾哈迈恩例子。中心多面体43.5.x和半径的图b（x）中显示了Anh多面体，其有界r>0，因此h多面体，其中p br（x）。

根据惯例，我们同意RN本身是一个H多面体。

注：定义43.6的H多面体总是凸的。因为这个原因，就像在多面体而不是凸的H多面体中一样。圆锥的情况下，我们使用简单的术语h

在代数拓扑学中，有更多的非凸多面体。

结果表明，H-多面体P等于有限多点（P的极值点）的凸壳。这是一个非常重要的结果，其证明需要大量的工作；见Gallier[74]和Ziegler[189]。

无界H多面体不等于有限点集的凸壳。为了得到一个等价的概念，我们引入了V多面体的概念。

定义43.7.v多面体是形式的任何凸子集a rn。

a=conv（y）+cone（v）=a+v a∈conv（y），v∈cone（v），

图43.4:z=1的平面曲线。s的线性圆锥体，由连接s到原点的所有半射线组成，不是凸形的。

其中y rn和v rn是有限的（可能是空的）。

当v=∅时，我们只得到一个多面体，当y=∅或y=0_时，我们只得到一个圆锥体。

可以看出，每个H多面体都是V多面体，反之亦然。这是多面体理论中的一个重要定理，它的证明是非平凡的。完整的证据见Gallier[74]和Ziegler[189]。

每个多面体圆锥都是闭合的。这是一个重要事实，用于证明其他几个关键结果，如命题44.1和Farkas–Minkowski命题（命题46.2）。

虽然多面体圆锥应该是闭合的，但严格的证明并不完全是微不足道的。

实际上，多面体圆锥体是闭合的这一事实，关键在于C是由有限数量的向量构成的，因为无限集生成的圆锥体可能不会闭合。例如，考虑圆心（0,1）和半径1的闭圆盘d r2，它与原点的x轴相切。然后，圆锥体（d）由打开的上半平面加上原点（0,0）组成，但该集合不是闭合的。

提案43.2.每个多面体锥c都是闭合的。

证据。证明了这一点

\1. 每个原始圆锥体都是闭合的。

图43.5：二十面体是H-多面体的一个例子。

\2. 多面体圆锥体c是有限多个原始圆锥体的联合，其中原始圆锥体是由线性无关向量跨越的多面体圆锥体。

假设（a1，…，am）在rn中是线性无关的向量，并考虑任何se-

频率（x（k））k≥0

原始圆锥体（a1，…，am）中的向量，这意味着

1，…，m和所有k≥0。向量x（k）属于（a1，…，am）所跨越的子空间u，u是闭合的。假设序列（（k）∈u对于所有k≥0，我们有xx（∈k））uk≥。如果我们写0收敛到一个极限x=x1a1+x········r+n.sincexmam，weu是闭的，x

希望证明i＝1，…，m的Xi超0，序列（x（k））k＝0收敛到x。

敌我识别

敌我识别

敌我识别

由于所有k＝0，对于I＝1，…，M，SO x锥（{A1，…，AM}），我们都有Xi±0。

接下来，假设x属于多面体锥c。考虑正组合。

x=λ1a1+····+λkak，（1）

对于一些非零a1，…，ak∈c，其中λi≥0且k最小。因为k是最小的，所以i=1，…，k时我们必须有λi>0。我们声称（a1，…，ak）是线性无关的。

（2,0,0）转换（Y）（-2,0,0）

图43.6：由不等式y−z≤0、y+z≥0和−2≤x≤2确定的“三角形槽”是H多面体和V多面体，其中y=（2,0,0）、（−2,0,0）和v=（0,1,1）、（0、−1,1）。

如果不是，有一些非平凡的线性组合

1+·····+k=0，（2）

由于ai不为零，对于一些至少一些j，μj=06。我们可以假设对于一些j，μj<0（否则，我们考虑族（−μi）1≤i≤k），那么让

j=j∈1，…，k _礹j<0。

对于任何t∈r，由于x=λ1a1+····+λkak，使用（2）我们得到

，（3）

如果我们选择

对于i=1，…，k，我们有（λi+tμi）≥0，但是对于一些j∈j，λj+tμj=0，因此（3）是x的表达式，其系数小于k非零，包含k的最小值（1）。

因此，（A1，…，AK）是线性无关的。

由于多面体的锥C是由有限多个向量构成的，因此有有限多个原始锥（对应于线性无关的子族），并且由于每个X∈C都属于某个原始锥，因此C是有限个原始锥的并集。由于每个原始圆锥体都是封闭的，作为有限多个闭集的联合，C本身是封闭的。

上述事实也在马托塞克和加德纳[120]中得到证明（第6章第5节，引理6.5.3、6.5.4和6.5.5）。

证明多面体锥C是闭合的另一种方法是证明C也是H多面体。这需要更多的工作；见Gallier[74]（第4章，第4节，提案4.16）。LAX[110]中给出了另一个证明（第13章，定理1）。