第4讲+非线性规划

第四节非线性规划模型的解•二次插值法•最速下降法•罚函数法非线性规划模型的一般形式：一、无约束模型:}|)(min{nRXXf二、有约束模型：)(minXfmiXgtsi,,2,1,0)(.pjXhj,,2,1,0)()()(XfXf),(XNSX若,SX若则称为局部最优解，X或局部解；则称为整体最优解，X或最优解或解一、无约束模型的解}|)(min{nRXXf沿某直线方向求目标函数的极小值点，称为一维搜索。高维问题可通过一系列的一维搜索，求出其近似最优解。}|)(min{Rxxf一维搜索沿某些方向作一维搜索)(minXfmiXgtsi,,2,1,0)(.pjXhj,,2,1,0)(化为无约束问题讨论顺序：1.一维搜索（二次插值法）],[),(baxxf单峰函数满足设,321xxx)()()(321xfxfxf或)()()(321xfxfxf1x2x3x)(xf)(xgx过三点作抛物线：2210)(xaxaaxg有)()(12121101xfxaxaaxg)()(22222102xfxaxaaxg)()(32323103xfxaxaaxg,jixx0111233222211xxxxxx故方程组有唯一解，且02a即抛物线的开口向上。令02)(21xaaxg得极小值点212aax再从中选出满足前面不等式的三点，xxxx,,,321重复前面的过程，直到满足终止条件：2131||,|)()(|xxxgxf则xx注：迭代时，若出现退化情形2xx,221xxx可取继续迭代。#2.最速下降法Xf(X)D=－f(X)第1步求新点设f(X)可微，给定初始点X1,0,每次沿使f下降得最快的负梯度方向D=－f(X)搜索，直到满足终止条件为止。第k次迭代令)(kkXfD使求k)(min)(0kkkkkDXfDXf注意：k不是步长（因Dk不是单位向量），且非负（否则，不是下降得最快的方向）。得新点kkkkDXX1设已得Xk第2步验证终止条件,,)(11kkXXXf则若处的最大变化率。在是11)()(kkXXfXf否则，将Xk+1作为新的出发点，作为新的迭代方向，进行下一次迭代。)(11kkXfD有结论：1kkDD因为kdDXfdkk)(kkDXf)(1kkDD1kkkkkkDDXdDXfd)()(0可见，搜索路线呈之字形。该法的优点是：不论维数多高，每次迭代只沿一个方向搜索。“较圆”时，则收敛得较快；“较扁”时，则收敛得较慢。当目标函数等值线X•实际中，前面阶段可用最速下降法，后面阶段用旋转方向法。缺点是：收敛速度“前快后慢”。例求解2212221222)(minxxxxxXf解TxxxxXf)224,22()(1221,)0,0(3.01TX初始点，＝因,)2,0()(1TXf2)(1Xf所以令,)2,0()(11TXfDTDX)2,0(11则有)2,0()(11fDXf482120110}48{min)(min的现求使DXf由,0416f411＝得得新点：1112DXXT)21,0(TT)2,0(41)0,0(第1步第2步因,)0,1()(2TXf1)(2Xf令TXfD)0,1()(22沿方向搜索，得2D212迭代：经5次迭代后得解点,)87,43(6TX,)0,41()(6TXf41)(6XfTX)87,43(故得近似最优解：而本题的精确最优解是：T)1,1(搜索过程见P.32表1.11。例1.24例1.23)6,5()1,1(罚函数法)(minXfmiXgtsi,,2,1,0)(.pjXhj,,2,1,0)(利用约束函数，引入辅助函数nRXXMXfMXF),()(),(值迭代。加大时为所求，否则当的求使MSMXMXMXFnRX)(),()},({min思路：二、有约束模型的解构造非负函数：,0,0,0)(2ttttu0)(),(0)(,0)]([2XgXgXgXguiiii,))](,0[min(2XginRX0)(),(0)(,0)]([2XhXhXhXhvjjjj,)]([2XhjnRX作罚函数：,)]([)]([)(11pjjmiiXhvXguXnRX时；当SX,0.,0时当SX所有约束都满足至少有一个不满足0,0,0)(2ttttv作辅助函数：)()(),(XMXfMXFmiiXgMXf12))](,0[min({)(,})]([12pjjXhnRX罚因子(充分大）原模型化为无约束模型：}|),(min{nRXMXF对给定的M1,求得最优解X1=X(M1)•当时，SX11XX)0(•当时，SX1否则，加大罚因子，迭代，…12MM若满足终止条件)(11XM（X1近似可行）;1XX则可以证明：对于kMMM210XMXMSkk外从时，解点列当)}({因此，该方法也称为外点法。#例用罚函数法求解21)(minxxXf0)(0)(.122211xXgxxXgts解构造辅助函数})],0[min()],0{[min(),(21222121xxxMxxMXF2RX在图中阴影区域内（S外的点），用微分法求F的极小值点。即0)(0)(122211xXgxxXgS令02)(41122111MxxxMxxF}){(),(21222121xxxMxxMXF0)(212212xxMxF)1()2(,212212Mxx）式解得：由（,)1(2111Mx）式得：代入（MMx21)1(41:22从而得＃注：若不便用微分法求解，则可用无约束模型的搜索法对给定的Mi（或任意的M）求X(Mi),用终止条件终止计算。TMMMMX21)1(41,)1(21)(2)()0,0(MXT的解：}|),(min{2RXMXF变化过程见P.35另外：还有混合罚函数法、内点法等。＃