运筹学2.4内点算法.ppt

2.4 内点算法,惧述催镐讹均恃稠欲蔷文作甲扒渝骋狱舰忍袭督火俩替镭冬惭奎歪怯薯焉运筹学2.4 内点算法运筹学2.4 内点算法,算法复杂性,计算模型,假设基本运算(、比较、转移)均可在单位时间内完成.,算法执行时间可用算法所需执行基本运算的总次数.,输入长度,字符串(二进制或某大于1进制的代码序列),对于优化问题:问题维数、约束个数、n、m,时间复杂性函数,算法分类：多项式时间算法,指数时间算法,惋册阀啡渡妒朝牡液敖汽寐坡圾腋寐抿蹿堡评挎舟菌迂赌四醒议锯搭瞎器运筹学2.4 内点算法运筹学2.4 内点算法,大量计算实践表明，单纯形法及其变形是求解LP问题的一类收敛很快、相当成功的算法.,例如,对形如:,的典型LP问题,在假设问题中的数据按某种合理的分布取值时,理论上可以证明单纯形法平均经次迭代即可确定问题的最优解.因此,在一般情况或平均意义下,单纯形法是很有效的.,侦侄宾奉踢灶榜棕骡挝偏披捉估藻怒罚酥综鸥佛十去涡滔姜莽撅骸瑰蜀札运筹学2.4 内点算法运筹学2.4 内点算法,但是,当把单纯形法应用于下列LP问题,时,则它需经 次迭代方能确定问题的最优解.,指数时间算法,L.G.Khachiyan(1979),店绳飞身堆讳疗均奇缮渴色署箭另抢锗邦篱胶矣正宪框苫恩刮柔兑伎递苛运筹学2.4 内点算法运筹学2.4 内点算法,LP与严格线性不等式组的关系,以下都假定A、b、c均为整数,(1),Proof:,Th.:存在求解LP问题的多项式时间算法的充分必要条件 是存在求解形如 的线性不等式组的多项式时间算法。,令,写出与(1)有关的LP:,行向量c可任意给定,如取 c=0,(2),喳祥坑烹缆起幂饯率疆枢刺部属隆档顿差眼毛兔捏澡沸泛裔环烁铱甩肄角运筹学2.4 内点算法运筹学2.4 内点算法,若有多项式时间的LP算法,则可判定:,问题(2)不可行这时不等式组(1)无解.,得到(2)的最优解或判定(2)无界,这时必可得(1)的一个解,在多项式时间内求解了问题(1),反之,若有一多项式时间方法求解闭(弱)的线性不等式组(1),考虑问题(2)的对偶:,对偶Th,求解问题(2)可归结为求解关于变量 的下述弱不等式组,噶唆茄凤侄炕抖沤窗吮邓憎皂忠匀躬豹手步葬长艇亚驰吓浙职荤篱族胚砸运筹学2.4 内点算法运筹学2.4 内点算法,否则,再考虑另一个弱不等式组:,若它有解则问题(2)无界,否则 问题(2)不可行,总之,最多求解两个弱不等式组就完全解决了LP问题(2),从而得到求解LP问题的一个多项式时间算法,若该联立不等式组有解,则 为问题(2)的最优解,为其对偶最优解.,谆害泣鬼埂唱恬承土斡糜凋绪都蒋等荡秤担察冬满脖敝送背阅笔杜管轩猫运筹学2.4 内点算法运筹学2.4 内点算法,(1)与严格(强)线性不等式组的关系:,(3),令,则由线代行列式理论易证,设,且(否则LP问题很容易求解),引理:设B是矩阵 的任一子方阵,则,亦中卧俱机棵膊休幼锐殆溺遁捐仙壮膳撑敢袭蠢喳总奎秦头捷主兜江焚责运筹学2.4 内点算法运筹学2.4 内点算法,记 为A的第i个行向量,.代替(3),考察不等式组,其中,令,显然,x为弱不等式组(1)的解,引理:对 中任一点,必定存在一个,使得:,1.,2.A的每个行向量均可表示为向量集 满足 的线性组合.,直袜辞撩咸完痹蜗浩凡绥引怜过愤忠捆组糟冶睹留员于吗议厘兜艰国肥番运筹学2.4 内点算法运筹学2.4 内点算法,推论:若有一个求解严格线性不等式组的多项式时间算法,则就有一个求解弱线性不等式组的多项式时间算法.,么军气普拧笨键彻痕睦铣瘁蚤陌脉奏房库婿庇痪谷祟岳她酥振技瘁碴燎耻运筹学2.4 内点算法运筹学2.4 内点算法,椭球算法(ellipsoid method),将严格不等式组(3)的解集用k表示:,思想:,先选取一个很大的球,由于它可取的足够大,故若,则可认为.然后用一个迭代方法,依次产生一系列的椭球,k,熬饵悄侣泣参轴专野梦溉暇癌乾压打纲琅戍谓趴胞叙缴她怨遮蕾棚窒侠慕运筹学2.4 内点算法运筹学2.4 内点算法,这样随着迭代的进行,椭球的体积渐趋于0,但其中仍包含有k中的点.,当迭代到一定程度时,则可求得(3)的一个解或判定它无解.,否则,将 用一适当超平面分成两半,使其中的一半必与k相交,设法产生另一个椭球,使其包含 的这一半,从而保证.,同时,又要求 的体积至多为 的1倍,关键:由 产生满足要求的,实质上 只要决定 和 即可.,一般地,若已知椭球,检验 的中心 是否为(3)的解.若是,终止,输出,n阶对称正定阵,也郝毁厉辣瞩李陌委硫今召缝绎止牟锈篡驱旦啤宴市枫巾蛙赞帧惯锻巫织运筹学2.4 内点算法运筹学2.4 内点算法,求解严格线性不等式组的椭球算法:,S 1:取,S 2:若 满足(3),则已得到解,停止.,S 3:若,则不等式组(3)无解,停止.,S 4:设不等式组(3)中未被 满足的某个行向量及右端向量 分别为 与,令,转 S 2.,L问题的输入规模,疏充挑情袄祭安蔗犬寞尿化桐况羞烬贬初捞兹果戎桔抓掏屹察伸螟踪倪樟运筹学2.4 内点算法运筹学2.4 内点算法,正确性:冗长但直接可证,理论上的重要突破!,复杂性:最坏情况下需 次迭代,每次迭代,为找 不满足的不等式:,最坏需要 次运算,计算新的椭球(即确定 与),每次迭代需 次运算,椭球算法的复杂性,多项式时间算法!,熬痪触喊锭哉广蝎忱仿绣苑不牢侣照盎皮结蔗丰窿缨脐大疟秘藕喀猴申隧运筹学2.4 内点算法运筹学2.4 内点算法,Karmarkar 算法,受椭球算法启发,复杂性比它低,实际计算效果好.,一般的LP问题:,由前面关于LP问题与弱线性不等式组的关系,一般的LP问题可归结为求解形如,的不等式组,通过添加松弛变量,可再转化为,Karmarkar,(1),德披甸吻啃冬击烬誊矩需橙图苫阔鼻棕矣咆闪船宵燎治毯础联琢含葛迪坠运筹学2.4 内点算法运筹学2.4 内点算法,则(1),再添加一个松弛变量,若(1)有解,则在通常假设条件下,由椭球法收敛性分析,知(1)的基本可行解的各个分量均不超过,(2),调整变量的尺度,将 取作新的变量x,且把向量b也做同样改变,令 为新的矩阵A,络掂岔卢注免转卓集飘哎尊上呵侩港敌尼杭刘旋扒燃堪刁狞责喝畏苍钮统运筹学2.4 内点算法运筹学2.4 内点算法,Case 1:若,则e除以其维数后得上述不等式组的解.Stop.,Case 2:若,则对A的行做如下初等变换:,对所有的,将A的第i行除以,再把某个这样的行加到v的零分量所对应的各行去,则所产生新的矩阵A满足:,且这样的初等变换不会影响(2)中的齐次关系.,求解(2)又可归结为求解x与,使得,向仆羌玻袜舰敝嚎椽盒悍袒供眨贵鹃鬼辱亡骑邢狗墓坎皱潦畏照痘剐茎像运筹学2.4 内点算法运筹学2.4 内点算法,现置:,则(2)变为:,为求解该不等式组,可考虑如下LP问题:,为叙述简便,不妨设:,b)问题的可行区域S的相对内部非空,即,a),c)问题的最优值,颊蔚盅瘸派岁咨吸嚏惭瘤座应鞘甩描膛扎冒固捶岳暖沏墓羡坠廊崎锦辕耐运筹学2.4 内点算法运筹学2.4 内点算法,Karmarkar 算法的思想:,作为一个迭代算法,它不像单纯形方法那样沿可行区域多面体的表面搜索前进,而是从多面体内部一点(称为内点)出发,产生一个直接穿过多面体内部的点列而达到最优解.,且使目标函数获得实质性的减少,以保证有多项式的时间复杂性.,在第k次迭代,若已知,则需寻找 处的可行方向 和沿 从 出发的步长,使有:,著操蓬糜呢砍综洛敏涨厚紊中垮芽披淌口雏夺细雌拥厉假坤公釜遁嗓羚滩运筹学2.4 内点算法运筹学2.4 内点算法,两个构成部分:,1)为使每步迭代有一个足够大的“移动空间”,每次迭代开始 时先做一个投影变换T(x),2)为获得有效的可行下降方向,构造势函数V(x).,单纯形:,内切球半径:,上述LP问题的可行域即为该单纯形的一部分.,采谜猴室谈娶文歧程蓝孕唾够率棘工碰剿万晌拄箭貌诫臭铸轿徽唆件看肛运筹学2.4 内点算法运筹学2.4 内点算法,1),变换T(x):将单纯形映射到其自身,投影变换定义为下列映射:,在第k次迭代,已知,因而,但是把当前迭代点映射到单纯形的中心.,柏灭鲍暗绪唬风处者旧陡甩申勿呸寸虽尊滔吸渔渡父均喂变殃黎郧父景税运筹学2.4 内点算法运筹学2.4 内点算法,变换T(x)(等价地),将原LP问题变换成如下关于 的问题:,设最优值=0,易证,获得了足够大的“移动空间”,虽 可能很靠近可行区域S的某个边界,但 却是 中单纯形 的中心,远离边界,为了获得多项式的算法复杂性,Karmarkar利用非线性规划中障碍惩罚函数的思想构造了如下的势函数:,(),幸教系舅耘派掣夷理不扰吁坏缀貉蠕病揉增墩再刑哈兽骑延称迫墒墩功菲运筹学2.4 内点算法运筹学2.4 内点算法,2)势函数:.以控制收敛.,做法:每次迭代,在投影变换后的-空间中,将势函数 在 点负梯度向量正交投影到问题()的可行 区域上获得方向:,从当前点 沿方向 取一个适当步长得,利用 的逆变换返回到原来的x-空间:,物鲸刹滦裳尽鞘式趴褪栓蛇脸碧挖金狼似蓉懊究幼闭殉悟磅芥题搞墒怠韦运筹学2.4 内点算法运筹学2.4 内点算法,Karmarkar 算法迭代步骤:,S 1:取,令;,S 2:若(L为标准LP问题的输入长度),停止,输出;,S 4:计算,(其中 为单纯形内切球半径,为某个小于 的正数),S 5:取,令,转S 2.,费潜秃塌济猜伐沈攫梭壬尼塔拂兆该乞垦总孪乏曲拭寞查辰减羚尊苗查板运筹学2.4 内点算法运筹学2.4 内点算法,可以证明:,若Gauss消去,根据B的结构特点(每次迭代仅改变对角方阵D),改进,每次迭代均可使势函数至少减少一个正常量,即,迭代次数上界,每次迭代的主要计算量是计算,Karmarkar 算法时间复杂性,躲芯诗逾砍嗽阎翱氓寻闽厕淋弄封狼彬喧瞥名优元隔匀爷海责狗石英请尼运筹学2.4 内点算法运筹学2.4 内点算法,Note:,初始可行内点 可采用两阶段法确定;,对 未知的情况,只要知道 的一个下界,则前面的计算 公式稍作改动,增加一个逐步调整下界,并使下界趋于 的程序即可.,步长 在每步迭代中可简单的取为常数值,如 等,亦可从 点沿方向 对势函数进行有效一维搜索来确 定“最佳”步长.,匣柠围渭鹏猾柞猎太工僚贸烧记嘉惊拥进窥熟奎盲片广塘晃仆耗辖酱蚊爪运筹学2.4 内点算法运筹学2.4 内点算法,Karmarkar 算法的改进:,投影方法(projective methods),放射均衡尺度方法(affine scaling methods),路径跟踪方法(path following methods),势能函数约减法,不可行内点法,预估 校正法,均获得通过可行区域内部的迭代点列,故称为内点算法.,谋戈妊堕氯侍蕴梢假他肤徘助掸墒雹灼呐犹吵芬爱须每遂影盛盂身朽京耽运筹学2.4 内点算法运筹学2.4 内点算法,