第五章-02投影梯度法

1、 可行方向法 & 投影梯度法（Feasible Direction Method & Gradient Projection Method）南京邮电大学理学院南京邮电大学理学院 2008-05-122008-05-12求解算法分类求解算法分类(1)将这种约束问题转化为无约束问题进行求解(因无约束问题已有较好的求解方法比如BFGS,DFP等)(2)直接从这种约束问题出发来求解数学模型数学模型min f(x)s.t. s1(x) 0sm(x) 0h1(x)=0hl(x)=01 1 知识回顾知识回顾起作用约束（有效约束）起作用约束（有效约束） 对容许点 来说，若有不等式约束si(x)

2、 0变成等式，即si( )=0,则该不等式约束称为关于容许点 的一个起作用约束；若si( )0则称之为这个容许点的不起作用约束。xxx则对点则对点(1,0)(1,0)T T来说来说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易见易见：不等式约束关于容许集的任意内点都是不起作用约束只有边界上的点才可能使得某个或某些不等式约束有效按照定义可见，任一等式约束关于容许点都是起作用约束任一等式约束关于容许点都是起作用约束容许方

3、向（可行方向）容许方向（可行方向） Rn中的一个非空点集D，xD，若对某个非0向量d，存在一个小正数，对t(0, ),总有x+td D（容许方向容许方向只与只与约束函数有关约束函数有关）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处的一个容许方向容许方向的判定定理容许方向的判定定理0*)(Ii 0*)(dxhdxsTiTi进一步，对于等式约束， hi(x)=0稍做等价变换:hi(x) 0, -hi(x) 0可得相

4、应结果。h hi i(x)(x)T Td=0d=0容许方向容许方向d d的数学表达式的数学表达式容许下降方向容许下降方向方向d既是点x处的容许方向，又是下降方向0*)(Ii 0*)(0*)(dxhdxsdxfTiTiT容许下降方向容许下降方向d d的数学表达式的数学表达式(1)如果某点x不是极小点，则继续寻优时的搜索方向就应该从该点的一个可行下降方向上去找（因为这样就既保证函数值的下降，又能确保找到的好点是一个可行的）(2)如果某点x*是一个极小点，则在该点就不会有容在该点就不会有容许下降方向许下降方向. .基本迭代格式基本迭代格式(i)从容许点x(0)开始迭代，设已迭代到x(k)(ii)在x

5、(k)处用某种方法确定一个下降容许方向d(k)(iii)在d(k)方向上寻找一个新的迭代点x(k+1)=x(k)+tkd(k),使得x(k+1)是容许点且f(x(k+1)f(x(k)(iv)判断终止？ (v)置k：=k+1，转(ii)可行方向法就是一种沿着下降容许方向搜索并保持新的迭代点为容许点的迭代算法。简要概述简要概述可行方向法是求解约束问题的一类方法,它一般从线性约束问题开始讨论,然后在推广到非线性约束问题上去,虽然理论上可行方向法对非线性约束问题有效,但实际使用时，一般不使用可行方向法,(一个重要的原因就是工作量太大)所以我们对于可行方向法的重点放在线性约束重点放在线性约束上。（对非线

6、性约束情形不作推广）2.2. ZoutendijkZoutendijk容许方向法容许方向法 (Feasible Direction) (Feasible Direction)min f(x)s.t. Axb Ex=eARmn,ERln,bRm,eRl,f:RnR1有一阶偏导数, ,bxAbxAbbbAAA使得定理定理x-则非0向量d为从点 出发的容许方向的充要条件： Ad0,Ed=0 设 是上述问题的一个容许点，适当调换A的行向量与b的相应分量成x-(2)利用这个性质，我们可通过解不等式组(1)利用这个性质，我们可通过解不等式组注注00EddA来计算线性约束问题的容许方向000EddAdxfT

7、)(来计算线性约束问题在点 的容许下降方向x)(),(,211100031 0 00 1 00 0 10 2- 1eEbA同时易得例 考虑问题 min x12+x1x2+2x22-6x1-2x2-12x3 s.t. x1+x2+x3=2 -x1+2x23 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就是一个容许方向(但未必是下降方向！)解例(自作) 考虑问题mi

8、n 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即为一个容许方向 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下降容许方向的进一步确定在所有的可行方向中x-找一个使得f( )Td最小的方向(即:使得f下降最多)x-

9、意即：min f( )Td s.t. Ad0 Ed=0(1)求一个下降容许方向就转化为一个子问题的求解，子问题是一个线性规划问题，可调用单纯形法求解.(2)这个子问题得到的将是一个无界解,需对这个问题加以修正.则td也满足此三式,t可无穷大x-d满足f( )Td0,Ad0,Ed=0由于我们关心的是确定d的方向，而不是具体长度所以，我们在上述问题中可加上对方向d的长度的限制从而得子问题x-minf( )Td s.t. Ad0 Ed=0 -1dj1，j=1:n因d=0是容许解且f( )T0=0 x-此子问题最优值必非正( )（* *）直线搜索直线搜索 从从x x(k)(k)出发，确定新的迭代点出发

10、，确定新的迭代点x x(k+1)(k+1) 。使得：。使得： (1) (1) 在下降容许方向在下降容许方向d d上目标函数值下降上目标函数值下降 (2) (2) 新的点新的点x x(k+1)(k+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其次：对现在所得的这个一元问题还可简化.不等

11、式约束分为两部分：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) 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)|

12、vjb”b”(iii)(iii)求解线性规划子问题求解线性规划子问题( (确定可行下降方向确定可行下降方向) ) min min f(xf(x(k)(k) )T Td d s.t. Ad0 s.t. Ad0 Ed=0 Ed=0 -1d -1dj j11，j=1:nj=1:n 得最优解设为得最优解设为d d(k)(k)ZoutendijkZoutendijk算法算法( (不完整不完整) )(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(

13、k)Td s.t. Ad0 Ed=0 -1dj1，j=1:n得最优解设为d(k)(iv)若| f(x(k)Td|,则x(k) 即为最优解，stop.(v)计算u=A”x(k)-b”,v=A”d(k)(vi)若v0,则作e.l.s.得x(k+1)=x(k)+tkd(k),置k:=k+1,转(ii)(vii)计算t=minui/(-vi)|vib”,EAN记 不妨设N行满秩(否则可直接去掉多余行),定义Q=I-NT(NNT)-1N,若Qf(x(k) 0,则 d= -Qf(x(k)是下降容许方向。设N有r行，易验证 QTQ=I-NT(NNT)-1NTI-NT(NNT)-1N=I-2 NT(NNT)-

14、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(k)|220可行： 只要验证Ad0,Ed=0,Nd=-NQ f(x(k) =-NI- NT(NNT)-1Nf(x(k)=-N-N f(x(k)=0ProofProof）对应于对应于EzAyzyq, (00zEyAxfzyEAxfTTkTk)()()()(即Q Qf(xf(x(k)(k) =0) =0的情况的情况Qf(x(k)=I- NT(NNT)-1Nf(x(k)= f(x(k)-

15、 NT(NNT)-1Nf(x(k)= f(x(k)- NTq=0 记 q=(NNT)-1Nf(x(k)对应于N可将q也加以分解这样上式就成为一般约束问题的最优性条件一般约束问题的最优性条件设x*为混合约束问题的一个极小点，函数f(x),s1(x),sm(x), h1(x), 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必非

16、负)Kuhn-TuckerKuhn-Tucker定理定理I=i|si(x*)=0,i=1:m但若y0,即y中有负分量比如yj(可能会有多个，任取一个)，这时将A中与yj相对应的那个行整个删去，仍记删去该行后的矩阵为N,用这个新的矩阵N构造Q，从而构造d，这时这个必为下降容许方向(不证)。从而,若y0的话,则上式就是K-T条件，从而知x(k)为KT点。else 0v|vumin-0 v iiit直线搜索直线搜索min f(x(k)+td) s.t. 0tt其中设得t*,则得新的迭代点x(k+1)=x(k)+t*d投影梯度算法投影梯度算法(i)取初始可行点x(0)，置k:=0(ii)在x(k)处将

17、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,则求解 min f(x(k)+td(k) s.t. 0tt 设得t*,则得新的迭代点x(k+1)=x(k)+t*d(k)置k:=k+1,转(ii)0012118221bAxxxf,1 00 110 151 ,)(例例min f(x)=x12+4x22s.t. x1+x21 15x1+10 x212 x1 0 x20解解取初始容许点x(0)=(

18、0,2)T,01211 010 151 1,bA01601 00 0001)(,)()()(xfQdNNNNIQTT取初始容许点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.011 01 10120 110 15 ,bAbA000 110 150 101 150 110 150 101 151 00 10 110 15111)()(,)(xfQdNNNNIQNTT从而第二次迭代：第二次迭代：x x(1)(1)x x(2)(2)在x