求解LP问题 | 一种多项式复杂度的解法：椭圆算法

照例先引用两篇文章：
第一篇关于椭圆算法的思路与简单步骤：The Ellipsoid Algorithm for Linear Programming
第二篇关于此算法中重要的一个步骤：Separation Oracles

相比单纯性算法，此算法巧妙的地方在于其控制了复杂度。虽然实际操作中可能没有单纯形好用，但是它提供了一种LP问题的多项式复杂度解法，借此可以引出更多更简单的多项式复杂度解。因此学习的时候要注意理论推导。建议学习时间为1小时。

基本定义与概念，

定义1 $R^{n}$ 中的超平面(Hyperplane)定义为集合 $H = \{x|a^{T}x=b\}$ 。其中 $a,x\in R^{n}$ ， $b\in R$ 。

这里书上定义一写错了，但是不妨碍理解。类比低维空间的直线和平面方程即可。
由于 $b$ 不一定等于0，因此超平面不一定过原点。
$R^{n}$ 中的超平面为一 $n-1$ 维流形。（这个性质可能跟我们要讨论的问题没什么关系）
“超”的意思是“在维度上做推广”。由于当 $n=3$ 时我们称定义1中所说的这种集合为“平面”，所以推广地说对于任意 $n \neq 3$ ，上边定义的集合就叫超平面。注意， $R^{2}$ 中的直线也是超平面。

定义2 $R^{n}$ 中的凸体(Convex body)定义为有界闭凸集。

凸集的定义和数学中是一样的。下面举几个例子：

线性规划问题的每一个限制条件（包括符号限制）都定义了一个超平面和两个半空间(Half-space)。半空间就是将 $R^{n}$ 用一个超平面一分为二所得到的集合。显然两个半空间以对应超平面为分界面。当限制条件分别为 $\leq$ ， $\geq$ 和=时，该限制条件对应的解空间为一个半空间（闭的）或超平面。
边长为 $l$ 的超立方体(Hypercube)： $B=\{x|0 \leq x_{i} \leq l , 1\leq i \leq n \}$ 显然为凸体。
一个椭球体（定轴的）为： $E = \{x| \sum^{n}_{i=1}\frac{x_{i}^{2}}{a^{2}_{i}}\leq 1 \}$ 。在本文中我们可以类比三维地考虑椭球体的集合意义。
$R^{n}$ 是一个平凡的凸集，但不是凸体。

下面是与椭圆算法相关的几个比较重要的结论：

解空间为半空间的交。满足一则限制条件的点集为半空间（或超平面。书上没有考虑等号限制条件，但是读者要意识到这一点即可。），故满足所有限制条件的点集为这些半空间的交。
有限个半空间的交为凸集。因为凸集的有限交仍然是凸集。
对于一个凸集 $K$ 与凸集外一点 $x$ ，存在超平面使得凸集与该点分居两侧。文章中是这样写的，但这样写显然是错的。二维欧式空间中的开单位圆盘与单位圆上任意一点构成反例。此性质要求凸集是闭的。

证明考虑 $x$ 到 $K$ 的距离，由于距离函数是连续的且在 $K$ 中可以取下届，故存在下确界。因此取一列 $K$ 中的点使得与 $x$ 的距离趋于下确界，由 $K$ 是闭集可知下确界可以取到，且不为0（否则与 $x$ 在 $K$ 外矛盾）。之后取中点构造垂直超平面即可。

这就引入了一种名为Separating Oracle的操作：

对于一个给定的点 $x$ ，其关于一个凸集 $K$ 的Separating Oracle操作为：要么说明 $x \in K$ （返回"YES"），要么返回"NO"加上一个分割 $x$ 与 $K$ 的超平面。

简单地说就是对于不在凸集中的点，找个超平面“切一刀”，把点和凸集分开。注意，“找一个超平面将该点和该凸集分开”与“找一个半空间覆盖住原来的凸集”是等价的。另一方面，这样的超平面的存在性已在上边有过证明。

算法

此算法分两部分理解。第一部分较为简单，即用二分法逼近最大值。第二部分用一种很巧妙的方法证明可解性（可解性用来判断二分法下一步往那边走），是本算法的关键。

第一部分：二分法

首先，我们使用二分搜索将求解最大值的过程转化为寻找可行解的过程。考虑

求最大值的近似解

不妨设最大值存在，记之为。当 $c_{0} > M$ 时上图方程（相当于比原LP问题多了一个限制条件的新LP问题）没有可行解。当时有可行解。
对于任意一个合适的初始，若上图中方程有解则考虑：若此时方程无解则最大值落在中。其他情况同理。
对于任意的误差，此方法（只考虑二分）的复杂度都为与矩阵大小无关的常数。

第二部分：判断可解性

对于一个给定的 $c_{0}$ ，现在只须判断上图中方程是否有解则可进行下一步。首先由之前的叙述可知可行域是一个凸集，记之为 $S$ 。

剩下好难，自己也没懂，不写了。