《投影梯度法精选课件.ppt》由会员分享，可在线阅读，更多相关《投影梯度法精选课件.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于投影梯度法关于投影梯度法第一页，本课件共有41页求解算法分类求解算法分类(1)将这种约束问题转化为无约束问题进行求解(因无约束问题已有较好的求解方法比如BFGS,DFP等)(2)直接从这种约束问题出发来求解数学模型数学模型min f(x)s.t.s1(x)0sm(x)0h1(x)=0hl(x)=0第二页，本课件共有41页1 1 知识回顾知识回顾起作用约束（有效约束）起作用约束（有效约束）对容许点 来说，若有不等式约束si(x)0变成等式，即si()=0,则该不等式约束称为关于容许点 的一个起作用约束；若si()0则称之为这个容许点的不起作用约束。xxx则对点则对点(1,0)(1,0)T T
2、来说来说1 1，4 4为有效约束，为有效约束，2 2，3 3为不起作用约束为不起作用约束ABx1x2P例例：某问题的约束函数分别为：s1(x)=1-x12-x22 0s2(x)=x1-x2 0s3(x)=x1 0s4(x)=x2 0易见易见：不等式约束关于容许集的任意内点都是不起作用约束只有边界上的点才可能使得某个或某些不等式约束有效按照定义可见，任一等式约束关于容许点都是起作用约束任一等式约束关于容许点都是起作用约束第三页，本课件共有41页容许方向（可行方向）容许方向（可行方向）Rn中的一个非空点集D，xD，若对某个非0向量d，存在一个小正数，对t(0,),总有x+td D（容许方向容许方向
3、只与约束函数有只与约束函数有关关）x设不等式约束问题不等式约束问题的可行域为D=x|si(x)0,i=1:mx为任一容许点,记I=i|si(x)=0,i=1:m当iI,si(x)在x处有一阶偏导数，且si(x)Td 0当iI,si(x)在x处连续,则d是x处的一个容许方向容许方向的判定定理容许方向的判定定理第四页，本课件共有41页进一步，对于等式约束，hi(x)=0稍做等价变换:hi(x)0,-hi(x)0可得相应结果。h hi i(x)(x)T Td=0d=0容许方向容许方向d d的数学表达式的数学表达式第五页，本课件共有41页容许下降方向容许下降方向方向d既是点x处的容许方向，又是下降方向
4、容许下降方向容许下降方向d d的数学表达式的数学表达式(1)如果某点x不是极小点，则继续寻优时的搜索方向就应该从该点的一个可行下降方向上去找（因为这样就既保证函数值的下降，又能确保找到的好点是一个可行的）(2)如果某点x*是一个极小点，则在该点就不会有容许在该点就不会有容许下降方向下降方向.第六页，本课件共有41页基本迭代格式基本迭代格式(i)从容许点x(0)开始迭代，设已迭代到x(k)(ii)在x(k)处用某种方法确定一个下降容许方向d(k)(iii)在d(k)方向上寻找一个新的迭代点x(k+1)=x(k)+tkd(k),使得x(k+1)是容许点且f(x(k+1)f(x(k)(iv)判断终止
5、？(v)置k：=k+1，转(ii)可行方向法就是一种沿着下降容许方向搜索并保持新的迭代点为容许点的迭代算法。第七页，本课件共有41页简要概述简要概述可行方向法是求解约束问题的一类方法,它一般从线性约束问题开始讨论,然后在推广到非线性约束问题上去,虽然理论上可行方向法对非线性约束问题有效,但实际使用时，一般不使用可行方向法,(一个重要的原因就是工作量太大)所以我们对于可行方向法的重点放在线性约束重点放在线性约束上。（对非线性约束情形不作推广）第八页，本课件共有41页2.2.ZoutendijkZoutendijk容许方向法容许方向法 (Feasible Direction)(Feasible D
6、irection)min f(x)s.t.Axb Ex=eARmn,ERln,bRm,eRl,f:RnR1有一阶偏导数第九页，本课件共有41页定理定理x-则非0向量d为从点 出发的容许方向的充要条件：Ad0,Ed=0 设 是上述问题的一个容许点，适当调换A的行向量与b的相应分量成x-第十页，本课件共有41页(2)利用这个性质，我们可通过解不等式组(1)利用这个性质，我们可通过解不等式组注注来计算线性约束问题的容许方向来计算线性约束问题在点 的容许下降方向第十一页，本课件共有41页例 考虑问题 min x12+x1x2+2x22-6x1-2x2-12x3 s.t.x1+x2+x3=2 -x1+2
7、x23 x1,x2,x30求出在点x(0)=(1,1,0)T处的一个可行方向。这个问题的不等式约束有四个，从而可写出在x(0)处可看出它的有效约束：A=(0,0,1),b=(0)解不等式：Ad0,Ed=00d1+0d2+1d3 0,1d1+1d2+1d3=0比如d=(1,-1,0)T就是一个容许方向(但未必是下降方向！)解第十二页，本课件共有41页例(自作)考虑问题min x12+x1x2+2x22-6x1-2x2-12x3 s.t.x1+x2+x3=2 -x1+2x2 3 x1,x2,x30求出在点x(0)=(1,1,0)T处的一个下降可行方向。解 Ad0,Ed=0得到的d即为一个容许方向
8、0d1+0d2+1d3 0,1d1+1d2+1d3=0再结合下降的要求 f(x(0)Td0即(-3,3,-12)d0即 -3d1+3d2-12d30从而由d3 0,d1+d2+d3=0 -d1+d2-4d30解出一个d即为下降可行方向比如(1,-1,0)T第十三页，本课件共有41页下降容许方向的进一步确定在所有的可行方向中x-找一个使得f()Td最小的方向(即:使得f下降最多)x-意即：min f()Td s.t.Ad0 Ed=0(1)求一个下降容许方向就转化为一个子问题的求解，子问题是一个线性规划问题，可调用单纯形法求解.(2)这个子问题得到的将是一个无界解,需对这个问题加以修正.则td也满
9、足此三式,t可无穷大x-d满足f()Td0,Ad0,Ed=0第十四页，本课件共有41页由于我们关心的是确定d的方向，而不是具体长度所以，我们在上述问题中可加上对方向d的长度的限制从而得子问题x-minf()Td s.t.Ad0 Ed=0 -1dj1，j=1:n因d=0是容许解且f()T0=0 x-此子问题最优值必非正()（*）第十五页，本课件共有41页直线搜索直线搜索 从从x x(k)(k)出发，确定新的迭代点出发，确定新的迭代点x x(k+1)(k+1)。使得：。使得：(1)(1)在下降容许方向在下降容许方向d d上目标函数值下降上目标函数值下降 (2)(2)新的点新的点x x(k+1)(k
10、+1)是一个容许点是一个容许点.这也就是这样的一个一元问题：min f(x(k)+td)s.t.A(x(k)+td)b E(x(k)+td)=e事实上这个问题还可以简化：首先，由x(k)是容许点，d是容许方向,知:E(x(k)+td)=e恒成立。故上述问题中的第二组等式约束可以直接去掉。min f(x(k)+td)s.t.A(x(k)+td)b其次：对现在所得的这个一元问题还可简化.不等式约束分为两部分：A(x(k)+td)b,A”(x(k)+td)b”由Ad0,Ax(k)=b知第一部分也可以直接去掉。从而得一个约束已大大减少的一元问题min f(x(k)+td)s.t.A”(x(k)+td)
11、b”分析：A”(x(k)+td)b”,即A”x(k)-b”-tA”d 设A”x(k)-b”=u=(u1,u)T,A”d=v=(v1,v)T,从而要u-tv 当v0时，显然问题变成min f(x（k）+td),对t无要求；当v 0不成立即v有分量0,而为使ui-tvi,i=1:都成立，就必须 tuj/(-vj),jj|vj0 也就是:令t=minuj/(-vj)|vjb”b”(iii)(iii)求解线性规划子问题求解线性规划子问题(确定可行下降方向确定可行下降方向)min f(x min f(x(k)(k)T Td d s.t.Ad0 s.t.Ad0 Ed=0 Ed=0 -1d -1dj j11
12、，j=1:nj=1:n 得最优解设为得最优解设为d d(k)(k)ZoutendijkZoutendijk算法算法(不完整不完整)第十七页，本课件共有41页(v)若v0,则作e.l.s.得x(k+1)=x(k)+tkd(k),置k:=k+1,转(ii)(vi)计算t=minui/(-vi)|vib”(iii)求解线性规划子问题以确定可行下降方向：min f(x(k)Td s.t.Ad0 Ed=0 -1dj1，j=1:n得最优解设为d(k)(iv)若|f(x(k)Td|,则x(k)即为最优解，stop.第二十页，本课件共有41页(v)计算u=A”x(k)-b”,v=A”d(k)(vi)若v0,则
13、作e.l.s.得x(k+1)=x(k)+tkd(k),置k:=k+1,转(ii)(vii)计算t=minui/(-vi)|vib”,记 不妨设N行满秩(否则可直接去掉多余行),定义Q=I-NT(NNT)-1N,若Qf(x(k)0,则 d=-Qf(x(k)是下降容许方向。设N有r行，第二十八页，本课件共有41页易验证 QTQ=I-NT(NNT)-1NTI-NT(NNT)-1N=I-2 NT(NNT)-1N+NT(NNT)-1N NT(NNT)-1N=I-2 NT(NNT)-1N+NT(NNT)-1N=I-NT(NNT)-1N=Q下降：f(x(k)Td=-f(x(k)TQf(x(k)=-|Qf(x
14、(k)|220可行：只要验证Ad0,Ed=0,Nd=-NQ f(x(k)=-NI-NT(NNT)-1Nf(x(k)=-N-N f(x(k)=0ProofProof第二十九页，本课件共有41页Qf(xQf(x(k)(k)=0)=0的情况的情况Qf(x(k)=I-NT(NNT)-1Nf(x(k)=f(x(k)-NT(NNT)-1Nf(x(k)=f(x(k)-NTq=0 记 q=(NNT)-1Nf(x(k)对应于N可将q也加以分解这样上式就成为第三十页，本课件共有41页一般约束问题的最优性条件一般约束问题的最优性条件设x*为混合约束问题的一个极小点，函数f(x),s1(x),sm(x),h1(x),
15、hl(x)在x*处都有一阶偏导数当h1(x*),hl(x*),si(x*)(iI)线性无关，则存在实数1,m,1,l使得f(x*)-1s1(x*)+2s2(x*)+msm(x*)-1h1(x*)+2h2(x*)+lhl(x*)=0isi(x*)=0,i=1:mi0,i=1:m(即j可正可负，但i必非负)Kuhn-TuckerKuhn-Tucker定理定理I=i|si(x*)=0,i=1:m第三十一页，本课件共有41页但若y0,即y中有负分量比如yj(可能会有多个，任取一个)，这时将A中与yj相对应的那个行整个删去，仍记删去该行后的矩阵为N,用这个新的矩阵N构造Q，从而构造d，这时这个必为下降容
16、许方向(不证)。从而,若y0的话,则上式就是K-T条件，从而知x(k)为KT点。第三十二页，本课件共有41页直线搜索直线搜索min f(x(k)+td)s.t.0tt其中设得t*,则得新的迭代点x(k+1)=x(k)+t*d第三十三页，本课件共有41页投影梯度算法投影梯度算法(i)取初始可行点x(0)，置k:=0(ii)在x(k)处将A，b分解(iii)构造N，从而构造Q(若N空的话，就取Q=I)(iv)计算d(k)=-Qf(x(k)(v)若d(k)=0,则计算q=(NNT)-1Nf(x(k)并相应分解为两块y,z 若y0,stop。否则，修正A，转(iii)(vi)若d(k)0,则求解 mi
17、n f(x(k)+td(k)s.t.0tt 设得t*,则得新的迭代点x(k+1)=x(k)+t*d(k)置k:=k+1,转(ii)第三十四页，本课件共有41页例例min f(x)=x12+4x22s.t.x1+x21 15x1+10 x212 x1 0 x20解解取初始容许点x(0)=(0,2)T,第三十五页，本课件共有41页取初始容许点x(0)=(0,2)T,第一次迭代：第一次迭代：x x(0)(0)x x(1)(1)在x0处A=(1 0),b=(0)从而N=(1 0)要先生成寻优方向d(0),先求解投影矩阵Qx(0)沿着方向d(0)作线性搜索，从而可得新点x(1)=(0,1.2)T.第三十
18、六页，本课件共有41页第二次迭代：第二次迭代：x x(1)(1)x x(2)(2)在x(1)处2,3约束有效：从而第三十七页，本课件共有41页计算其中第二个分量小于0，故删去A中对应的行，从而有新的A=(15 10),故有新的N=(15 10),x(1)沿着该方向作线性搜索可得新的点x(2)=(0.4,0.6)T第三十八页，本课件共有41页4.4.简简(既既)约梯度法约梯度法 Reduced GradientReduced Gradientmin f(x)s.t.Ax=b x0ARmn,mn,bRm,f:RnR1有一阶偏导数基本思想 利用约束条件将问题的某些变量用其它的变量来表示，从而达到降低维数的目的，然后构造可行下降方向作线性搜索逐步逼近问题的最优解。第三十九页，本课件共有41页函数的简约梯度设已得到可行解x，对约束Ax=b,将A分块A=(B,N),使得B为非奇异，相应地x分块从而有BxB+NxN=b,故xB=B-1b-B-1NxN将这个表达式代入目标函数，有这就得到一个降低了维数的以xN为自变量的函数F.第四十页，本课件共有41页感感谢谢大大家家观观看看第四十一页，本课件共有41页