最优化 9 内点法

《最优化 9 内点法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内点法椭球法第一个可以在多項式时间內解决一般线性规划问题的解法。TmincxmaxbwT()Pst..Axb()Dst..Awcx0w0根据(P)与(D)的对偶关系,我们可将两者的最优解以一组最优性条件联结起来:Axb,x0TAwc,w0(*)cxwb0定理：存在求解LP问题的多项式时间算法的充要条件是存在求解线性不等式组Axb的多项式时间算法。证明：与线性不等式组Axb相关的LP问题为mincx*st..Axbx0x其中x,AAAb,bxx,,0,c任取如

2、c0x若有多项式时间的LP算法，能够判断问题*不可行，则不等式组Axb无解；或者得到其最优解或判定问题无界，则得到不等式组Axb的一个解，显然就以多项式时间解决了问题Axb。定理：存在求解LP问题的多项式时间算法的充要条件是存在求解线性不等式组Axb的多项式时间算法。maxwb*的对偶问题为st..wAcw0所以求解LP问题可归结为求解关于变量xw,的线性不等式组：AxbwA,ccx,wb0,,xw0设有多项式时间方法求解线性不等式组。若该联立不等式组有解xw*,*，则x*是LP问题的最优解，w*是

3、其对偶问题的最优解；若该联立不等式组无解，考虑不等式组Axbx,0若它有解，则LP问题无界；否则LP问题不可行。只要能有效的解决最优性条件的线性不等式,就能夠同时的解决一个线性规划问题(P)以及它的对偶问题(D)。椭球法正是一种专门解决线性不等式的方法。介绍如何以椭球法來解一组线性不等式Mu≤vMu≤v的解集合是一个凸集：S{

4、uMuv}假设S≠Ø,以原点u1为圆心,足夠大的半径做一圆E1,使得S∩E1≠Ø。11若Muv，则u为所求的解。否则,因为S∩E1是一个凸集,所以经过圆心,可以切掉不含S∩E1的半个圆,而只剩下包含S∩E1的半个圆(以1/2E

5、1表示)。对1/2E1而言,可以做出一个最小的椭圆E2,使得1/2E1⊆E2，椭圆的圆心记u2。S∩E1⊆E2,若Mu2≤v成立,则u2∈S∩E1必为其解。否则经过u2又可切去半个E2,而使S∩E1包含在另一半椭圆1/2E2之中。在p维空间中,每次做出的椭球体积都会逐渐缩小。以V(Ek)及V(Ek+1)来表示前后两个椭球的体积,那么可以证明V(Ek+1)

6、m的空间中,以原点u1=(x1,w1)为心,足夠大的正数22L为半径做一圆球E1。置k=1。2:检验现有球心uk=(xk,wk)是否满足该最优化不等式。若满足,则xk是(P)的最优解,wk是(D)的最优解。若不满足,则依前述方法得到一个新的椭球Ek+1及其球心uk+1。3:若是V(Ek+1)=0,uk+1仍不满足最优化不等式,則(P)或(D)至少有一无最优解。否则置k:=k+1,返回2。内点法Tmincx()Pst..Axbx0称x∈Rn为一个可行內点(interiorfeasible)如果Ax=b,x>0。可行內点解集合：F0={x∈Rn

7、Ax

8、=b,x>0}。假设F0非空。內点法可粗略的分为三个步骤:步骤一:找一个可行內点x1∈F0。置k=1。步骤二:决定现有解xk是否为(P)的最优解。若是,则输出x∗=xk。否则就寻找一个好的移动方向k,dx以及适当的步长k>0。k步骤三：由x移动到新的内点k1kk0xxdF.kx置k:k1，返回步骤二。PrimalAffineScaling内点法假想(P)的可行解集合位于第一象限的一个球,而现行解xk落在球心上,此球的半径是r>0。Tmincx()Pn21k2st..xjxjrj1最优解为：k1kcx*xxrc将

9、(P1)变得稍微复杂一些,将球改为第一象限来考虑下列问题:Tmincx()P2st..x0k假设x0，定义nn矩阵1kkx1x11k00x21kDDxk2kk0xn10kxn定义映射：nnT:RRk1xyTx()Dx则kk1nnT:RRk1yxT()yDykkkk1kyTx()Dxekk1kT()eDexkk在上述转化之下,(P2)的近似问题在y空间中就可写成:TmincDyk()Pn22st..yj1

10、1j1应用(P1)的解答技巧,在y