第10讲 可行方向法和制约函数法

第5章有约束极值问题最优性条件（1学时）二次规划（1学时）可行方向法（1学时）制约函数法（1学时）非线性规划软件求解简介（1学时）应用案例（1学时）可行方向法制约函数法重点：可行方向法的思路；制约函数法的求解步骤。难点:制约函数法的求解基本要求：理解可行方向法的思路；掌握制约函数法的函数构造思路，了解制约函数法的步骤，会用制约函数法中惩罚函数和障碍函数法求解简单有约束极值问题。第8讲可行方向法和制约函数法可行方向法（5.4）可行方向法可看作无约束下降算法的自然推广，其典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点．算法的主要步骤是选择搜索方向和确定沿此方向移动的步长．搜索方向的选择方式不同就形成各种可行方向法．下面给出Zoutendijk可行方向法。设()kX()kX点的起作用约束集非空，为求点的可行下降方向D，D应满足下述不等式：()()()0()0,(1)kTkTjfXDgXDjJ()()()(),(1)0kTkTjfXDgXDjJ()()()(2)(),111,2,...,kTkTjiMinfXDgXDjJdin()(,)kkD解线性规划问题（2）得最优解()kD0k若则()kX即为F-J点停止迭代。若0k则即为可行下降方向。以该可行下降方向进行一维搜索迭代出新点。不等式组（1）等价于存在使得下式成立对于D要求指出方向，而不要求大小，故限定-1di1,且使得的最大值取极小，得到下面线性规划问题:例1用可行方向法求解（书上例5-5）844)(min212221xxxxXf024)(211xxXg解：取初始点TX)0,0()0(于是有8)()0(Xf4242)(21xxXf44)()0(Xf于是有由于04)()0(1Xg由于故约束024)(211xxXg不是初始点)0(X的有效约束。取TXfD)4,4()()0()0(从而有：444400)0()0()1(DXX124844)()1(1Xg0124)()1(1Xg令可得11383232)(2)1(Xf令03264)()1(dXdf12231213121},min{},min{取于是有：TX),(3434)1(98)1()(XfTXf),()(3434)1(0)()1(1XgTXg)2,1()()1(1，，，构造线性规划：为了便于求解令用单纯形法求解，可得最优解),,2(104103Y11d1072d104，，即所以TTddD),1(),(10721)1(TDXX),(1073434)1()1()2(889.04.049.1)(2)2(Xf04.098.2)()2(dXdf134.0所以令得现暂时用该步长计算)2(X有TX)239.1,467.1()2(0055.0)()2(1Xg因为)2(X故为可行点选取是可行的。继续迭代下去，可得最优解134.0TX)2.1,6.1(最优值8.0)(Xf（一）罚函数法（外点法）其中是En的连续函数。(),(),()jifXgXhXmin()..()0,1,...,()0,1,...,jifXstgXjphXim2211min()()[min(0,())]()pmjijiPXfXMgXMhX利用目标函数和约束函数组成辅助函数：0M为罚因子。随着罚因子的增加，P（X）的最优解越靠近可行域，最终趋于所求非线性规划的最优解。*X制约函数法2211()()[min(0,())]()pmjijiPXfXMgXMhX称为罚函数。考虑约束问题1罚函数法的思路通过一系列罚因子构造罚函数，将问题转化为序列无约束极值问题，求罚函数的极小点来逼近原约束极值问题的最优解。2罚函数法的迭代步骤（1）给定初始点,初始罚因子，允许误差及)0(X0M,01C，令k=0。（2）以为初始点，对罚函数进行无约束及极小化，求，得最优解。),(minkMXP)()(kkMX)(kX（3）若存在j，使得，取)mj(0))M(X(gk)k(jkkCMM1并令k=k+1,返回（2），否则停止迭代，并取)(kkMXX例1：用外点法求解非线性规划112221min()00fXxxxxx12221221(,)[min(0,())][min(0,)]PXMxxMxxx构造罚函数解析法求解解：)2()],0[min(2)]2)(,0[min(21112211xMxxxMxP)3(),0min(212212xxMxP（1）取不满足约束条件的点12210,0xxx)1()],0[min(2)]2)(,0[min(21112211xMxxxMxP)3(2)2)(21112211MxxxxMxP则（1）（2）式变为因X*为可行解故为原问题最优解)2(),0min(212212xxMxP取不满足约束条件的点无法求出*MX则（1）（2）式变为取不满足约束条件的点1221+0,0xxx则（1）（2）式变为3罚函数法的优缺点优点（1）程序简单适应性强（2）外点容易求出，等式和不等式约束问题都适用。缺点（1）开始时M不能选得太大，否则可能求不出最优解；M选小了又会增加计算量，（2）每个M求出的都不是可行解。适用场合任何有约束极值问题。（二）障碍函数法（内点法）考虑约束问题krkr利用目标函数和约束函数组成辅助函数，称为障碍函数P（X）。对于障碍因子，选择为一个严格减小趋于零的数列从可行点出发，逐个求解（1）或（2）。111(,)(),(0)(1)()(,)()log(()),(0)(2)lkkkjjlkkjkjPXrfXrrgXorPXrfXrgXr1障碍函数法的思路l2障碍函数法的迭代步骤（1）给定初始点,初始障碍因子，允许误差及)0(X0r,01，令k=0。（2）以为初始点，对障碍函数进行无约束极小化，求，得最优解。),(minkrXP)()(kkrX)(kX（3）若存在j，使得取)0(mipjk)k(jk))r(X(gr11kkrr1并令k=k+1,返回（2），否则停止迭代，并取)(kkrXX例2：用内点法求解非线性规划23131)1()(minxxXf01)(11xXg0)(22xXg解：构造障碍函数21231311)1(),(xrxrxxrXP0)1(211)1(21xrxPx01222xrxP求解rrx1)(1可得：rrx)(2TTrrrX)0,1(),1(lim0min如此求得：3障碍函数法的优缺点优点（1）程序简单适应性强，（2）每步迭代的点都为可行解。缺点（1）内点不容易求出，（2)等式约束问题不适用。。适用场合仅有不等式约束的有约束极值问题。（三）混合罚函数法外点法(惩罚函数法)和内点法(降碍函数法)各有其优缺点；因此，往往将内点法和外点法结合起来使用，称之为混合惩罚函数法。当给定初始点后，对满足的那些不等式约束，按内点法来构造障碍函数，对不满足的那些不等式约束和等式约束，按外点法构造惩罚函数。同时，在算法程序中，为加快迭代，减少计算量，将利用极小点的已知近似值通过外推的途径来提高计算效率。1混合罚函数法的思路在混合惩罚函数法中。增广目标函数的构造为120krrr其中：混合惩罚函数法的终止准则为1()()kkrPxrBx2混合罚函数法的迭代步骤（1）给定初始点,使得初始障碍因子，允许误差及)0(X0r,02c，令k=0。（2）以为初始点，求解无约束及极小化问题，得最优解。)()()(),(min1XBrXPrXfrXFkkk)()(kkrX)(kX（3）极小点外推（4）若满足终止条件，令计算结束，否则，，返回步骤(2)。)(kXX0)(,0)()0()0(XgXhjm)1)(1()(1)2()1()()1()(CCXXCCXCXorCXXCXkkkkk若有JjXgj,...,2,1,0)(,令XXk)(否则舍去X1/kkrrc1kk，，4乘子法（1）等式约束情形考虑问题min()..()0,1,...,ifXsthXim(),(),1,...,ifXhXim211(,,)()()()2mmiiiiicXcfXhXhX为二阶连续可导。设乘子罚函数：c为罚因子。（2）不等式约束情形考虑问题min()..()0,1,...,jfXstgXjp2min()..()0,1,...,jjfXstgXyjp22211min(,,,)()(())(())2ppjjjjjjjcXYcfXgXygXy221min(,,,)()[max(0,()]2pjjjjcXYcfXcgX由（1）上述问题转化为整理后消去yj得：（3）不等式和等式约束情形考虑问题min()..()0,1,...,()0,1,...,jifXstgXjphXim221211min(,,,,)()[max(0,()]2()()2pjjjjmmiiiiicXYcfXcgXchXhX作业：习题53（1）(2），4，5，6（选作）