最优化：可行方向法

最优化主讲：刘陶文课件制作：刘陶文唯楚有材於斯为盛学好最优化，走遍天下都不怕第十三章约束问题算法(II)——可行方向法一、Zoutendijk可行方向法二、投影梯度法三、既约梯度法思想点且单调下降列使得目标函数序构造可行点序列KKT,)}({}{kkkxxfxkkkkkkkdxxdx1,)((2);(1),产生新的可行点：计算步长受可行性限制通过线性搜索计算下降可行方向给定可行点其过程如下：.,),2()1(线性约束问题然后将其适当推广到非方向法题的可行我们先介绍线性约束问和考虑到算法第一节ZoutendijkEIixgiExIxAxDxEjxhIixgxDEjbxaxhIibxaxgtsxfijijTjjiTii}0,)(|{)()(,}0,)(;0,)(|{).(0,)(0,)(..)(min处的有效集为在记可行域考虑线性约束问题线性约束情形一.1、下降可行方向0)(},0);(,0|{)(,,)1.13(dxfxEjdaxIidaRdxSxDxTTjTin向满足：处的目标函数的下降方而在处的可行方向集在的约束是线性的由于确保目标函数有界)2.13(1||||,0)(,0..)(min:,,dEjdaxIidatsdxfxTjTiT降可行方向规划问题来计算下我们通过求解下列线性处在因此等其它有界形式也可写成如约束1||||1||||dd)2.13(1||||,0)(,0..)(mindEjdaxIidatsdxfTjTiT.0)(,)2.13(dxfdT则的最优解为设,0)(,00)(无非零解EjdaxIidadxfTjTiT点的是问题KKT)1.13(x;,,0,0)(1处的一个下降可行方向在是显然则：情形xfdddxfT即线性系统：可行方向处不存在下降这说明在则：情形,,0,0)(2xddxfT.,0)(,0)()2(;KKT)1.13(,0,0)()1(,)2.13(,1.1.13处的一个下降可行方向点在可行是函数则即若点的是问题则即若则的解是线性规划问题设定理xfddxfdxfxddxfdDxTTT我们有下列结论：由上面的分析,由线性搜索产生的步长其中需计算新的可行点我们点不是时的解当知由定理tDtdxxxd:,KKT,0)2.13(,1.1.132.线性搜索—计算步长:,我们考虑三种情形的计算关于为确保tDtdxxEjbdtaxatdxaxIibdtaxatdxatEjdaxIidajTjTjTjiTiTiTiTjTi,0)()(,)(,0,0)(,0我们有对任意的由于,)(1EjxIi及：情形)(\,)(,0,xIIibdtaxatdxatiTiTiTi我们有对任意的显然daxIIidaxabtdaxabtbdtaxatdxaTiTiTiiTiTiiiTiTiTi),(\min,,)(从而则若要使0),(\2daxIIiTi但：情形.0),(\3daxIIiTi但：情形).(),(\min,,3,maxdaxIIidaxabttTiTiTii我们令为此决定的计算完全由情形步长综上所述:,向法我们得到如下的可行方在上面分析的基础上Dtdxxtt,][0,max总有时则当max,3t自然令不存在若情形.)(minmax0ttdxftt来计算步长然后我们通过求解.1,1:..)(min.,,(13.3)4.STOP.,,|)(|31||||,0)(,0s.t.)(min2;0:.0,0)k(Zoutendij13.110max0max转步令令得步长求解其中计算由：步否则转下一步则得解若：步得解的线性规划问题求解下列关于：步令精度选取初始点：步算法算法kkdtxxttdxfddxxtxdxfddEjdaxIidadxfdkDxkkkkkkkttkkkkTkkTjkTiTkTxxxgxxgxxxgxxxgtsxxxxxf),()()()()(..)(minZoutendijk1.13)(取初始点：算法求解下列约束问题用例0,,,,)(aaaaxxxf解：TtTTTTdtxxttttdxfttxabdaxabdadddddtsddxIxf),(,)(min:122,11min2,;,1..min},{)(,)()()()((0))(max)((0)(0)(0))()()(所以解得求解问题计算步长得解解子问题：第一次迭代：TtTTTTTTdtxxttttdxftdaxabtdaxabdadddddddtsdxIxf)3/2,/(,)(min:11;,12..2min2}1,{)(,),()()((1)(2))()()()(max)()()()((1)(1)所以解得求解问题计算步长得解解子问题：第二次迭代：2}{)(,)1,1()((2)(2)xIxfT第三次迭代：最优解是故而且此例是凸规划点是知由定理得解解子问题：)()()(,,KKT,1..130..minxxdddddtsdd1122xy●●●●●)0(x)1(x)2(x可行域等值线非线性约束情形二.1||||)(,0)(..)(min.)(,0)(,}.,0)(|{)5.13(,0)(..)(minTTTdxIidxgtsdxfxdxIidxgRdDxIixgRdDIixgtsxfiinini：下降可行方向的计算为处的一个可行方向是则满足若对任意的记可行域考虑不等式约束问题：.,,导致可能的无解可能是空集是可行域非闭但该子问题的明显缺陷.,,(13.6).,0,.0,);()6.13(1||||)(,0)(0-)(..min,T不收敛可能导致相应的算法由于约束的突变中然而在处的下降可行方向是则若特别则是上述子问题的解设修改子问题如下：变量解决的办法是引入辅助xdzzzddxIizxgzdxftszziT方向能产生稳定的下降可行中约束的稳定性由于做出修改：对和年,).().(||||,)()()(..min(13.6)VeinottTopkis,1967TdIizdxgxgzdxftsziiT}0,)(|{max(13.7t))()(min.,0),,()7.13(,max0maxIitdxgttdtxftdxftdzzdxxkkikkkkkttkkkkkk其中：由线性搜索计算步长下降可行方向是则若的解是设问题令.0:John-Fritz)5.13().;((13.7).,,,2.1.13zxzdDxIigfi的充要条件是点的是原问题则的解为设问题连续可微设函数定理00dz.KKT0.KKTJohn-Fritz0,)()()(John-Fritz,00,John-Fritz).(条件时就是当条件弱条件比条件：满足全为零的数如果存在不点：的一个是问题称IixgxgxfIiDxiiIiiii.1,1:.4.(13.7t)3.STOP.,,||||2.,)()7.13(1;0:.0,0)Veinott-(Topkis13.210转步令：令步计算步长由线性搜索：步否则转下一步则得解若：步得解其中求解：步令精度选取初始点：步算法算法kkdtxxtxdzdxxkDxkkkkkkkkkk算法收敛性：.John-Fritz)5.13(}{3.2,,,3.1.13点的都是问题的任何极限点的点列产生则算法连续可微设函数定理xxIigfkiFrank-Wolfe算法与Zoutendijk算法类似略第二节Rosen投影梯度法思想.,,;,空间的投影为搜索方向的梯度的零即取负梯度在有效约束向影作为搜索方梯度在可行方向集的投将负否则向取负梯度方向为搜索方负梯度可行时最速下降法的推广：当1x2xdoD)(xfx●,13.2.1.,():||()||min{||-|||}().nnRxRPxPxxyxyPxx首先我们介绍投影的概念：定义设是闭凸集对若向量满足则称是在中的投影也是投影矩阵则是投影矩阵若投影矩阵是半正定的：由定义知影矩阵是一个投则称满足若对称矩阵定义我们引入投影矩阵投影为计算向量在集合中的QIQQQQQQQQQT-,,,2.2.13.,22投影矩阵的构造是投影矩阵则令行满秩设矩阵PQQIPMMMMQnmRMTTnm,-,)(,)(1-个行向量的第是其中则iMMMMMMyMyMMMMMQxRximmiiTiTTTn,)(,2111-的行向量生成的子空间投影到将向量即矩阵MxQ.,0,0))(-(,-1-的零空间投影到将向量即矩阵因此则令MxPMPxMMMMIMMPQIPTT一.线性约束情形}0,)(|{)(,}0,)(;0,)(|{)1.13(0,)(0,)(..)(minIixgixIxDxEixhIixgxDEibxaxhIibxaxgtsxfiiiiTiiiTii处的有效集为在记可行域考虑线性约束问题.,)(,00)())(-(-0||||-||)(||-)()(-)()(-)(,,.,0)(-,)(-.,)()(,1.2.131-221-)(处下降可行方向是因此即又从而可得即是投影矩阵证明：易验证处的下降可行方向在是函数则若令行满秩即无关处有效约束的梯度线性设在令设定理xdExIidaxfMMMMIMMddxfPxfPPxfxfPxfdxfPPPPxfddxfPdMMMMIPMxaaMDxTiTTTTTTTTTEiTixIiTi).()(-0,)(-,1.2.13),(,(2))(-,,,)1(:方向集处的可行即投影到的零空间投影到着将这意味知由定理边界上在可行域的处存在有效约束即在非空若此时空矩阵是则在可行域内部处无有效约束即若在注xMxfxfMPMdxxMxfdIPMxx会怎么样？时向；当得到下降可行方时当知由定理,0,0)(-,1.2.13dxfPd.0),(-)(-,)()(,,:.,,0),(KKT),(,0KKT)11.13(--)(-)()()(()(0,)())(1-}{\)()(1-1-处下降可行方向且必为则令即令新矩阵为中去掉行在矩阵修正方法产生新的方向则修正投影矩阵如果点是则条件：如果比较则令xdxfPdMMMMIPaaMMaMuxIjxxIiuavauxfwMxfxfMMMMIxfPvuxfMMMwTTEiTijxIiTiTjjiEiiixIiiiTTTT