18433 组合最优化.PDFVIP

18.433 组合最优化 椭球算法 Oct 30, Nov 4 授课教师：Santosh Vemp ala 1 求解线性规划的算法 1. 问题 给定一个多面体 ，记为 ，找一个 内的点。 处理这个问题之前，先给出一些定义。称一个实对称矩阵 是正定的，若对任意 有 成立。如果 是正定的，那么存在一个可逆矩阵 ，满足 。设 是一个正定矩阵，考虑椭球体 。令 表 1 示描述 的一个顶点所需的最大位数，并设 。用下面的方法来求解问题 ： 椭球算法 从椭球体 开始。 i 在第 步叠代中，检查 是否在 内。 - 是：输出 ，作为一个可行点。 - 否：在 的约束条件中找到一个 不满足的约束 ，把包含 的最小体积椭球体记为 ，递归。 1 图 ：算法的一个循环 当找到一个点在 i 内时，算法停止。它一定会停止，因为在任意的第 步， 是 的一个 子集，而且我们可以看出算法进行过程中 的体积是以一个可估计的速度在递降的。那 i 一定存在某个 使 的体积小于 的体积，所以算法会在达到这个值之前停止。在下一节 中我们来说明算法可以在多项式时间内完成。 2 时间限制 1. 的最小体积椭球体为 ，其 引理 包含 中 且 证明梗概：首先，注意 可以从 ( ) ，其中 单位球 中利用变换 得到。这一点用下面的式子说明： 其中第一个和最后一个分别是单位球和 的定义。 我们先对单位球 (1) (2) (1) 来证明结果 和 。在这种情况下， 式简化为 (2) 而 式则简化为 因为 是一个球，所以我们可以旋转 而没有任何影响。不妨假定 ， 那么 。 可以利用微积分得到 和 的简化形式。然后，利用一个从 到单位球的转换（上面的 det B ；这个转换用因子 （）改变了凸集的体积大小）就可以证明一般的情形。 (1) (2) (3) 有了 和 ，接下来我们证明 。注意到 E 仍然是包含 的一半的最小椭球体。 我们仍通过转换取 为球，转换后的 2 E 图 ：把 转换为球