运筹学2.4 内点算法

§2.4

内点算法编辑ppt算法复杂性计算模型假设基本运算(﹢、﹣、×、÷、比较、转移)均可在单位时间内完成.算法执行时间可用算法所需执行基本运算的总次数.输入长度字符串(二进制或某大于1进制的代码序列)对于优化问题:问题维数、约束个数、n、m时间复杂性函数算法分类：多项式时间算法指数时间算法大量计算实践表明，单纯形法及其变形是求解LP问题的一类收敛很快、相当成功的算法.例如,对形如:的典型LP问题,在假设问题中的数据按某种合理的分布取值时,理论上可以证明单纯形法平均经次迭代即可确定问题的最优解.因此,在一般情况或平均意义下,单纯形法是很有效的.但是,当把单纯形法应用于下列LP问题时,则它需经次迭代方能确定问题的最优解.指数时间算法L.G.Khachiyan(1979)LP与严格线性不等式组的关系以下都假定A、b、c均为整数(1)Proof:

Th.

:

存在求解LP问题的多项式时间算法的充分必要条件是存在求解形如的线性不等式组的多项式时间算法。令,写出与(1)有关的LP:行向量c可任意给定,如取c=0(2)若有多项式时间的LP算法,则可判定:问题(2)不可行→这时不等式组(1)无解.得到(2)的最优解或判定(2)无界→这时必可得(1)的一个解

在多项式时间内求解了问题(1)反之,若有一多项式时间方法求解闭(弱)的线性不等式组(1)考虑问题(2)的对偶:对偶Th求解问题(2)可归结为求解关于变量的下述弱不等式组否则,再考虑另一个弱不等式组:若它有解→则问题(2)无界否则→问题(2)不可行总之,最多求解两个弱不等式组就完全解决了LP问题(2)从而得到求解LP问题的一个多项式时间算法若该联立不等式组有解则为问题(2)的最优解,为其对偶最优解.(1)与严格(强)线性不等式组的关系:(3)令则由线代行列式理论易证设,且(否则LP问题很容易求解)引理:

设B是矩阵的任一子方阵,则记为A的第i个行向量,.代替(3),考察不等式组其中令显然,x为弱不等式组(1)的解引理:对中任一点,必定存在一个,使得:1.

2.

A的每个行向量均可表示为向量集满足的线性组合.推论:

若有一个求解严格线性不等式组的多项式时间算法,则就有一个求解弱线性不等式组的多项式时间算法.Th.

:

弱不等式组(1)可行严格不等式组(3)可行椭球算法(ellipsoidmethod)将严格不等式组(3)的解集用k表示:思想:先选取一个很大的球,由于它可取的足够大,故若,则可认为.然后用一个迭代方法,依次产生一系列的椭球k这样随着迭代的进行,椭球的体积渐趋于0,但其中仍包含有k中的点.当迭代到一定程度时,则可求得(3)的一个解或判定它无解.否则,将用一适当超平面分成两半,使其中的一半必与k相交,设法产生另一个椭球,使其包含的这一半,从而保证.同时,又要求的体积至多为的β<1倍关键:由产生满足要求的,实质上只要决定和即可.一般地,若已知椭球检验的中心是否为(3)的解.若是,终止,输出n阶对称正定阵求解严格线性不等式组的椭球算法:S1:

取

S2:

若满足(3),则已得到解,停止.S3:若,则不等式组(3)无解,停止.S4:设不等式组(3)中未被满足的某个行向量及右端向量分别为与令,转S2.L—问题的输入规模正确性:冗长但直接可证理论上的重要突破!复杂性:最坏情况下需次迭代每次迭代,为找不满足的不等式:,最坏需要次运算计算新的椭球(即确定与)每次迭代需次运算椭球算法的复杂性

多项式时间算法!Karmarkar算法受椭球算法启发,复杂性比它低,实际计算效果好.一般的LP问题:由前面关于LP问题与弱线性不等式组的关系,一般的LP问题可归结为求解形如的不等式组,通过添加松弛变量,可再转化为Karmarkar已知求,使且(1)则(1)再添加一个松弛变量若(1)有解,则在通常假设条件下,由椭球法收敛性分析,知(1)的基本可行解的各个分量均不超过(2)调整变量的尺度,将取作新的变量x,且把向量b也做同样改变令为新的矩阵ACase1:若,则e除以其维数后得上述不等式组的解.Stop.Case2:若,则对A的行做如下初等变换:对所有的,将A的第i行除以,再把某个这样的行加到v的零分量所对应的各行去,则所产生新的矩阵A满足:且这样的初等变换不会影响(2)中的齐次关系.求解(2)又可归结为求解x与,使得现置:则(2)变为:为求解该不等式组,可考虑如下LP问题:为叙述简便,不妨设:b)

问题的可行区域S的相对内部非空,即a)

c)问题的最优值Karmarkar算法的思想:作为一个迭代算法,它不像单纯形方法那样沿可行区域多面体的表面搜索前进,而是从多面体内部一点(称为内点)出发,产生一个直接穿过多面体内部的点列而达到最优解.且使目标函数获得实质性的减少,以保证有多项式的时间复杂性.在第k次迭代,若已知,则需寻找处的可行方向和沿从出发的步长,使有:两个构成部分:1)为使每步迭代有一个足够大的“移动空间”,每次迭代开始时先做一个投影变换T(x)2)为获得有效的可行下降方向,构造势函数V(x).单纯形:内切球半径:上述LP问题的可行域即为该单纯形的一部分.1)变换T(x):将单纯形映射到其自身投影变换定义为下列映射:在第k次迭代,已知,因而但是把当前迭代点映射到单纯形的中心.变换T(x)(等价地),将原LP问题变换成如下关于的问题:∵设最优值=0易证获得了足够大的“移动空间”虽可能很靠近可行区域S的某个边界,但却是中单纯形的中心,远离边界为了获得多项式的算法复杂性,Karmarkar利用非线性规划中障碍惩罚函数的思想构造了如下的势函数:(△)2)势函数:.以控制收敛.做法:每次迭代,在投影变换后的--空间中,将势函数在点负梯度向量正交投影到问题(△)的可行区域上获得方向:从当前点沿方向取一个适当步长得利用的逆变换返回到原来的x--空间:Karmarkar算法迭代步骤:S1:取,令;S2:若(L为标准LP问题的输入长度),停止,输出;S3:令,计算投影方向;S4:计算(其中为单纯形内切球半径,为某个小于的正数)S5:取,令,转S2.可以证明:若Gauss消去根据B的结构特点(每次迭代仅改变对角方阵D)改进每次迭代均可使势函数至少减少一个正常量,即迭代次数上界每次迭代的主要计算量是计算Karmarkar算法时间复杂性Note:①初始可行内点可采用两阶段法确定;②对未知的情况,只要知道的一个下界,则前面的计算公式稍作改动,增加一个逐步调整下界,并使下界趋于的程序即可.③