最优化 9 内点法.pdf

内点法 椭球法 第一个可以在多項式时间內解决一般线性规划问 题的解法。  T min cx maxb w   T (P) st.. Ax b (D) st.. A wc  x  0  w 0   根据(P) 与(D) 的对偶关系, 我们可将两者的最优解以 一组最优性条件联结起来: Ax b, x  0  T A w c, w  0 (*) cxwb 0  定理：存在求解LP问题的多项式时间算法的充要条件 是存在求解线性不等式组Ax b的多项式时间算法。 证明：与线性不等式组Ax b相关的LP问题为 min cx  * st.. Ax b     x  0  x    其中x ,A A A ,b b,x ,x  0,c任取 如c 0          x  若有多项式时间的LP算法，能够判断问题 *   不可行，则不等式组Ax b无解；或者得到其最优 解或判定问题无界，则得到不等式组Ax b的一个 解，显然就以多项式时间解决了问题Ax b。 定理：存在求解LP问题的多项式时间算法的充要条件 是存在求解线性不等式组Ax b的多项式时间算法。 max wb  * 的对偶问题为 st.. wAc     w 0  所以求解LP问题可归结为求解关于变量 x,w 的   线性不等式组：Ax b,wA ccx, wb  0,x,w  0 设有多项式时间方法求解线性不等式组。若该联立不 等式组有解 x*,w* ，则x*是LP问题的最优解，w*是其对   偶问题的最优解；若该联立不等式组无解，考虑不等式组 Ax b,x  0 若它有解，则LP问题无界；否则LP问题不可行。 只要能有效的解决最优性条件的线性不等式, 就能夠同时的解决一个线性规划问题(P) 以及它的 对偶问题(D) 。椭球法正是一种专门解决线性不等 式的方法。 介绍如何以椭球法