约束优化常见算法

定义5・1设xwS为一可行点起若存在6>0,使对W[0,5]均有无+MW$则称d是可行域S在可行解兀处的可行方向，可行域S在可行解一兀处的所有可行方向记为FDOC),简记为FDO)定理5・1设x是问题(5.1)的可行解，在点无处有Axx=bpA2x>b2,其中则非零向量d为兀处的可行方向的充要条件是每〃20fEd=0oZoutendiik方法：如果非零向量d同时满足Vf(x)Td<0fAid20,Ed=0,贝临是在x处的下降可行方向。因此，Zoutendijk法把确定搜索方向归结为求解线性规划问题：minVf(x)Tds.tAjd20Ed=0IIdII1.(5.2)其中增加约束条件IIdII 1是为了获得一个有限解。在(5.2)中，显然d=0是可行解，因此最优目标值小于或等于零.如果Vf(x)Td<0,则得到下降可行方向弘如果最优值为零,则有如下结果.定理5・2考虑问题(5.1),设X是可行解，在点无处有A]X=6人2无>»2，其中B=biB=bi.^2则无为KuhmTucker点的充要条件是问题(5.2)的最优目标值为零。Rosen投影梯度法定义5.2设P为TI阶矩阵，若P=PT且P2=P,则称P为投影矩阵。定理53设兀是问题(5.1)的可行解，在点无处，有Alx=blfA2x>bl,其中B=biB=bi又设M=[I1]为行满秩矩阵，则P=IWT(MMT)TM是一个投影矩阵，且若PV/(%)=#0,贝忆=-PV/(%)是下降可行方向.定理5・4设兀是问题(5.1)的一个可行解,A1>A2,M的定义同定理5.3,且M为行满秩矩阵，令W= /(%)=[為其中u和卩分别对应于A】和E.若PV/(%)=0,贝IJ1如果u鼻0,那么无是K・T点；2如果u中含有负分量，不妨设Uj<0,这时从Al中去掉q对应的行,得到瓦，令・■M=Al,P=I-Mt(MMt)M-E-d=-PV/(%)那么d为下降可行方向。梯度投影法计算步骤给定给定初始可行点x（D,置k=lo在点x（k）处，将A和b分别分解成A「A2和b」2,使得A1X=bl,A2x>b2.3•令M=[I1]如果M是空的，令P=I（单位矩阵），否则令P=IWT（MMT）-iM・4•令d（k）=-P\7f（x（k））.若d（Q工0,则转步6;若d（k）=0,则进行步5•若M是空的，则停止计算，得到x（k）；否则，令W=（mmt）-1mv/（%）=[^]如果u20,则停止计算，x（k）为K・T点；如果u中包含负分量，贝IJ选择一个负分量，比如q,修正A-去掉A]中对应Uj的行，返回步3。根据式（5.4）计算入嗅，然后解下列问题，minf（x（k）+久d（k））S・t0W2W入max得步长入k，令X（k+D=x（k）+入kd（k）,置k:=k+1,返回步2Du&Zhang的修改1・给定给定初始可行点x⑴和一个正常数c>0,置k=lo2•在点x（k）处，将A和b分别分解成A],A2和b],b2,使得A、x=bpA2x>b2・3令如果M是空的，令P=I（单位矩阵），否则令P=I ・4计算W=（MMt）_1MV/（%）=[為和d（k）=-PVf（x（k））・定义1%,niinfiii|y=1,...,m}.女口果IIdkII=0且I%》0（或M是空的），则停止计算，x（k）为K・T点；若IIdkIIAiihC,dk不变，转下步；若IIdkII<-uhc,修正41,去掉A】中对应Uj的行，令dkJ—Pj\（K}gk,转下步.根据式（5・4）计算入max，然后用Amijo线搜索近似求解下列问题，minf（x（k）+/ld（k））得步长入k,令X（k+1）=x（k）+入kd®置k:=k+1,返回步2罚函数法对于等式约朿问题min/(%)s.t.Cj(%)=0J=1八・』.(5・6)可定义辅助函数Fl3O=0)+辺書Cj2(x)(5.7)参数CT是很大的正数。这样就能把(5.6)转化为无约朿问题min%(%,er)=f(x)+a甜c?(x)(5.8)显然，(5.8)的最优解必使得q(兀)接近零，因为如若不然，(5.7)的第2项将是很大的正数，现行点必不是极小点。由此可见，求解问题(5.8)能够得到问题(5.6)的近似解。罚函数的理论分析考虑min/(%)s.t.Cj(x)=0,iwE

Cj(%)20,iw/xwX其中X是非空闭集,E={l,・・・,nie},I=[me+1,・・・"}・定义S={xei^n|q(%)=0,ieE；q(%) 0,ie/}该问题对应的罚函数优化问题是：minF(x,cr)=/(%)+crP(x).且:xwS<=>P(x)=0,x丰S0P(X)>0定义：8(o)=inf{F(x,a)|xeX}引理5.1设X,S均是R"的非空子集,/(x),ci(x)(i=l,.-,m)^P(x)均在X上连续，并存在6>0,当6>6时，存在x§EX,使0(5)=F(xl5)(=f(x5)+8P(x6)),贝叭©inf{f(x)|x6SAX}>6^0(S)②f(x§)和9(5)=F(xs,5)是<7的增函数(毎％),P(Xa)是(7的减函数证明：®VxESnx,可推出f(x)二f(x)+8P(x)>0(8)②®>S2>80,所以f(®)+51P(xS1)<f(g)+®P(x§2)f(82)+82P(x62)<f(51)+82P(x1)(51一§2)P(X§J<(51一§2)P(X2)P(X&J<P(X2)0(S2)=f(62)+62p(x52)<f(®)+82P(X1)<0(80定理5.6假设同上述引理，贝h1若存在m<t彳&使p(x§)=o,则x§是代兀)在xqs上的全局最优点。2设XQSH0,若。2®时，集合｛x§|<72®｝包含在X的某个有界闭子集中，且x是集合｛x§|<t>80｝某个子序列的极限点，则无是代兀)在XAS上的全局最优点，且lim^+008P(x0)=0罚函数的数值实现一般策略是取一个趋向无穷大严格递增正数列｛§订，从某个％开始,对每个k,数值计算min/(x)+8kP(x),其中P(x)是罚函数,常取P(x)=殆(f(x)+器me+i[max｛0,-cKx)｝]?,从而得到一个极小点的序列｛Xk｝算法5・7外点法计算步骤(SUMT)步1・给定初始点x$,初始罚因子6>0,内精度序列｛%>oI/c=0,1,•••｝,且TkI0(/cf+8),外精度£>0,置kJ0o步2.以&为初始点，计算无约束优化问题n】in/(%)+瓦戸仗)得Xy使IIVF(xk)IIWTk且F(xJ8k)>F(xk,瓦)。步3•若8kP(x(k))<£,则停止计算，点x(k)为近似最优点；否则，取8k+l>8k(当kf+8时，应有+8)和新的xf+1+l使F(xf+h8k+l)WF(xk,8k+l)(通常令x；+l=xk),置k-fc+1,返回步2。定理5・8在上述算法中，取P(x)=工答Cj2(x)+y世me+i[max{0,-Ci(x)}]2,并设f(x),Cj(x)(i=1,…,m)均一阶连续可微，TkI0,nkT+8(k->+8),x*是算法产生的序列区}眾=i的一个聚点，VCj(x*)(ie/(%*)UE)线性无关，则疋是KKT点，且li叫t+88kCi(xk)=—入;/2,ieE；liniakniinfCj(x),0}k->+co其中入;(iw/(%*)UE)是对应的Lagrange乘子。内点法也称为障碍函数法，在迭代中总是从内点出发，并保持在可行域内搜索，只适合于不等式约束问题:minf(x)s.t.Cj(x)a0,i=1,...,(5.14)其可行域为：F={xE5Rn|Ci(x)M0,i=1,…,}其内点集合为：F°={x65R11|Cj(x)>0,i=1,••-,m}非空.算法5.9内点法计算步骤步1・给定初始内点x(0)eF。,初始参数口，缩小系数0>1,允许误差£>0,置k：=lo步2・以x(kT)为初始点，求解问题minG(x,)=/(%)+rkB(x)s.t.%丘F设其极小点为X(k)。步3.若rk5(x(k))<£,则停止计算，得到点x(k)；否则，令耳+1=/?rk,置k:=k+l,返回步2。Lagrange-Newton法考虑等式约束优化问题minxGRnf(x)(5.19)s.t.(x)=0.(5.20)其Lagrange函数是：L(x,A)=/(x)-ATc(x),x是一个K・T点当且仅当存在久W