第十一次可行方向法课件.ppt

1、方法方法一一WolfeFrank .给给定定非非线线性性规规划划问问题题 0.)(minxbAxtsxf。函数，函数，是可微是可微维列向量，维列向量，是是，矩阵，秩为矩阵，秩为是是其中其中nRxxfmbmnmA )(为可行域。为可行域。称称令令DxbAxxD, 0,| 问题问题. 1)1(算法分析算法分析. 2线线性性规规划划方方法法求求解解。线线性性化化，再再利利用用函函数数在在每每次次迭迭代代中中，将将目目标标算算法法思思想想：)(xf算算法法分分析析：则则有有设设已已知知可可行行点点,kx)()()()()()()(kTkkTkkTkkxxfxfxxfxxxfxfxf 求求解解线线性性规

2、规划划DxtsxxfTk .)(min)2(的的可可行行下下降降方方向向。处处关关于于在在点点是是则则向向量量时时）当当（点点。）的的是是（则则时时）当当（则则有有）的的最最优优解解，是是线线性性规规划划（，如如果果可可微微，设设定定理理DxxfxydxyxfTKxxyxfyDxxfkkkkkkTkkkkTkkk)(,0)()(21,0)()(12)( ：求求解解下下列列一一维维搜搜索索问问题题时时当当,0)()( kkTkxyxf10.)(min ttsxytxfkkk重重复复上上述述过过程程。再再对对点点则则为为凸凸集集，。因因为为则则可可取取设设极极小小点点为为111)(, kkkkkk

3、kkxDxDxytxxt算算法法：WolfeFrank 。，令令允允许许误误差差给给定定初初始始可可行行点点00,.10 kx 求解线性规划求解线性规划. 2DxtsxxfTk .)(min。解解得得极极小小点点ky。转转步步；否否则则则则停停止止计计算算，得得到到点点若若4,| )()(|. 3kkkTkxxyxf ：求求解解下下列列一一维维搜搜索索问问题题出出发发，沿沿方方向向从从kkkxyx . 410.)(min ttsxytxfkkk。解解得得kt。返回返回令令令令2,1:, )(. 51 kkxytxxkkkkk算算法法步步骤骤. 3算算法法收收敛敛性性：点点。）的的是是（点点意意

4、一一个个极极限限则则必必有有极极限限点点，且且其其任任是是无无穷穷点点列列）如如果果（点点。）的的是是（则则其其最最后后一一个个点点是是有有穷穷点点列列）如如果果（）产产生生的的点点列列，则则算算法法求求解解（是是由由，如如果果，有有界界可可微微，设设定定理理TKDxxTKxxwolfeFrankxDxDxfkkkk 1*,21,11)(0可行方向法可行方向法二二 Zoutendijk.问题问题. 1给定非线性规划问题给定非线性规划问题 eCxbAxtsxf.)(min)3(。维维列列向向量量维维和和分分别别是是和和秩秩为为矩矩阵阵，是是矩矩阵阵，秩秩为为是是是是可可微微函函数数其其中中lme

5、bRxlnlCmnmAxfn,)( 搜搜索索。处处的的可可行行下下降降方方向向进进行行在在每每次次迭迭代代中中沿沿迭迭代代点点算算法法思思想想：？如如何何确确定定可可行行下下降降方方向向为可行域。为可行域。称称令令DeCxbAxxD, ,| 算法分析算法分析. 2束束确确定定可可行行方方向向。）利利用用迭迭代代点点的的积积极极约约（1。要要条条件件是是处处的的可可行行方方向向的的充充分分必必是是则则非非零零向向量量其其中中处处有有，在在点点设设定定理理0,0,121212211 CddAxdbbbAAAbxAbxAxDx证明：证明： 必必要要性性。仍仍是是可可行行解解。即即有有，的的，使使得得

6、对对任任意意处处的的可可行行方方向向。则则存存在在是是设设非非零零向向量量tdxtxd ),0(0 btdxA )(etdxC )()()(21tdxAAtdxA 212211bbdtAxAdtAb。，所以，所以因为因为001 dAtetCdetdxC )(。所以所以0 Cd充分性同理可证。充分性同理可证。）可可行行下下降降方方向向的的确确定定（2 000)(1CddAdxfT处的可行下降方向。处的可行下降方向。是点是点xd的的可可行行下下降降方方向向？如如何何求求出出满满足足上上述述条条件件求求解解下下列列线线性性规规划划问问题题 jdCddAtsdxfjT, 1|00.)(min1)4(。

7、标标函函数数值值不不大大于于是是可可行行解解，因因此此最最优优目目）（结结果果：001 d。，则则得得到到可可行行下下降降方方向向值值小小于于）如如果果线线性性规规划划的的最最优优（02点点。是是，则则值值等等于于）如如果果线线性性规规划划的的最最优优（TKx 03。）的的最最优优目目标标函函数数值值为为点点的的充充要要条条件件是是（是是则则其其中中处处有有，在在点点设设定定理理04,21212211TKxbbbAAAbxAbxAxDx ）搜搜索索步步长长的的确确定定（3。可可令令则则和和该该点点的的可可行行下下降降方方向向已已知知迭迭代代点点kkkkkkdtxxdx 1,）使使目目标标函函数

8、数值值下下降降。（仍仍为为可可行行解解；）（应应满满足足：其其中中iidtxitkkkk :kt问问题题求求利利用用下下列列辅辅助助线线性性规规划划 0)()(.)(mintetdxCbtdxAtstdxfkkkkkk)5(）化化简简线线性性规规划划问问题题（ 5是是可可行行下下降降方方向向，所所以以因因为为kd，即即约约束束条条件件0 kCdeCxtCdCxtdxCkkkkk )(总总是是成成立立。 21212211,bbbAAAbxAbxAxkkk其其中中处处有有设设在在点点可可以以改改写写为为则则约约束束条条件件btdxAkk )( 2121)()(bbtdxAtdxAkkkk，所所以以

9、不不等等式式约约束束因因为为0,0,111 tdAbxAkk自自然然成成立立。11)(btdxAkk ）简简化化为为所所以以问问题题（ 5 0.)(min222tbdtAxAtstdxfkkkk为为。所所以以约约束束条条件件可可改改写写则则，令令0,222 bdAdxAbbkk 0tbdt的的上上界界为为则则可可得得 t 000|minmaxddddbtiiii当当当当存存在在(*)所所以以问问题题可可最最终终简简化化为为max0.)(mintttstdxfkk )6(算法步骤算法步骤. 3。令令给给定定初初始始点点0,)1(0 kx。计算计算。使得使得和和分解成分解成和和处将处将在点在点)(

10、,)2(22112121kkkkxfbxAbxAbbAAbAx 求求解解线线性性规规划划问问题题)3( jdCddAtsdxfjTk, 1|00.)(min1。求求得得最最优优解解kd）。点点；否否则则转转（是是则则算算法法结结束束，如如果果5,0)()4(TKxdxfkkTk ，求求解解一一维维搜搜索索问问题题）式式计计算算利利用用（max*)5(tmax0.)(mintttstdxfkk ）。，返返会会（。令令，令令解解得得极极小小值值点点21:1 kkdtxxtkkkkkZoutendijk221212121212min246210(1)20(2). .0(3)0(4)xxxxxxxxs

11、 txx 用用方方法法解解：例例100 x 初初始始点点解解 第一次迭代第一次迭代112222( ),()244xf xf xx , 3 4, 1 21( )( )( )( ),x在在处处为为紧紧约约束束是是松松的的 故故121021,0111AA 1201,02bb 11:min()0. .1,1,2Tjf xdA ds tdj 解解线线性性规规划划1212122400min. .1111dddds tdd 即即111d 由由图图解解法法得得求步长求步长1122211,22dA dbbA xmax12min,112 进行一维搜索进行一维搜索, 解解11201min()266f xd 11 得

12、得步步长长 111112dxx 20()2f x , 1 2, 3 42( )( )( )( ),x在在处处为为紧紧约约束束是是松松的的1212211010,110120AAbb 12212212200. .1111minddddds tdd 解解211d 由由图图解解法法得得2222210111,01111dA dbbA x max1 同样同样,进行第二次迭代进行第二次迭代:进行一维搜索进行一维搜索, 解解22201min()222f xd 212 得得步步长长32223122xxd 所所以以继续迭代继续迭代,因为因为 所以所以 300d 33122xKT mixgtsxfi,1,0)(.)

13、(min 在迭代点在迭代点 x k ，选择一个可行下降方向，选择一个可行下降方向 d k 为搜索方向，为搜索方向， 设设 d k 满足满足)(,0)(0)(kkTkikTkxIidxgdxf d k 可以通过解下述线性规划获得：可以通过解下述线性规划获得：njdxIidxgdxftsjkTkiTk,2,1,11)(,)()(.min nddd1其其中中4. 非线性约束非线性约束;)()(,0*线线性性无无关关）点点（若若已已是是处处不不存存在在可可行行下下降降方方向向则则性性质质：若若kkikkxIixgTKxx 。处处的的一一个个可可行行下下降降方方向向则则得得到到若若*,0*dxk 。点点

14、，即即总总有有一一定定收收敛敛到到有有例例子子表表明明上上述述方方法法不不0* TK可可行行解解。是是上上述述线线性性规规划划的的一一个个Td)0,0(,0 改进方法：在找可行下降方向时考虑所有约束，即改进方法：在找可行下降方向时考虑所有约束，即njdmidxgxgdxftsjTkikiTk,2,1,11,2,1,)()()(.min 行行解解。也也是是上上述述线线性性规规划划的的可可Td)0,0(,0 ;,0*点点是是则则性性质质：若若TKxk 处处的的可可行行下下降降方方向向。是是则则若若kxd *,0* 是是可可行行方方向向。又又，时时，*,0*)(,0*)(0)()(ddxfdxgxgxIiTkTkikik 可证：改进方法具有全局收敛性。可证：改进方法具有全局收敛性。