运筹学2.4内点算法.ppt

《运筹学2.4内点算法.ppt》由会员分享，可在线阅读，更多相关《运筹学2.4内点算法.ppt（27页珍藏版）》请在第壹文秘上搜索。

1、 2.4 内点算法OR第二章 线性规划算法复杂性算法复杂性u计算模型计算模型 假设基本运算假设基本运算(、比较、转移、比较、转移)均可在均可在单位时间内完成单位时间内完成.算法执行时间可用算法所需执行基本运算的总次数算法执行时间可用算法所需执行基本运算的总次数.u输入长度输入长度字符串字符串(二进制或某大于二进制或某大于1进制的代码序列进制的代码序列)对于优化问题对于优化问题:问题维数、约束个数、问题维数、约束个数、n、mu时间复杂性函数时间复杂性函数算法分类算法分类：多项式时间算法多项式时间算法指数时间算法指数时间算法OR第二章 线性规划 大量计算实践表明，大量计算实践表明，单纯形法及其变形

2、是求解单纯形法及其变形是求解LP问题问题的一类收敛很快、相当成功的算法的一类收敛很快、相当成功的算法.例如例如,对形如对形如:Tmin,0c x Axb x的典型的典型LP问题问题,在在假设问题中的数据按某种合理的分布取值假设问题中的数据按某种合理的分布取值时时,理论上可以证明单纯形法平均经理论上可以证明单纯形法平均经次迭代即可确定问题的最优解次迭代即可确定问题的最优解.因此因此,在在一般情况一般情况或或平均意义平均意义下下,单纯形法是很有效的单纯形法是很有效的.111min,1,1228nmmnOR第二章 线性规划但是但是,当把单纯形法应用于下列当把单纯形法应用于下列LP问题问题 时时,则它

3、需经则它需经 次迭代方能确定问题的最优解次迭代方能确定问题的最优解.n21n-1n-212n-1n12123123nn-1n-2n123n-1n12nmin222s.t.54584522245,0 xxxxxxxxxxxxxxxx xx指数时间算法指数时间算法L.G.Khachiyan (1979)OR第二章 线性规划LP与严格线性不等式组的关系与严格线性不等式组的关系以下都假定以下都假定A、b、c均为整数均为整数(1)Proof:Th.:存在求解存在求解LP问题的多项式时间算法的充分必要条件问题的多项式时间算法的充分必要条件 是存在求解形如是存在求解形如 的线性不等式组的多项式时间算法的线性

4、不等式组的多项式时间算法。Axb令令 ,写出与写出与(1)有关的有关的LP:(,0)xxxxxmins.t.0cxAxbxxxAAAbbx 行向量行向量c可任意给定可任意给定,如取如取 c=0(2)OR第二章 线性规划若有多项式时间的若有多项式时间的LP算法算法,则可判定则可判定:l问题问题(2)不可行不可行这时不等式组这时不等式组(1)无解无解.l得到得到(2)的最优解的最优解l或判定或判定(2)无界无界这时必可得这时必可得(1)的一个解的一个解 在多项式在多项式时间内求解时间内求解了问题了问题(1)反之反之,若有一多项式时间方法求解闭若有一多项式时间方法求解闭(弱弱)的线性不等式组的线性不

5、等式组(1)考虑问题考虑问题(2)的对偶的对偶:maxs.t.0bAc,0,0AxbAc cxbx对偶对偶Th求解问题求解问题(2)可归结为求解关于可归结为求解关于变量变量 的下述弱不等式组的下述弱不等式组(,)xOR第二章 线性规划否则否则,再考虑另一个弱不等式组再考虑另一个弱不等式组:若它有解若它有解则问题则问题(2)无界无界 否则否则 问题问题(2)不可行不可行总之总之,最多求解两个弱不等式组就完全解决了最多求解两个弱不等式组就完全解决了LP问题问题(2)从而得到求解从而得到求解LP问题的一个多项式时间算法问题的一个多项式时间算法若该联立不等式组有解若该联立不等式组有解(,)x则则 为问

6、题为问题(2)的最优解的最优解,为其对偶最优解为其对偶最优解.x,0Axb xOR第二章 线性规划(1)与严格与严格(强强)线性不等式组的关系线性不等式组的关系:Axb(3)令令则由线代行列式理论易证则由线代行列式理论易证设设 ,且且 (否则否则LP问题很容易求解问题很容易求解)m n,2ARm n22ij2iiji1 loglog(1)log(1)mnab 引理引理:设设B是矩阵是矩阵 的任一子方阵的任一子方阵,则则,A I b2det()BnOR第二章 线性规划记记 为为A的第的第i个行向量个行向量,.代替代替(3),考察不等式组考察不等式组ia1im ii2a xb其中其中21lognn

7、 令令 iii,1Q xa xbim 显然显然,x为弱不等式组为弱不等式组(1)的解的解 i0,1Q xim 引理引理:对对 中任一点中任一点 ,必定存在一个必定存在一个 ,使得使得:n0RxnxR1.0iimax0,1Q xQ xim 2.A的每个行向量均可表示为向量集的每个行向量均可表示为向量集 满足满足 的线性组合的线性组合.ii0aiQ x ii221,1,a xbimOR第二章 线性规划推论推论:若有一个求解严格线性不等式组的多项式时间算法若有一个求解严格线性不等式组的多项式时间算法,则就有一个求解弱线性不等式组的多项式时间算法则就有一个求解弱线性不等式组的多项式时间算法.Th.:弱

8、不等式组弱不等式组(1)可行可行严格不等式组严格不等式组(3)可行可行OR第二章 线性规划椭球算法椭球算法(ellipsoid method)将严格不等式组将严格不等式组(3)的解集用的解集用k表示表示:思想思想:先选取一个很大的球先选取一个很大的球 ,由于它可取的足够大由于它可取的足够大,故若故若 ,则可认为则可认为 .然后用一个然后用一个迭代方法迭代方法,依次产生一依次产生一系列的椭球系列的椭球0Ek 0kE 12k,E EE0E1EOR第二章 线性规划 这样随着迭代的进行这样随着迭代的进行,椭球的体积渐趋于椭球的体积渐趋于0,但其中仍但其中仍包含有包含有k中的点中的点.当迭代到一定程度时

9、当迭代到一定程度时,则可求得则可求得(3)的一个解或判定它无解的一个解或判定它无解.否则否则,将将 用用一适当超平面分成两半一适当超平面分成两半,使其中的一半必与使其中的一半必与k相交相交,设法设法产生另一个椭球产生另一个椭球 ,使其包含使其包含 的这一半的这一半,从而保证从而保证 .kEk+1Ek+1kE kE同时同时,又要求又要求 的体积至多为的体积至多为 的的11倍倍k+1EkE关键关键:由由 产生满足要求的产生满足要求的 ,实质上实质上 只要决定只要决定 和和 即可即可.kEk+1k+1k+1,EE xBk+1k+1xB01E E一般地一般地,若已知椭球若已知椭球kkkk,B,kEE

10、xE 检验检验 的中心的中心 是否为是否为(3)的解的解.若是若是,终止终止,输出输出kkExkxTnk-1kkk1ExRxxBxxn阶对称正定阵阶对称正定阵kB OR第二章 线性规划求解严格线性不等式组的椭球算法求解严格线性不等式组的椭球算法:S 1:取取 L200(2)k0,0,nxBInS 2:若若 满足满足(3),则已得到解则已得到解,停止停止.kxS 3:若若 ,则不等式组则不等式组(3)无解无解,停止停止.k2(1)(3)3nnS 4:设不等式组设不等式组(3)中未被中未被 满足的某个行向量及右端向量满足的某个行向量及右端向量 分别为分别为 与与kxTTkjjjjab a xb令令

11、kjk+1kTjkjT2kjkjk+1k2Tjkj1n+1()()211B axxa B aB aB anBBnna B a,转转 S 2.k:k1L问题的输入规模问题的输入规模OR第二章 线性规划正确性正确性:冗长但直接可证冗长但直接可证 理论上的重要突破理论上的重要突破!复杂性复杂性:最坏情况下需最坏情况下需 次迭代次迭代16(1)n nL2()n L每次迭代每次迭代,为找为找 不满足的不等式不满足的不等式:,最坏需要最坏需要 次运算次运算kxTjkja xb()mn计算新的椭球计算新的椭球(即确定即确定 与与 )k+1k+1xB2()n每次迭代需每次迭代需 次运算次运算()n mn椭球算

12、法的复杂性椭球算法的复杂性3()n mn L 多项式时间算法多项式时间算法!OR第二章 线性规划Karmarkar 算法算法受椭球算法启发受椭球算法启发,复杂性比它低复杂性比它低,实际计算效果好实际计算效果好.一般的一般的LP问题问题:由前面关于由前面关于LP问题与弱线性不等式组的关系问题与弱线性不等式组的关系,一般的一般的LP问题可归结为求解形如问题可归结为求解形如的不等式组的不等式组,通过添加松弛变量通过添加松弛变量,可再转化为可再转化为KarmarkarTmins.t.0c xA xbx已知已知 求求 ,使使m nn,0,ARAexRTT0,0,1,0 xAxe xc x且且0,xAxb

13、0,xAxb(1)OR第二章 线性规划则则(1)再添加一个松弛变量再添加一个松弛变量 若若(1)有解有解,则在通常假设条件下则在通常假设条件下,由椭球法收敛性分析由椭球法收敛性分析,知知(1)的基本可行解的各个分量均不超过的基本可行解的各个分量均不超过2nT0,2xAxbe x(2)T0,2xAxbe x 调整变量的尺度调整变量的尺度,将将 取作新的变量取作新的变量x,且把向量且把向量b也做同样改变也做同样改变2xT0,1xAxbe xTT()0be xbAbex令令 为新的矩阵为新的矩阵ATAbeT0,0,1xAxe xOR第二章 线性规划Case 1:若若 ,则则e除以其维数后得上述不等式

14、组的解除以其维数后得上述不等式组的解.Stop.0Ae Case 2:若若 ,则对则对A的行做如下初等变换的行做如下初等变换:0Aev对所有的对所有的 ,将将A的第的第i行除以行除以 ,再把某个这样再把某个这样的行加到的行加到v的零分量所对应的各行去的零分量所对应的各行去,则所产生新则所产生新的矩阵的矩阵A满足满足:i0v ivAee且这样的初等变换不会影响且这样的初等变换不会影响(2)中的齐次关系中的齐次关系 .0Ax求解求解(2)又可归结为求解又可归结为求解x与与 ,使得使得1RT(,)0,0,1,0,0 xAxee xAee且OR第二章 线性规划现置现置:TTT(,),(,1)(0,0,

15、1)xxeecAeA则则(2)变为变为:TT0,0,1,00 xAxe xc xAe且为求解该不等式组为求解该不等式组,可考虑如下可考虑如下LP问题问题:TTmins.t.010zc xAxe xx为叙述简便为叙述简便,不妨设不妨设:b)问题的可行区域问题的可行区域S的相对内部非空的相对内部非空,即即a)m n(),;rank AmARc)问题的最优值问题的最优值0znT00,1,0SxRAxe xx T0011,xSnn且OR第二章 线性规划Karmarkar 算法的思想算法的思想:作为一个迭代算法作为一个迭代算法,它不像它不像单纯形方法那样沿可行区域多面单纯形方法那样沿可行区域多面体的表面

16、搜索前进体的表面搜索前进,而是从多面体而是从多面体内部一点内部一点(称为内点称为内点)出发出发,产生一产生一个直接穿过多面体内部的点列而个直接穿过多面体内部的点列而达到最优解达到最优解.0 x1xkxk+1xk+2xx且使目标函数获得实质性的减少且使目标函数获得实质性的减少,以保证有多项式的时间复以保证有多项式的时间复杂性杂性.在第在第k次迭代次迭代,若已知若已知 ,则需寻找则需寻找 处的可行方向处的可行方向 和沿和沿 从从 出发的步长出发的步长 ,使有使有:Tkkk1n0,xxxSkxkxkdkdkk+1kkk0 xxdSOR第二章 线性规划两个构成部分两个构成部分:1)为使每步迭代有一个足够大的为使每步迭代有一个足够大的“移动空间移动空间”,每次迭代开每次迭代开始始 时先做一个投影变换时先做一个投影变换T(x)2)为获得有效的可行下降方向为获得有效的可行下降方向,构造势函数构造势函数V(x).单纯形单纯形:nT1,0 xR e xxn1n,Ree中中以以为为顶顶点点的的单单纯纯形形内切球半径内切球半径:1(1)rn nT11:,nn中中心心上述上述LP问题的可行域即为该单纯形的一部