最优化：可行方向法

1、最最 优优 化化主讲：刘陶文课件制作：刘陶文课件制作：刘陶文唯楚有材唯楚有材 於斯为盛於斯为盛学好最优化，走遍天下都不怕学好最优化，走遍天下都不怕第十三章第十三章 约束问题算法约束问题算法(II) 可行方向法可行方向法一、一、ZoutendijkZoutendijk可行方向法可行方向法二、投影梯度法二、投影梯度法三、既约梯度法三、既约梯度法思想思想点且单调下降列使得目标函数序构造可行点序列KKT,)( kkkxxfxkkkkkkkdxxdx1 , )( (2); (1), 产生新的可行点：计算步长受可行性限制通过线性搜索计算下降可行方向给定可行点其过程如下：. ,),2() 1 (线性约束问题

2、然后将其适当推广到非方向法题的可行我们先介绍线性约束问和考虑到算法第一节Zoutendijk EIixgiExIx AxDxEjxhIixgxDEjbxaxhIibxaxgtsxfijijTjjiTii0,)(|)()( , 0,)( ; 0,)(| ).( 0,)( 0,)(. . )(min 处的有效集为在记可行域考虑线性约束问题线性约束情形一 .1、下降可行方向0)( , 0);(, 0|)( ,) 1 .13(dxfxEjdaxIidaRdxSxDxTTjTin向满足：处的目标函数的下降方而在处的可行方向集在的约束是线性的由于确保目标函数有界)2 .13( 1 | , 0)(, 0.

3、. )(min : , ,dEjdaxIidatsdxfxTjTiT降可行方向规划问题来计算下我们通过求解下列线性处在因此等其它有界形式也可写成如约束1 |1 |dd)2 .13( 1 | , 0)(, 0. . )(min dEjdaxIidatsdxfTjTiT . 0)(,)2 .13(dxfdT则的最优解为设 , 0)(, 0 0)(无非零解EjdaxIidadxfTjTiT点的是问题KKT ) 1 .13(x;, , 0, 0)(1处的一个下降可行方向在是显然则：情形xfdddxfT即线性系统：可行方向处不存在下降这说明在则：情形 , , 0, 0)( 2xddxfT. , 0)(,

4、 0)( )2(;KKT) 1 .13(, 0, 0)( ) 1 (,)2 .13(, 1 . 1 .13处的一个下降可行方向点在可行是函数则即若点的是问题则即若则的解是线性规划问题设定理xfddxfdxfxddxfdDxTTT我们有下列结论：由上面的分析,由线性搜索产生的步长其中需计算新的可行点我们点不是时的解当知由定理tDtdxxxd :,KKT,0)2 .13(,1 . 1 .132.线性搜索计算步长:, 我们考虑三种情形的计算关于为确保tDtdxxEjbdtaxatdxaxIibdtaxatdxatEjdaxIidajTjTjTjiTiTiTiTjTi , 0)( )( ,)( , 0

5、 , 0 )(, 0 我们有对任意的由于, )(1EjxIi及：情形)( ,)( , 0 ,xIIibdtaxatdxatiTiTiTi我们有对任意的显然daxIIidaxabtdaxabtbdtaxatdxaTiTiTiiTiTiiiTiTiTi),( min , ,)( 从而则若要使0),( 2daxIIiTi但：情形 . 0),( 3daxIIiTi但：情形).( ),( min , ,3 ,maxdaxIIidaxabttTiTiTii我们令为此决定的计算完全由情形步长综上所述:,向法我们得到如下的可行方在上面分析的基础上Dtdxxtt , 0,max总有时则当max , 3t自然令不

6、存在若情形. )(min max0ttdxftt来计算步长然后我们通过求解. 1 , 1: . .)(min .,(13.3) 4. STOP., |)(| 3 1 | , 0)( , 0s.t. )(min 2; 0:. 0, 0)k(Zoutendij 13.110max0max转步令令得步长求解其中计算由：步否则转下一步则得解若：步得解的线性规划问题求解下列关于：步令精度选取初始点：步算法算法kkdtxxttdxfddxxtxdxfddEjdaxIidadxfdkDxkkkkkkkttkkkkTkkTjkTiTkTxxxgxxgxxxgxxxgtsxxxxxf) ,( )( )( )(

7、)(. .)(min Zoutendijk 1 .13)(取初始点：算法求解下列约束问题用例0 , , , ,)(aaaaxxxf解：TtTTTTdtxxttttdxfttxabdaxabdadddddtsddxIxf) ,( , )(min :122 ,11min 2, ;, 1 . .min , )( ,)( )()()(0)(max)(0)(0)(0)()()(所以解得求解问题计算步长得解解子问题：第一次迭代：TtTTTTTTdtxxttttdxftdaxabtdaxabdadddddddtsdxIxf)3/2 ,/( , )(min :11 ;, 1 2. .2min 2 1, )(

8、,) ,()( )(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)(. . )(min TTTdxIidxgtsdxfxdxIidxgRdDxIixgRdDIixgtsxf

9、iinini：下降可行方向的计算为处的一个可行方向是则满足若对任意的记可行域考虑不等式约束问题：.,导致可能的无解可能是空集是可行域非闭但该子问题的明显缺陷.,(13.6)., 0, . 0,);()6 .13( 1 |)(, 0)( 0-)(. . min ,T不收敛可能导致相应的算法由于约束的突变中然而在处的下降可行方向是则若特别则是上述子问题的解设修改子问题如下：变量解决的办法是引入辅助xdzzzddxIizxgzdxftszziT方向能产生稳定的下降可行中约束的稳定性由于做出修改：对和年,).().( |,)()( )(. . min (13.6)VeinottTopkis,1967T

10、dIizdxgxgzdxftsziiT 0,)(|max (13.7t) )()(min ., 0),()7 .13(,max0maxIitdxgttdtxftdxftdzzdxxkkikkkkkttkkkkkk其中：由线性搜索计算步长下降可行方向是则若的解是设问题令. 0:John-Fritz)5 .13( ). ;(13.7) . , , , 2 . 1 .13zxzdDxIigfi的充要条件是点的是原问题则的解为设问题连续可微设函数定理0 0dz.KKT0 .KKTJohn-Fritz 0,)()()( John-Fritz ,00, John-Fritz).(条件时就是当条件弱条件比条

11、件：满足全为零的数如果存在不点：的一个是问题称IixgxgxfIiDxiiIiiii. 1 , 1: .4 .(13.7t) 3. STOP., , | 2.,)( )7 .13( 1; 0:. 0, 0)Veinott-(Topkis 13.210转步令：令步计算步长由线性搜索：步否则转下一步则得解若：步得解其中求解：步令精度选取初始点：步算法算法kkdtxxtxdzdxxkDxkkkkkkkkkk算法收敛性：.John-Fritz)5 .13(3.2 , , , 3 . 1 .13点的都是问题的任何极限点的点列产生则算法连续可微设函数定理xxIigfkiFrank-Wolfe算法与算法与Z

12、outendijk算法类似算法类似略第二节第二节 RosenRosen投影梯度法投影梯度法思想思想., , ;,空间的投影为搜索方向的梯度的零即取负梯度在有效约束向影作为搜索方梯度在可行方向集的投将负否则向取负梯度方向为搜索方负梯度可行时最速下降法的推广：当1x2xdoD)(xfx,13.2.1 .,( ): |( )| min| - | | ( ).nnRxRP xP xxy xyP xx 首先 我们介绍投影的概念：定义设是闭凸集 对若向量满足则称是 在 中的投影也是投影矩阵则是投影矩阵若投影矩阵是半正定的：由定义知影矩阵是一个投则称满足若对称矩阵定义我们引入投影矩阵投影为计算向量在集合中的

13、QIQQQQQQQQQT-, , 2 . 2 .13.,22投影矩阵的构造是投影矩阵则令行满秩设矩阵PQQIPMMMMQnmRMTTnm,- ,)( ,)(1 -个行向量的第是其中则iMMMMMMyMyMMMMMQxRximmiiTiTTTn , )( ,2111 -的行向量生成的子空间投影到将向量即矩阵MxQ., 0,0)(-( ,-1 -的零空间投影到将向量即矩阵因此则令MxPMPxMMMMIMMPQIPTT一.线性约束情形0,)(|)( , 0,)( ; 0,)(| ) 1 .13( 0,)( 0,)(. . )(min IixgixIxDxEixhIixgxDEibxaxhIibxax

14、gtsxfiiiiTiiiTii处的有效集为在记可行域考虑线性约束问题.,)( , 0 0)()(-( - 0|-|)(|- )()(-)()(-)( ,. , 0 )(- ,)(- .,)()( , 1 . 2 .131 -221 -)(处下降可行方向是因此即又从而可得即是投影矩阵证明：易验证处的下降可行方向在是函数则若令行满秩即无关处有效约束的梯度线性设在令设定理xdExIidaxfMMMMIMMddxfPxfPPxfxfPxfdxfPPPPxfddxfPdMMMMIPMxaaMDxTiTTTTTTTTTEiTixIiTi).( )(- 0,)(-,1 . 2 .13),(, (2) )(

15、- , , ) 1 (:方向集处的可行即投影到的零空间投影到着将这意味知由定理边界上在可行域的处存在有效约束即在非空若此时空矩阵是则在可行域内部处无有效约束即若在注xMxfxfMPMdxxMxfdIPMxx会怎么样？时向；当得到下降可行方时当知由定理,0,0)(-,1 . 2 .13dxfPd.0),(- ) ( - ,)()( ,:., 0),(KKT),( , 0 KKT)11.13( -)( -)()()()(0 , )()( 1 - )()(1 -1 -处下降可行方向且必为则令即令新矩阵为中去掉行在矩阵修正方法产生新的方向则修正投影矩阵如果点是则条件：如果比较则令xdxfPdMMMMI

16、PaaMMaMuxIjxxIiuavauxfwMxfxfMMMMIxfPvuxfMMMwTTEiTijxIiTiTjjiEiiixIiiiTTTT.(2).0)-(-)-( ,0-)( 0,)(0-)( 0,)( . 0)( ) 1 ( )( )( )(下降性：显然成立无关矛盾处有效约束的梯度线性这与得上述两式相减即由于即若xavvauuauavauauxfxfPavauxfxfPxfPdEiiiijxIiiiijjEiiijjjxIiiiEiiijxIiii( ) (3):0, 0,( ) ( )-0 ( )- ( )- ( ) -( )-0Tiiijjiii I xji ETTjjTjjT

17、TTTTjjjjjjMda diI xEjf xua u av af x M wf x M w u af xM wu aa da P f xa PM w u a Pa 可行性 显然 即由于即故.)( -)(- )()( . 0),( )2( .KKT) 1 .13(, 0 (1) .)( ,)( 0. )( .,)()( , 2 . 2 .131 -)(1 -)(处的下降可行方向在是函数则令若存在点的是问题则若中的元素数目相同和的维数分别于其中令若行满秩即无关处有效约束的梯度线性设在令设定理xfxfPdMMMMIPajaMuxIjxuExIvuvuMMMMwxfPMxaaMDxTTEiTixI

18、iTijTTEiTixIiTi(0)(0)0-1( )13.4 (Rosen)0,0,:0,().1,() , -()()2-(). | , 4.3, , STOP. kkkTii ITTkkkkkkTii EkkkkkxDkII xEIPIaMPI MM MMadPf xdI算法投影梯度法步 ：选取初始点精度令步 ：若令否则令步 ：令若转步步 ：若则得解否则max( )( )-1( )( )( )( )( )( )( )0(1)( )max1, ()()0, , ,0,: , 1.4 min()(), (13.3). ,(kkTkkkkkkkkkjkkkkkkkt tkkkkkkkuwM MMf xvuxjIuIIjf xtd