优化与分离的等价性(1)

优化与分离的等价性(The equivalence of optimization and separation)是凸优化中非常基本也是非常NB的一个定理。说基本是因为它告诉我们在一个凸集上做优化时,这个凸集的哪些信息真正需要的?说NB是因为我们所需要的信息时如此之少:我们不需要知道这个凸集的顶点,不需要知道它的形状,甚至我们不需要关于这个凸集的一个显式的描述,我们需要的只是以下这种能力:给定一个点,断言这个点在凸集内,或者找到一个超平面能够把这个点跟凸集分离开来。优化与分离的等价性揭示了凸优化的一些最本质的性质。

这个描述起来很简单的结果,其证明却涉及很多技术细节。本文只介绍证明的基本直观思路,这一结论的完整证明,公认最好的参考书是Grotschel, Lovasz和Shrijiver的Geometric Algorithms and Combinatorial Optimization。

本文分为两部分,第一部分介绍分离=>优化的证明,第二部分介绍优化=>分离的证明。

当然在证明之前,需要说明何为优化,何为分离,何为等价。这里假设K是我们要考虑的凸集。

这里的优化特指对线性目标函数的优化:给定c, 找出K里的一个x,使得对于K里的任何点y,都有c*x <= c*y。也就是说,我们要找到一个可行的x使线性目标函数c*x在K上最小。

所谓分离,是指对于任何给定的点x,我要么能正确地断言断言y在K里,否则,如果x不在K里的话,我能找到一个超平面,使x和K分别在超平面的两边。也就是说,我能找到这么一个c(超平面的法向量),使c*x <= c*y对于K里的所有y都成立。

所谓等价,指的是多项式时间上的等价:假如我有分离的能力,那么我只要进行多项式次的分离,就能完成优化的任务;反之亦然。

由于计算机上只能进行有限精度的计算,所以上面的优化和分离的等价都是在有限精度的意义上说的(亦即所谓的弱优化与弱分离)。具体而言,对有优化,我们不需要找到真正最优的那个x,而只需要“几乎最优”的那个x,也就是说,对于给定的误差e, 我们只需要找出K里的一个x,使得对于K里的任何点y,都有c*x <= c*y+e;对分离而言,我们只需要正确地断言x“几乎属于”K(x属于K或者x虽然在K外,但在K的边界附近一个厚度为e的“薄壳”内),或者找到一个超平面“几乎能分离”x和K(c*x <= c*y+e,对于K里的几乎所有y都成立,不成立的那些y都在K的边界附近一个厚度为e的“薄壳”内)。事实上,我们紧紧要求优化和分离只在有限精度上成立,是这一结果能得到证明的关键—-如果我们要求的是严格的优化和分离,我们反而无法证明我们的结论。

分离=>优化

如果我们具有分离的能力,如果能够利用这种能力去优化呢。证明最NB但也是最不直观的地方在我们能利用分离的能力来设计一种所谓椭圆算法(“Ellipsoid Algorithm”),利用椭圆算法,我们能把我们分离的能力转化为判断K中是否存在一个点x使c*x小于一个给定的值的能力。有了后面这种能力,利用二分法我们很容易就能(近似地)最小化c*x的点。

椭圆算法是如此之牛B,值得专开一段讲讲它的历史地位和理论意义。众所周知,Dantzig同学在六十年代某次做作业的时候顺手发明了解线性规划的单纯型算法。单纯型算法至今仍然是线性规划的最有效的算法。但不幸的是,单纯性算法在最坏情况下是指数级的。(当然,这种最坏情况在实际中很少出现,如何衡量单纯型法在实际中的平均性能,是当前武林另一绝学Smoothed Anaysis所研究的内容)。七十年代末八十年代初,苏联和美国的数位牛人Shor, Yudin, Nemirovski发明了椭圆算法,并以此证明了分离和优化的多项式等价性。然后Karmarkar将椭圆算法修改应用到线性规划上,得到了历史上第一个线性规划的多项式算法,从而证明LP是在P中。这一系列结果是如此地重要,并且在当时是相当出乎意料,以至于竟然上了纽约时报等新闻媒体的头条,这对于一项纯理论纯学术的成果来说是空前绝后的。然而椭圆算法虽然理论上是多项式,在实际中却效率很低,这与理论上是指数级但实际中效率很高的单纯型法正好相反。这一理论与实际的不符合一直在内点法(Interior Point Method)出现后才部分地得以解决。后来Nemirovski和Nemhauser发明了多项数级的解一般凸优化的内点法,从而证明凸优化也在P内,乃为后话了。

言归正传,椭圆算法干的这么一件事情。给定一个凸集K,假设我们有对于K的分离能力(所谓separation oracle),那么椭圆算法能够找到K里面的一个点,或者断言K是空的。椭圆算法的做法是构造一系列椭圆,这些椭圆都包含了K,并且体积一个比一个小。最后的那个椭圆要么其中心在K内(这个中心就是我们要找的那个点),要么椭圆的体积是如此至小,使它里面不可能再包含一个凸集K了。椭圆算法成功的关键在于以下五点:(1)给定一个椭圆,我们调用separation oracle就能判断椭圆的中心是否在K里,如果不在的话,separation oracle能够给出一个(经过椭圆中心的)分离超平面,利用这个分离超平面,我们能显式地再构造一个新的椭圆,它依然包含K(事实上,它是包含原来椭圆被超平面切下来那一部分的最小椭圆,所谓的Lower-John Ellipsoid),并且这个新的椭圆的体积比原来椭圆要小;(2)我们能够证明前后两个椭圆体积缩小的比率是一个常数,所以椭圆的体积是指数级下降的,从而即使最初椭圆的体积是指数级的,我们的算法仍然只需要进行多项式级那么多步;关于椭圆体积的证明利用到det(A)的一些上下界结果;3)以上算法能开始的前提是我们知道包含K的第一个椭圆,所以“优化=分离”必须加一个前提:我们知道包含K的一个大椭圆;当然如果K是一个由线性不等式给定polytope,这就不成问题,因为我们就能直接从线性不等式的系数中估计数这个大椭圆;(4)我们必须知道我们我们最后椭圆的体积小到什么程度后我们能够停止;对于K是polytope的情况,我们再一次能够从其线性不等式中得到这个K体积的一个下界,如果椭圆的体积(记住这个椭圆包含了这个polytope)小于这个下界的话,说明这个polytope只可能是空的;对于一般的凸集K,我们没有这个下界,但由于我们要求的只是近似的优化,所以我们只需要保证最后的椭圆的体积小到能够满足精度的要求就行;(5)椭圆算法所有计算都是有限精度的(包括开方和除法运算),我们能够证明,只要精度足够的高,我们的结论仍然成立,关于这一点的证明是最技术的部分。

现在,给了我们separation orale,我们就能实现椭圆算法。注意到如果拥有关于K的separation oracle,我们也就拥有了关于K‘的separation oracle,其中K‘是K和一个半平面交集。为了判断K中是否存在x使c’x大于等于给定的值b,我们令K’等于K和{y|c*y>=b}的交集。利用K’的separation oracle,我们能够实现关于K’的椭圆算法,算法有两种可能的结果:(1)算法找到K’中的一个点x,根据定义, x就是K中使c*x>=b的点;(2)算法找到一个椭圆,这个椭圆包含K‘,并且体积很小。由于这个椭圆的体积很小,我们能够保证K’即使不是空,它里面的点x也都满足c*x<b-e,亦即近似不能满足c*x>=b,这种精度的近似对于我们来说已经足够了。

综上所述,给定一个目标函数系数c和一个目标函数的界b,我们能近似地判断K里的点是否都满足c*x>b(这样的话c*x的最小值就比b大),或者找出一个使c*x<b的x(这样c*x的最小值就比b小)。利用二分法我们就能以任意精度找到使c*x最小化的那个最优解x。这样我们证明了(近似)分离=>(近似)优化。

这里我们再次强调,要在K上进行优化,我们只需要K的separation oracle,以及知道包含K的一个椭圆,除此以外,我们不需要知道关于K的任何其他全局或者局部信息。K是凸集保证了分离超平面的存在性。以上证明的直观idea是,每次调用separation oracle,我们都使我们搜索可行解得范围缩小,并且是指数级地缩小,最后这个范围是是如此之小,使这范围里面的点都是近似最优。

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: