第四章约束最优化方法

1、 min( ).( )0,1,2,.(1)min( )=|,( )0,1,2,.(2)ix Dnif xs tg ximf xDx xRg xim ；或或写写成成；其其中中可可行行域域且且( )0.( )0,( )0( )=0iiiixDxg xxg xxxxg xxg xx 设设，显显然然 应应满满足足所所有有的的约约束束条条件件. .现现考考虑虑某某一一个个不不等等式式约约束束条条件件满满足足这这一一不不等等式式有有两两种种情情况况：一一种种是是这这时时点点 不不在在由由这这一一约约束束条条件件所所形形成成的的可可行行域域边边界界上上，因因此此当当点点不不论论沿沿着着什什么么方方向向稍稍微

2、微离离开开点点 时时，都都不不会会违违背背这这一一约约束束条条件件，也也就就是是说说这这一一约约束束条条件件对对点点 在在选选择择可可行行方方向向时时不不起起约约束束作作用用. .因因此此称称这这样样的的为为点点 处处的的约约. .相相反反，另另一一种种情情况况是是，此此时时点点 位位于于由由该该约约不不起起作作用用束束.xxxx束束条条件件所所形形成成的的可可行行域域边边界界上上，当当点点沿沿某某些些方方向向稍稍微微离离开开 时时，仍仍能能满满足足约约束束条条件件，而而沿沿着着另另一一些些方方向向离离开开 时时，不不论论步步长长多多么么小小，都都将将不不满满足足这这个个约约束束条条件件. .

3、也也就就是是说说这这个个约约束束条条件件对对 选选择择可可行行方方向向是是有有约约束束作作用用的的. .将将这这样样的的约约束束条条件件称称为为点点 处处的的起起作作用用约约束束 (2)( )=0( )0.=|( )=0,( )0( )0( )0iiiiijxDg ximg xxI xi g ximxg ximg xxh x 对对于于问问题题式式，设设，若若有有（1 1），则则称称不不等等式式约约束束为为点点 处处的的起起作作用用约约束束 且且将将下下标标集集 ( ),1( ),1称称为为点点 的的起起作作用用下下标标集集. .若若有有（1 1），则则称称不不等等式式约约束束为为点点 的的不不

4、起起作作用用约约束束. .显显然然等等式式约约束束都都是是起起作作用用约约束束. .(2).xx对对于于非非线线性性规规划划问问题题式式，如如果果可可行行点点 处处，各各起起作作用用约约束束的的梯梯度度向向量量线线性性无无关关，则则称称 是是约约束束条条件件的的一一个个正正则则点点*(2)( )xDf xxxx 考考虑虑问问题题式式，设设，在在处处可可微微，若若是是局局部部最最优优解解，则则点点处处必必不不存存在在可可行行下下降降方方向向. .*1(1)(2).()0;1( )0.xxDxDxf xxDxxxgxx 考考虑虑问问题题式式或或式式，设设是是它它的的极极小小点点，那那么么可可能能在

5、在可可行行域域 的的内内部部，也也可可能能在在可可行行域域的的边边界界上上 若若在在 的的内内部部，实实际际上上是是个个无无约约束束问问题题, ,必必满满足足条条件件：若若在在 的的边边界界上上，分分为为几几种种情情况况来来讨讨论论：（ ）设设位位于于一一个个约约束束条条件件形形成成的的边边界界上上，即即只只有有一一个个起起作作用用约约束束，不不失失一一般般性性，设设位位于于第第一一个个约约束束条条件件生生成成的的边边界界上上，即即是是 点点处处的的起起作作用用约约束束*11*1*1*1()=0.-()().-()(),-()()( )( )gxxf xgxf xgxxpf xgxpxxf x

6、gxx故故有有若若是是局局部部最最优优解解，则则必必有有与与同同处处在在一一条条直直线线上上，且且方方向向相相反反 如如若若与与不不在在一一条条直直线线上上且且方方向向相相反反，则则必必可可在在 点点处处找找到到一一个个方方向向它它与与及及的的夹夹角角都都是是锐锐角角，即即 是是 点点处处的的可可行行下下降降方方向向，这这与与定定理理4.1.14.1.1相相矛矛盾盾. .用用向向量量语语言言来来描描述述上上述述几几何何性性质质，即即：若若是是局局部部最最优优解解，与与（起起作作用用约约束束）在在点点*1*10()-()=00()()f xgxf xgx 1 11 11 1一一阶阶可可微微，则则

7、必必存存在在实实数数，使使成成立立，或或说说梯梯度度向向量量可可由由梯梯度度向向量量正正线线性性表表出出. .*12*12*12*12122()=0()=0()()()()()()()()00,xgxgxxf xgxgxxxgxgxf xgxgx（ ）设设 同同时时位位于于两两个个约约束束条条件件形形成成的的边边界界上上，即即，或或说说有有两两个个起起作作用用约约束束，此此时时，必必位位于于与与所所形形成成的的夹夹角角内内；否否则则，点点处处必必可可找找到到一一个个可可行行下下降降方方向向. .用用代代数数语语言言来来描描述述：若若是是局局部部最最优优解解，且且与与线线性性无无关关，则则必必可

8、可由由与与的的正正线线性性组组合合表表出出. .即即：必必存存在在，使使*1122()-()-()=0f xgxgx成成立立. .*()*=1*()-()=0(3)0().()0,1,2,.(3)()-()=0,()0,iii I xiiimiiiiif xg xI xxxg ximf xg xg x 将将上上述述分分析析作作进进一一步步类类推推，有有在在上上式式中中，是是点点处处的的起起作作用用下下标标集集，且且它它们们的的起起作作用用约约束束梯梯度度向向量量线线性性无无关关，即即 同同时时也也是是一一个个正正则则点点为为了了把把不不起起作作用用约约束束也也包包括括到到上上式式中中，可可以以

9、增增加加一一个个松松紧紧条条件件: :则则式式就就可可改改写写为为：1,2,(4)0,1,2,.iimim *()( )0()0=0()(4)(3)(4)-(2),()()()iiiiiiiI xg xxg xiI xxD f g iI xxg iI xxg x 当当时时，即即是是 的的不不起起作作用用约约束束，故故有有，则则由由松松紧紧条条件件：（）. .因因此此式式第第一一组组方方程程与与式式第第一一组组方方程程实实际际上上是是相相同同的的. .式式就就是是著著名名的的库库恩恩 塔塔克克条条件件，简简称称为为K-TK-T条条件件，满满足足K-TK-T条条件件的的点点称称为为K-TK-T点点

10、. .定定理理4.1.24.1.2 考考虑虑问问题题式式，设设在在处处可可微微，在在点点处处连连续续. . *12*=1*|()=(),()-()=0,()0,1,2,(5)0,1,2,.mmiiiiiiiI xxxf xg xg ximim 线线性性无无关关( (即即是是一一个个正正则则点点).).若若是是局局部部最最优优解解，则则存存在在向向量量， ，使使下下述述条条件件成成立立：min( )( )0,1,2,s.t(6)( )0,1,2, .(4)( )0( )0,-( )0(4)-ijjjjf xg ximh xjlh xh xh x 考考虑虑问问题题： ；为为了了利利用用式式，将将等

11、等式式约约束束，用用来来代代替替，这这样样就就可可以以利利用用式式，得得到到同同时时含含有有等等式式与与不不等等式式约约束束条条件件的的库库恩恩 塔塔克克条条件件，叙叙述述如如定定理理. . *12*4.1.3(6), ()=|()=0 1,( ),( )()()()( )(1,2, )()()|(),1,2,=()iiijijmxD I xi g ximf xg x iI xxg xiI xxh xjlxg xh xiI xjlx 定定理理考考虑虑问问题题式式，设设，在在处处可可微微，在在点点处处连连续续, ,在在点点处处连连续续可可微微，且且向向量量集集，线线性性无无关关. .若若是是问问

12、题题的的局局部部最最优优解解，则则必必存存在在向向量量， ，和和*12*=1=1*=()()-()-()=0,()0,1,2,(7)0,1,2,.(7)-lmliijjijiiif xg xh xg ximim 向向量量， ，使使下下述述条条件件成成立立：式式就就是是含含有有等等式式与与不不等等式式约约束束的的库库恩恩 塔塔克克条条件件. .*=1=1*1212*()-()-()(6)mliijjijmmf xg xh x通通常常称称函函数数为为问问题题式式的的广广义义拉拉格格朗朗日日函函数数，称称乘乘子子， ，和和， ，为为广广义义拉拉格格朗朗日日乘乘子子，称称向向量量和和为为乘乘子子向向量

13、量. .22112212221212min( )2210105.36f xxx xxxxxxs txx 22112212*T1212*121*12*2( )0( )50.( )360=(, ) ,4+2-10()=2+2-10-2()=-2-3()=-1ig xgxxxs tgxxxKTxxxxxf xxxxgxxgx 解解：将将上上述述问问题题的的约约束束条条件件改改写写为为的的形形式式：设设点点为为有有及及1211212122221122121212124.1.24+2-10+2+3=02+2-10+2+=0(5)0(63)000 xxxxxxxxxxxxKT 由由定定理理，且且将将式式中

14、中第第1 1个个向向量量方方程程拆拆成成分分量量形形式式，有有：求求解解上上述述联联立立方方程程组组( (若若原原问问题题有有等等式式约约束束的的话话，还还须须把把等等式式约约束束也也加加到到方方程程组组中中去去) )，即即可可求求出出 ， ， ，则则可可得得到到条条件件的的点点. .上上述述方方程程组组是是非非线线性性方方程程组组，*0,.ix 求求解解时时一一般般都都要要首首先先利利用用松松紧紧条条件件（即即上上述述方方程程组组中中的的第第3 3、第第4 4个个方方程程），其其实实质质是是分分析析点点处处，哪哪个个（那那些些）是是不不起起作作用用约约束束，以以便便得得到到这这样样分分情情况

15、况讨讨论论求求解解较较容容易易*12121212*1122121112121(1)=0=04+2-10=02+2-10=0=0=5()0(2)( )0( )=04+2-10+2=02+2-10+2=0(5xxxxxxxgxgxgxxxxxxx 假假设设两两个个约约束束均均是是 点点处处的的不不起起作作用用约约束束，即即有有，代代入入方方程程组组中中有有：解解之之有有: :但但将将该该点点代代入入约约束束条条件件，不不满满足足，因因此此该该点点不不是是可可行行点点. .若若是是起起作作用用约约束束，是是不不起起作作用用约约束束，则则有有，代代入入式式中中：22121)00 xx 1212*T12

16、112212221222=1=21=0=(1, 2)(3)( )0( )0=04+2-10+3=02+2-10+=0(63)00=0 xxxgxgxxxxxxx 解解出出：代代入入原原问问题题约约束束条条件件中中检检验验，可可知知该该点点是是可可行行点点，且且满满足足定定理理中中条条件件，又又是是一一个个正正则则点点，故故它它是是一一个个K-TK-T点点. .若若是是不不起起作作用用约约束束，是是起起作作用用约约束束，则则有有，代代入入式式中中：解解上上述述方方程程组组，可可得得到到2222122=-.=-055=0=0(1) 或或而而，不不满满足足的的条条件件，而而及及同同情情形形的的结结果

17、果1212112121222212121212*T(4)00 ,4+2-10+2+3=02+2-10+2+=0506300000 ,=(1, 2) .( )xxxxxxxxxxxf xKT 假假设设两两个个约约束束均均起起作作用用，这这时时，故故有有求求解解上上述述方方程程组组，得得到到的的解解不不满满足足与与故故舍舍去去. .因因此此本本题题的的K-TK-T点点为为 同同时时本本题题凸凸函函数数，故故本本题题是是凸凸规规划划，对对凸凸规规划划条条件件也也是是充充分分条条件件*T=(1, 2).x，因因此此也也是是本本题题的的全全局局极极小小点点min( ).( )0,1,2,.(1)ikkk

18、kf xs tg ximDxxp ( )( )( )( )( )( )考考虑虑问问题题：；记记上上述述问问题题的的可可行行域域为为 ，设设是是它它的的一一个个可可行行点点，但但并并不不是是所所要要求求的的极极小小点点. .为为了了求求得得极极小小点点或或近近似似极极小小点点，应应在在的的可可行行下下降降方方向向中中选选取取某某一一方方向向为为搜搜索索方方向向，然然后后确确定定该该方方向向上上的的步步长长，使使 +1+1+1+1=+(2)()()kkkkkkkkkxxpDf xf xxxx ()( )( )()( )( )()( )()( )()()()()( )( )若若满满足足精精度度要要求

19、求，停停止止迭迭代代，就就是是所所要要求求的的点点；否否则则从从出出发发继继续续迭迭代代，直直到到满满足足要要求求为为止止，上上述述方方法法称称为为可可行行方方向向法法. .它它具具有有下下述述特特点点：迭迭代代过过程程中中所所采采用用的的搜搜索索方方向向为为可可行行方方向向，所所产产生生的的迭迭代代点点列列始始终终在在可可行行域域内内，目目标标函函数数值值单单调调下下降降. .这这是是一一类类算算法法，由由不不同同的的规规则则产产出出可可行行方方向向作作为为搜搜索索方方向向形形成成了了不不同同的的可可行行方方outendijkoutendijk1960向向法法. .下下面面介介绍绍Z Z可可

20、行行方方向向法法，它它是是由由Z Z于于年年提提出出的的一一种种算算法法，用用求求解解一一个个线线性性规规划划问问题题来来确确定定可可行行下下降降方方向向的的方方法法，是是一一种种线线性性化化的的方方法法. .min( ),s.t(3).( ),(3).nmlf xAxbExef xAmnElnxRbReRml 考考查查一一个个非非线线性性规规划划问问题题： ；其其中中：是是可可微微函函数数， 为为矩矩阵阵， 为为矩矩阵阵, ,即即式式中中有有 个个线线性性不不等等式式约约束束，有有 个个线线性性等等式式约约束束1122112214.2.1(3)=,=: 1)000.2)( )0.nTxxA

21、x b A x bAbAbAbp pRpxA pEppf xpp 定定理理设设 是是问问题题式式的的一一个个可可行行解解，且且在在点点处处有有，其其中中，则则向向量量（且且）是是点点 处处的的可可行行方方向向的的充充要要条条件件为为：，若若此此时时 又又满满足足：，则则 是是一一个个可可行行下下降降方方向向112(3)min( );0.0(4)11,1,2, .(,) .(4).=0TjTnxpzf xpA ps tEpdjnpd ddpppp 从从上上述述定定理理可可知知，要要寻寻找找问问题题式式的的可可行行点点 的的一一个个可可行行下下降降方方向向 就就相相当当于于要要求求解解如如下下的的

22、一一个个线线性性规规划划问问题题： 式式中中式式中中所所增增加加的的最最后后一一个个约约束束是是为为了了防防止止，而而求求 主主要要是是求求出出一一个个方方向向，对对模模的的大大小小无无关关紧紧要要 显显然然是是可可行行解解，因因此此函函数数的的最最优优值值必必小小于于或或等等于于零零，若若目目标标函函数数-px的的最最优优值值小小于于零零，则则得得到到可可行行下下降降方方向向 ； 若若目目标标函函数数的的最最优优值值等等于于零零，则则可可以以证证明明 即即为为库库恩恩 塔塔克克点点. .112211224.2.2(3)=,=-(4)xxA x b A x bAbAbAbx 定定理理设设 是是

23、规规划划问问题题式式的的一一个个可可行行解解，且且在在点点处处有有，其其中中，则则 是是库库恩恩 塔塔克克点点的的充充要要条条件件是是规规划划式式的的目目标标函函数数最最优优值值为为零零. .min( )s.t( )0,1,2,.(5)( )( )1,2,inif xg ximxRf xg xim考考查查一一个个非非线线性性规规划划问问题题： ；其其中中：，（）均均为为可可微微函函数数. .如如何何求求上上式式的的可可行行下下降降方方向向？ 4.2.3(5)=|( )0( ),( )()( )()( )0( )0 ().iiiTTixIi g xxf xg x iIxg x iIxf xpg

24、xpiIp 定定理理设设 是是问问题题式式的的一一个个可可行行解解，是是点点 处处的的起起作作用用约约束束下下标标集集，若若在在点点 处处可可微微，在在点点 处处连连续续，如如果果，则则 是是可可行行下下降降方方向向(5)( )0(6)( )0 ()( )-( )()(7)0TTiTTixpf xpg xpiIpf xpg xpiI 根根据据定定理理可可知知，规规划划问问题题式式在在可可行行解解 处处的的可可行行方方向向 应应满满足足：而而上上述述方方程程组组当当引引进进数数 后后，等等价价于于下下述述方方程程组组求求向向量量及及实实数数 ：12min( ).-( )()(8)11,1,2,(

25、,) .TTijTnppf xps tg xpiIdjnpd dd 而而满满足足上上式式的的可可行行下下降降方方向向 及及数数 一一般般有有很很多多个个，而而希希望望求求出出能能使使目目标标函函数数值值下下降降最最多多的的方方向向 ，因因此此将将上上式式转转化化为为对对 求求极极小小值值的的一一个个线线性性规规划划问问题题： ；式式中中 ( )( )( +1)( +1)( )( )( +1)( +1)( )( )0( )( ),=+()min(+)(9)max|+kkkkkkkkkkkkkkkxpxDkxpxxxpxDf xf xpxpD 设设可可行行点点 处处的的可可行行下下降降方方向向 已

26、已求求出出，为为了了以以后后叙叙述述方方便便，假假定定就就是是第第 次次迭迭代代点点的的出出发发点点其其可可行行下下降降方方向向为为，则则后后继继点点为为为为了了使使，且且使使的的值值尽尽可可能能的的小小，求求解解一一维维搜搜索索问问题题：同同样样区区分分不不同同的的约约束束情情况况来来讨讨论论. .( )( )( )( )( )( )( )( )( )( )( )(3)min(+)(+).(10)(+)=0= .kkkkkkkkkkkf xpA xpbs tE xpepEpxExex 求求解解上上式式时时，考考虑虑到到线线性性约约束束时时式式，先先求求解解： ；而而上上式式可可进进一一步步化

27、化简简：因因为为是是可可行行方方向向，有有：； 而而是是可可行行点点，有有：因因此此上上式式中中第第2 2个个约约束束必必定定能能满满足足，可可不不再再考考虑虑它它. .在在点点处处将将不不等等式式约约束束分分为为起起作作用用约约束束与与不不起起作作用用约约束束，设设( )( )11221122( )( )111( )( )222( )( )1( )11=,=(10)+(11)+(12)0 .0=(11).(10)(12)(10)kkkkkkkkkA xb A xbAbAbAbA xA pbA xA pbpA pA xb 若若记记，则则式式中中第第一一个个约约束束就就可可记记成成又又因因是是可

28、可行行方方向向，由由定定理理知知又又设设，以以及及，因因此此式式也也自自然然满满足足 因因此此式式中中的的约约束束条条件件只只剩剩下下式式，故故式式可可简简化化为为：( )( )( )( )222( )( )222( )( )222( )( )2222min(+)+.(13)0-,(14)0-,0kkkkkkkkkkf xpA xA pbs tA pb A xbb A xpA ppbbb A xA xbb ；以以下下再再推推导导上上式式中中求求 上上限限的的公公式式，将将上上式式中中的的约约束束条条件件改改写写为为：若若记记则则有有：，同同时时考考虑虑到到，且且故故由由此此可可有有 的的上上限

29、限：( )22( )2( )( )( )(-)min0 ,0=()(15)0(10)min(+).0(16)(15).(4)kiiikiiiikkkbb A xpppA ppbpbpif xps txp 当当当当（式式中中， 表表示示 ， 中中第第 个个分分量量）因因此此求求解解式式就就化化为为求求解解： ；由由式式确确定定因因此此对对于于约约束束为为线线性性函函数数的的非非线线性性规规划划，若若已已知知一一个个迭迭代代点点后后，可可由由求求解解式式得得到到可可行行下下降降方方向向)(16).kk ，再再由由式式求求解解在在此此方方向向上上的的步步长长(0)12( )1122( )( )112

30、2( )( )11,: 0.2=,.3=0=0(kkkkkxDkxAbAbAbAbA xb A xbxxEAf x 约约束束为为线线性性函函数数时时非非线线性性规规划划的的可可行行方方向向法法计计算算步步骤骤如如下下：第第 步步：给给定定初初始始可可行行点点允允许许误误差差0,00,0，置置第第 步步：在在点点处处把把 与与 分分解解成成：，使使第第 步步：判判断断是是否否是是问问题题的的可可行行域域的的内内点点. .（1 1）若若是是可可行行域域的的一一个个内内点点（此此时时问问题题中中没没有有等等式式约约束束，即即，且且），而而且且( )1( ),.kkx 停停止止迭迭代代，得得到到近近似

31、似极极小小点点( )( )1( )( )( )( )1()=-()64min( );0.011,1,2, .kkkkkkTjxf xpf xxxzf xpA ps tEpdjn （2 2）若若是是可可行行域域的的一一个个内内点点，且且，则则取取搜搜索索方方向向，然然后后转转第第 步步，即即用用目目标标函函数数的的负负梯梯度度方方向向作作搜搜索索方方向向再再求求步步长长，此此时时类类似似于于无无约约束束问问题题. .（3 3）若若不不是是可可行行域域的的一一个个内内点点（即即在在可可行行域域的的边边界界上上），则则要要寻寻找找可可行行下下降降方方向向，转转第第4 4步步. .第第 步步： 求求解

32、解线线性性规规划划问问题题： ( )( )12(,) .(,).Tkknpd ddpz 其其中中设设求求得得最最优优解解为为( )( )2( )( )( )( )( +1)( )( )5.(),.66min(+).0=+7:1,kkTkkkkkkkkkzf xpxpf xps txxpkk 第第 步步： 判判断断精精度度 若若则则停停止止迭迭代代. .输输出出否否则则以以为为搜搜索索方方向向转转第第 步步. .第第 步步：作作一一维维搜搜索索. .首首先先计计算算，然然后后作作一一维维搜搜索索： ；求求得得最最优优解解，令令第第 步步：置置返返回回第第2 2步步. .2212121212(0)

33、12min( )(6)(2)243212.00=(2,3)0.0010.001.Tf xxxxxxxs txxx + +；取取，(0)(0)1(0)2(0)3(0)4(0)1=(2,3)()=22 34()=3 22 312()=20()=301=Txg xg xg xg xxAb 解解：将将代代入入约约束束条条件件因因此此第第1 1、2 2个个约约束束为为点点的的起起作作用用约约束束故故-4-4， -12-1212(0)1(0)1212121212(,)min()0.011,1,2.0,( )(212,24)()( 8,2)min8220320.1111TTjTTpd dzf xpA ps

34、tEpdjEf xxxf xzdddddds tdd 令令，求求解解线线性性规规划划： 因因为为, ,故故. .故故求求解解线线性性规规划划: : 11221212121212121,1.82min82213252.200ydydzyyzyyyyyyys tyyy 做做变变量量代代换换：令令则则+6+6故故上上式式化化为为： +6 +6引引入入松松弛弛变变量量标标准准化化：121231241526(0)121122(1)(0)(0)min8221325.220, 1,2,6522,0,3321,113222233313jzyyyyyyyys tyyyyyjyyzdydyxxp +6 +6用用单

35、单纯纯形形法法解解之之，得得：故故：因因此此(0)(0)222(0)(0)(1)(1)22222,3313min31min()min().0321333100()(4)(1)()391313bbA xpA pf xpf xs tf x 作作一一维维搜搜索索：所所以以求求解解规规划划式式： 因因为为*(1)1(1)(0)(0)(1)1(1)(1)1(1)(1)1(1)233100,(()613136040()(,) ,()131348636()=24131313486()=-32121313Tfxxxpf xf xf xxg xg x 故故求求得得最最优优值值：故故因因

36、此此再再对对寻寻找找可可行行下下降降方方向向. .(1)3(1)41112(1)12121248()=0136()=013( 3, 2),12(,)6040min()1313320.1111TTg xg xAbpd dzf xpdddds tdd 因因此此令令，求求解解线线性性规规划划： 112212123142526*(2)12*116040100min1313133252.220, 1,2,55,0,0.-3486100(,) ,()13 1313jTydydzyyyyyyys tyyyyyjyyzxxf x 引引入入变变量量，且且添添加加人人工工变变量量后后，可可化化成成下下述述规规划划

37、： + +用用单单纯纯形形法法解解之之，得得：故故是是库库恩恩 塔塔克克点点. .故故： ( )( )( )( )( )( )( )min(+).0sup|(+)0,1,2,kkkkkkkkixppf xps tg xpim 设设对对于于规规划划(5)(5)式式，通通过过求求解解线线性性规规划划(8)(8)式式，得得到到了了及及可可行行下下降降方方向向. .现现要要沿沿方方向向进进行行一一维维搜搜索索，求求得得，即即求求解解：其其中中 (0)( )( )( )( )( )( )( )( )( )1: 0.():()|()0,0()()()()kkkkikkkkkxDkxI xI xi g xi

38、mI xf xxI xf x 1 12 21 1约约束束为为非非线线性性函函数数时时，非非线线性性规规划划式式的的可可行行方方向向法法的的计计算算步步骤骤如如下下：第第 步步：给给定定初初始始可可行行点点，允允许许误误差差00，00，并并置置 第第2 2步步：确确定定点点处处的的起起作作用用下下标标集集 (1) (1)若若为为空空集集，而而且且，则则停停止止迭迭代代，得得到到近近似似极极小小值值. .(2)(2)若若为为空空集集，但但( )( )()kkpf x 1 1，则则取取搜搜索索方方向向=-=-，然然后后转转第第5 5步步. .( )( )( )( )()()kkkkkI xxDI x

39、p 因因为为为为空空集集，表表明明是是可可行行域域 的的内内点点，因因此此任任一一方方向向均均是是可可行行方方向向，类类似似于于无无约约束束问问题题，故故可可用用最最速速下下降降法法寻寻求求下下一一个个迭迭代代点点，但但毕毕竟竟不不是是真真正正的的无无约约束束问问题题，步步长长要要受受到到可可行行域域边边界界的的限限制制. . (3) (3)若若不不为为空空集集，转转第第3 3步步. .第第3 3步步：求求解解线线性性规规划划问问题题(8)(8)式式. .设设求求得得最最优优解解为为(,).(,).( )( )( )( )( )( )(1)( )( )4-:1kkkkkkkkkkkkkxxxp

40、ppxxpkk 2 2第第 步步：判判断断精精度度. .若若 ，则则停停止止迭迭代代，因因为为0 0，说说明明在在点点处处找找不不到到可可行行下下降降方方向向，可可以以认认为为是是一一个个库库恩恩 塔塔克克点点（假假定定也也是是一一个个正正则则点点）；否否则则以以为为搜搜索索方方向向，转转第第5 5步步. .第第5 5步步：在在点点处处沿沿搜搜索索方方向向作作一一维维搜搜索索，确确定定可可行行的的最最优优步步长长. .计计算算： 第第6 6步步：置置，返返回回第第2 2步步. .min( )( )0,1,2,.(1)( )0,1,2, .,( ),( ),( ).ijnijf xg xims

41、th xjlxRf xg x h xD 考考虑虑问问题题：；其其中中均均存存在在一一阶阶连连续续偏偏导导数数，记记其其可可行行域域为为( )(1)( ),( ),( )min()(ikjkf xg xh xxf xf x ( )( )近近似似规规划划法法的的基基本本做做法法：将将问问题题式式中中的的在在点点处处作作一一阶阶泰泰勒勒展展开开，并并取取其其线线性性近近似似，从从而而得得到到线线性性近近似似规规划划，并并对对其其变变量量的的取取值值范范围围加加以以限限制制因因为为用用线线性性函函数数逼逼近近非非线线性性函函数数时时，一一般般只只在在展展开开点点附附近近的的近近似似程程度度较较好好，远

42、远离离展展开开点点，可可能能产产生生较较大大偏偏差差，特特别别是是函函数数的的非非线线性性程程度度较较高高时时，会会产产生生偏偏差差更更大大因因此此需需要要对对变变量量的的取取值值范范围围加加以以限限制制可可得得到到下下列列线线性性规规划划问问题题：+ +( )( )( )( )( )( )( )( )( )( )()()01,2,.()()01,2,(2),1,2,kkkkkiikkkjjkkjjjx xg xg xxxims th xh xxxjlxxjn （ - -）（），（），( )( +1)( +1)( +1)( )( +1)( +1).(1)=1,2,kjjkkkkkjjkjxxx

43、jxxjnx 上上述述线线性性规规划划中中最最后后一一组组不不等等式式约约束束，即即是是对对变变量量 所所施施加加的的限限制制，其其中中是是 中中第第 个个分分量量，是是预预先先给给定定的的变变量量限限制制范范围围，称称为为步步长长限限制制量量. .求求解解上上式式，设设得得到到的的最最优优解解为为若若是是原原问问题题式式的的可可行行解解，则则在在这这一一点点再再将将目目标标函函数数与与约约束束条条件件函函数数线线性性化化，并并沿沿用用步步长长限限制制：（）. .若若不不属属于于原原问问题题的的可可行行域域，则则减减小小步步长长限限制制量量，取取：( )=1 11,2,.2 4.kjjn （）

44、，一一般般 取取， 等等值值 重重新新求求解解当当前前的的线线性性规规划划问问题题(0)( +1)( )12( )( )( )( )( )( )( )( )( )1=1,2,.: 0min()()()()01,2,.()()01,2,kkjjkkkkkkiikkkjjjjxjnkf xf xx xg xg xxxims th xh xxxjlxx 第第 步步：给给定定初初始始可可行行点点，步步长长限限制制（），缩缩小小系系数数(0,1).(0,1).允允许许误误差差置置. .第第2 2步步：求求解解线线性性规规划划问问题题：+ +（ - -）（），（），( )( ),1,2,.kkjjnx 求

45、求得得最最优优解解(1)( )( )(1)( )1(1)( )2( )2(1)(1)(1)( )3,1,2, ,()(),1,2,1,2, .:1kkkjjkkkkkjkkkkjjxxxjnf xf xxxjnxxjnkk 第第 步步：若若 满满足足原原问问题题的的可可行行性性，则则令令= = ，转转第第4 4步步；否否则则 置置:=:=，返返回回第第2 2步步. . 第第4 4步步：若若 ，且且满满足足 或或 11（如如取取 = = 或或1010），允允许许误误差差，令令第第 步步：求求解解罚罚函函数数的的无无约约束束极极小小化化问问题题. .以以为为初初始始点点，选选择择适适当当的的方方法

46、法求求解解，得得其其极极小小点点第第 步步：判判断断精精度度. .在在点点，若若罚罚项项 00，置置第第步步：构构造造障障碍碍函函数数第第步步：求求解解障障碍碍函函数数的的无无约约束束极极小小化化问问题题以以为为初初始始点点，求求解解min min 得得其其极极小小点点式式中中是是可可行行域域中中所所有有严严格格内内点点的的集集合合( )(*)+111( )( -1)( )(1)=:+11ln( )( )-()- ().kkkmmkkiiiikkkkxxrrkkrrg xg xxxf xf x 第第4 4步步：判判断断精精度度. .若若收收敛敛准准则则得得到到满满足足，则则迭迭代代停停止止，取取作作为为原原问问题题极极小小点点的的近近似