线性规划算法英文翻译 (自动保存的).docx

线性规划（273）：我们将通过考虑线性规划问题继续随机抽样的研究。线性规划问题是体现两个主要随机化优点（简单和速度）最显著的例子。在9.10.1节我们将针对这一问题研究随机递增算法。线性规划问题就是寻找线性目标函数的极值问题，线性目标函数受到一些真实变量的约束。下面，我们将用d来表示变量的数量，用n来表示约束条件的数量。每个约束条件都可以将d维空间划分成两部分，这样的多个两部分组成一个交叉区域，我们所寻找的极值就会被限制在这个区域的一些点上。这个交叉区域是d维空间中的一个多面体，我们把这个区域称为可行域。在这个过程中，我们要测量我们所执行的算术操作的数量，把在连续的时间内算术运算被执行的操作数作为真实的数据，这个和我们本节的观点是一致的，但有一点要提醒的是线性规划问题的很多工作都与操作数的有限精度有关。对于这种有限精度的操作数，在通过各种算法进行在操作时都需要认真考虑它们。我们对于少量的操作不会太关心，但是会把所有的数量作为原子操作数来考虑。让x1, xd表示线性问题中的d个变量，让c1, cd表示这些变量的系数，让Aij,1in, 1jd,表示第i个约束中xj的系数。让A表示矩阵（Aij），C表示矩阵中的向量（c1, cd），X表示矩阵中的向量（x1, xd），线性规划问题可以如下表示： mincTx 9.11条件 Axb (9.12)B是常数列向量。我们用A和b来表示可行域，表示为FA,b。向量C在d空间中指定了一个方向。从几何上说，我们在可行域FA,b中沿着指向C的方向寻找最远的点，前提是存在一个这样的有限点。线性规划问题有很长的历史，在注释部分有介绍。在我们处理的点中，伴随着起始点会有一系列的假设，这将有助于捕捉到线性规划问题；这些假设不会从设计算法的立场上不具有专业性和简洁性。所有这些假设都可以通过标准技术来去除；这一点会在问题9.8中会有进一步的研究。1. 多面体FA,b是非空并且是有界的。既然我们不假定我们能测试任意一个多面体为非空或有界的；这就相当于去解决一个线性规划。我们仅仅对FA,b做出这种假定。2. 我们把目标函数的最小值定义为x1；换句话说，假设c=(1,0,0)，以此我们用最小值x1在FA,b中寻找一个点。3. 我们寻找的最小值是在FA,b上的唯一的顶点。4. FA,b的每一个顶点都恰好符合d个约束条件。让H表示A和b定义的约束集，S为H的约束子集。我们经常考虑由子集S和c定义的线性规划定义的线性规划。当这样一个线性规划达到最小时，我们将会假定假设3-4仍然成立：（i）最小值是唯一的；（ii）可行域中的每一个点都是d个约束条件限定的。我们用O（S）表示由c和S定义的线性规划问题中目标函数的值。子集B是基础，因此对于任何B B ，O（B）-，并且O（B）O（B） 。H的基础是一个最小的子集B属于H，并且O（B）=O（H）。我们的目标是找到H，由于H定义了线性规划的最优点，我们有时会称H或者O（H）为线性规划的最优解。解决线性规划问题的一个方法是采用半空间相交算法来计算FA,b，然后对多面体FA,b的每一个顶点估算它的目标函数值。由于FA,b 顶点的数量有可能是nd/2，这种详细的估算过程一般来说会很慢。因此我们要寻找一种算法，不需要枚举FA,b中的每个顶点。在对线性规划进行随机算法研究之前，我们将会回想一下经典单纯行法的原理。这是一个确定的算法，从FA,b的一个顶点开始，随后每一次迭代，在目标函数有一个低值时算法会进行到邻近的一个点。如果不存在这样的点，那我们就找到了最小值。不过，这只是单纯行法的主要思想，当相邻点有同样的目标函数值，而且问题中没有最小值时，这种算法的复杂性也会增加。对于单纯形法我们将会避免详细的讨论；在讨论中我们只要确定存在一种单纯的函数通过逐个访问FA,b中的每个顶点直到找出最优解来解决线性规划问题就可以了，当然这个最优解应该是存在的。我们称约束hH如果O（Hh）O(H); 因此这些是H中的约束。直觉上说不是极端的约束H是冗余的约束，这种约束的缺失不会改变最优化。我们的第一个算法SampLP用随机抽样来迅速的去掉冗余约束。从空集开始，SampLP通过一系列阶段建立了约束集合S。在每一个阶段，集合V属于H但不属于S时，V被加入到S中。集合V有两个重要的性能：（i）它将会很小，（ii）在H（不包括S）中至少包含一个极端约束。因此当|H|=d,我们会在d阶段后停止。SampLP算法：输入：约束集H。输出：最优解H。1. S;2. 如果 n0随机选择RHS，并且|R|=r=mindn,|HS|; XSampLP(RS); VhH; 如果|V|2n 那么 SSV；2.3. 返回X； 因此对于n9d2SampLP选择r约束里的一个随机子集。r的值通常是dn，除非HS比dn包含更少的约束。它递归地解决被RS定义的线性规划，并且决定了VH妨碍了最优解；因此这些违反约束事实上来源于HS。如果V仅仅有2n个原理，我们把V添加到S里。当V变成空时，我们返回X。练习9.24：构建一个简单的例子表明，在通过SampLP的循环语句后，V可能不包含所有的H。因此，我们可能仅仅指出V至少包含H中的一个约束，而这个约束不在S里。常规的单纯形仅仅在9d2或更少的约束时调用。对于这种小的线性规划问题，我们可以像下面一样绑定调用单纯形的成本。对于这样一个成本，多面体的顶点总数不会超过（9d2d/2）,最多为（49d）d/2。我们有一个常数a,像这样单纯形法花在每个顶点上的很多时间是da,因此，我们有：引理9.14：在9d2或更少的约束时调用单纯形的总成本是Odd/(2+a)。 下一步，我们希望讨论V，不遵循X的约束集是小的。引理9.15：让SH，RHS是大小为r 的一个随机子集。让m表示|HS|。不属于O(RS)的H的约束集的期望数不超过d(m-r+1)/(r-d)。证明：对于由约束子集形成的线性规划，我们定义两个最优集。让H表示最优集 O(TS)|THS，因此SampLP的访问返回本集的一个元素。相同地，对于特定的子集R，我们定义R最优集为 O(TS)|TR。现在在R中O(RS)是唯一能满足R中每个约束的元素。对于每一个元素xH,让vx表示约束集侵犯x的数量。当x是O(RS)时让指数ix为1，否则为0。 我们可以写为 EV=ExHvxix=xHvxEix （9.13） 现在， x为最优解O(RS)的概率为Eix。这一事件一旦发生，约束条件d一定在R中，R中剩余的r-d条约束一定是HS中的m-vx-d条约束。m-vx-d条约束既没有被x定义也没有被x侵犯。因此 Eix= m-vx-dr-dmr （9.14）练习9.25：将（9.13）和（9.14）结合，并简洁化，得到如下所示 EVm-r+1r-dxHvx m-vx-dr-dmr （9.15） 我们将会通过计算公式（9.15）右边的求和结果不超过d来完成证明。R中的元素x恰巧侵犯R中的一个约束可能性为m-vx-dr-d/mr。通过vx给它加权，对R中恰巧违反R中一个约束的元素的期望数进行求和。然而这种元素的数量最多为d，因为每一个这样的元素是RSh集中的最优解，RSh是指在h约束下的最优解O(RS)。这有d条约束定义了最优集O(RS)。随着这种违反约束的期望数目的绑定，马尔科夫不等式在SampLP中揭示了任何随机抽样，Pr|V|2n1/2。它遵循在2.2步骤中扩增到S的迭代的期望数目最多为2。让T(n)表示SampLP中最大期望运行时间。S最初为空集，在d阶段中的每一阶段，最多增加2n个约束。因此，| RS |从来不超过3dn。因为在每一阶段，我们最多执行n个违反约束的测试，每次测试的成本为O（d）；因此在约束检测中的总的工作为O（d2n）。当在一个递归访问中，约束的数目下降到9d2或者更少，我们把时间绑定到单纯形（9.14）的访问中。将这些观察结果结合在一起，我们有T(n) 2dT(3dn)+O(d2n), n9d2 (9.16)练习9.26：在(9.16)中获得绑定T(n)的最大的可能性，与引理9.14互相协调。我们现在开始描述IterSampLP算法。而不是一点点发现H，在抽样中使用权值迭代技术来增加包括有用约束的可能性。我们选择约束R的一个随机子集，并且确定约束子集VH，这一子集违反了由R定义的线性规划的最优集。在SampLP中我们把V添加到集合S中，在这里，约束集V被选入未来循环的可能性的首次增加后，我们把V返回到H中。直觉上来说，在集合V中H的约束会不断的发现其本身，因此他们被包含在R中的可能性会迅速的增加。像这样有限的几次迭代后，H中所有的约束都有可能在R中，然后终止执行。下面是IterSampLP的详细描述，我们将会给每一个约束h赋予一个正的整数值wh,hH；约束h将会根据wh的现值按一定比例放入R中。在2.2步骤，约束h被选择的可能性按一定比例赋给wh。我们转向IterSampLP的分析。如果 hVwh(2hHwh)/(9d-1)成立，访问循环语句的一个执行（因此，对于每一个hV，将wh加倍）IterSampLP算法：输入：约束集H。输出：最优集H。1. hH, 令wh1；2. 如果n0 随机选择RH，|R|=r=9d2; x单纯形（R）; VhH|x不符合h； 如果hVwh(2hHwh)/(9d-1)那么 hH, 令wh2wh；2.3. 返回 x引理9.16 ：成功迭代中循环迭代的期望值最多为2。我们不能直接调用引理9.15的结论来分析IterSampLP，因为随机约束子集R不会等概率的被选择。引理9.16是引理9.15分析的一个扩展；读者可以根据问题9.9中的提示来完成证明。定理9.17： 存在连续的c1，c2，c3，IterSampLP期望的运行时间最多为 c1d2nlogn+c2dlogndd2+c3.证明：我们将会证明循环语句执行的期望值为O（dlogn）。思路是hHwh增长的比hHwh增长的要快，因此在dlogn次迭代后，V=除非hHwhhHwh,否则就会相矛盾。在每次循环成功，至少有一个约束h的权值加倍。成功执行循环kd之后，我们有hHwh=hH2nh, 其中nh为h进入V的次数。很显然hHnhkd。这些事实一起表明： hHwhd2k (9.17)另一方面，在每次成功执行循环语句后hHwh增加的网络不会超过2hHwh/(9d-1)。初始化hHwh=n。成功执行kd次迭代后它不会超过 N1+2/(9d-1)kdnexp2kd/9d-1 (9.18)将(9.17)和(9.18)相比较，在经过O（dlogn）次迭代后，我们跳出循环。在循环语句的成功迭代时，我们要花费多长时间？通过引理9.16，成功迭代数中期望迭代数目为2。在每次迭代期间，产生了单纯形访问的成本，在时间O（nd）中确定V。把这些因素一起放在定理中。9.10.1 递增的线性规划到目前为止，我们学习的线性规划都是基于随机抽样的。现在我们为线性规划开发随机递增的算法。下面的算法会立刻证明它本身：随机的添加n条约束，一次增加一个。目前为止，每增加一条约束，就会增加约束的最优集。这种算法可能被认为是在后退，但在续集中它会被证明是有用的。seideLP算法：输入：约束集H。输出：由H定义的LP的最优集。0. 如果|，输出H=H。1. 随机选择约束hH；2. 递归地发现Hh;2.1. 如果Hh没有违反h，向最优集H输出Hh；2.2. 否则把所有的约束Hh投射到h并且依次解决这个新的线性规划问题； 算法思想是简单的。H或者是冗余的，或者不是。在后面的例子中，我们知道由H形成的点一定位于边界h上。在这个例子中，我们把所有的约束集Hh映射到h上，然后解决了这个新的线性规划问题。当约束集的数目降到d，SeideLP停止循环。由于在H中至多，随机选择的约束h是我们所搜寻的极端约束之一的可能性最多为d/n。在d维空间中对于任何n个约束，让Tn,d表示算法的期望运行时间的上限。然后我们可以写Tn,dTn-1,d+O(d)+dnOdn+Tn-1,d-1. (9.19)在(9.19)中，右边的第一部分依次表示解决由约束集Hh定义的线性规划问题的成本。第二部分表示检查h是否违反Hh的检查成本。概率为dn，括号中的第一部分，表示映射到所有约束集h的成本。第二部分表示解决投影问题的成本，它有很少的约束和维度。下面的定理通过替代方法可以进行验证，通过直觉来进行证明。定理9.18：像循环(9.19)中一样，这有一个连续的b满足方法Tn,dbnd!。以上的递增算法有可能会变慢，除非d相当小。读者可能会问为什么，当在2.2步骤中解决d-1维的问题时，我们完全放弃了从线性规划Hh的方法中获得任何信息。我们现在进行到一个更复杂的算法，这个算法很仔细的保留了这些信息。在这样做之前，下面的练习会强化一下读者的直觉。练习9.27：考虑到算法SeideLP。构造一个例子来说明由约束集Hhh定义的线性规划的最优集有可能不同于由H定义的线性规划的最优集。因此，如果在步骤2.1中的测试失败，我们将会进行步骤2.2，它不能单独考虑约束集Hhh。 通过上面的练习，告诉我们在SeideLP的步骤2.2中，我们必须再一次的考虑在H中的所有的约束集。然而对于我们所希望的Hh实际上会包含H中的许多约束。我们可以用某种方式跳出SeideLP中的步骤2.2吗？这个想法的结果是算法BasisLP，这一算法会调用两个参数，一个约束集GH，一个基础TG。BasisLP返回基础G。BasisLP算法：输入：G，T。输出：对G的一个基础B。0. 如果G=T，输出T；1. 随机选一个约束集hGT;T=BasisLP(Gh,T);2.1. 如果h没有违反T，输出T；2.2. 否则输出BasisLP(G,Basis(Th);对于d+1集或者更少的约束函数Basis返回一个基础，如果这个基础存在的话。在我们的算法里，在给定的带有d个约束集的基础T上，我们通常调用Basis。通过计算h和T中的每个子集的交集，子集的基数为d-1,和在d个点上估算O，我们可以确定Basis(Th)。练习9.28：展示以上关于Basis的描述，在步骤O(d4)停止。练习9.29：通常BasisLP需要一个基础T作为输入之一。假设算法最初是以一个合适的基础开始的，以便在算法完成时，我们可以有最优集O(H)。每一个Basis调用都会先于一个违反集。在我们下面的分析中我们将会在整个运行时间里绑定测试集的数目并且从这推断出一个和Basis调用的数目有关的绑定。在给定的BasisLP执行中违反测试失败的可能性是什么？假设|G|=i。我们重新定义了一个约束hGT,它是随机选择的，并且希望能够和h违反最优集Gh的可能性进行绑定。很明显这个最多为d/(i-|T|)，因此G确定的(G)的约束最多为d并且h等可能的成为GT中i-|T|的任何一个约束。现在我们重新定义有关可能性的估计。感觉上来说如果T包含(G)中的一些约束，可能性会进一步降低；实际上，这是我们重新定义SeideLP来获得BasisLP的动机。最后，我们来介绍一些额外的概念。给定TGH，如果O(Gh)O(T),在(G,T)中我们将会执行访问一个约束。这一点在图9.12中将会被说明。在这个图中，有四个约束集，编号1,2,3和4。每个约束划定一个线组成一个可行域。很明显约束1和4是对于集合1,2,3,4的极端约束。考虑到BasisLP视图的时刻扮演相反的，并且在这种环境中约束被加入到序列1,2,3,4。观察说明在G=1,2,3,4和T=1,2时约束1没在G,T中执行。图9.12：极端和执行约束练习9.30：如果在序列4,3,2,1追踪访问BasisLP的过程中的约束被删除掉，就决定了各种递归访问的参数。如果删除约束的顺序为1,4,3,2，重复这一操作。练习9.31：如果在(H,T)中执行h，说明(i)hT，并且(ii)在所有的G中h是极值，比如TGH。如果所有的d约束都在(G,T)中执行，我们有T=(G)。在给定的TGH中，让G,T表示隐藏的维度(G,T)。约束集(G)的数目已经不在T中了。从以上的讨论可知，违反发生在if声明的可能性可以和G,T/(i-|T|)绑定在一起。我们首先会建立在步骤2.2的递归访问中隐藏的维度至少要下降1；以后，由于它可能降得更快，我们将会改善它。练习9.32：让TGH，让hFT成为F中的极端约束。让S成为(Fh)h