最优化方法之_罚函数法讲解.

最优化方法Optimization第十三章罚函数法外点罚函数法罚函数法内点罚函数法乘子罚函数法外点罚函数法mixgtsxfAi,,2,10)(..)(min)()},,2,1(0)(|{上连续。在),,,2,1)((),(其中mixgxREmixgxfini引入罚项0当0)(0当0)(是连续函数，且满足)(其中)()(1yyyyyxgxpmii2)(,0min)(的典型取法：函数xgxgiimixgtsxfi,,2,10)(..)(min)()(),(minxMpxfxFmiixgMxfMxF1)()(),(min是很大的正数。其中M01)(..)1()(min:例22221xxgtsxxxf1)1()1(1)1()1(,0min)1(),(解：定义罚函数222222122221222221xxMxxxxxxMxxMxF1)1(2212)1(222222211xxMxxxxFxxF)()11()11()()(得0FF令2121MMMxxMxxx12212min..0xxstxx222121)(),(解：定义罚函数xxMxxMxF)2)((21)(21222122211xxxxFxxxF2141时，有当21141得00令212121xxxMxxFxF0)(0)(..)(min12221121xxgxxxgtsxxxf21222121,0min,0min),(解：定义罚函数xMxxMxxMxF2212112211,0min21,0min,0min221xxMxFxxxxMxF00时，有当21)22(12210)(2102)(41得00令212212211221121xxMMMxMxxxMMxxxMxxFxF步骤:。1，置0，允许误差1系数，放大)1(0，初始罚因子给定初始点.111)0(kcMMx。设其极小点为)()(min问题为初始点，求解无约束以.2)()1(kkkxxpMxfx。2，返回1:，置令；否则，，则停止计算，得到点)(若.31)()(kkcMMxxpMkkkkk例:用外点法求解02..)1(min2xtsx2)2(202,0min)(，令1,0解：取221)0(xxxxxpMx第一次迭代23解得：2)2(1)1(2)1(),(其中)(1)1(),(min：求解无约束最优化问题)1(222121xxxxxxMxFxpxMxF1010令12MM121(1)x第二次迭代10010令23MM121(2)x1121解得：2)2(1)1(2)1(),(其中)(10)1(),(min：求解无约束最优化问题)2(222222xxxxxxMxFxpxMxF第三次迭代101201解得：2)2(100)1(2)1(),(其中)(100)1(),(min：求解无约束最优化问题)3(222323xxxxxxMxFxpxMxF，，，，以此类推，得序列：100120011012011121232外点罚函数法的一个重要特点:.规划的最优化且外点法也可用于非凸,点可任意选择初始,内进行优化是在整个空间),(函数nEMxF缺点:;在的二阶偏导数一般不存)(惩罚项.1xMp;,.2不能作为近似解可行解外点法的中间结果不是.使搜索产生极大困难,罚函数性质变坏可能使.很大罚因子,接近最优解时当点.3)(kkMx内点罚函数法mixgtsxfi,,2,10)(..)(min是连续函数。其中),,2,1)((),(mixgxfi基本思想:迭代总是从内点出发,并保持在可行域内部进行搜索.niExmixgxS,,,2,1,0)(|int|()0,1,2,,,niSxgximxE障碍函数)()(),(xrBxfrxG。趋向可行域边界时，当点是连续函数；它满足两个条件：定义在可行域内部，是很小的正数，其中)()2()()1()(xBxxBxBr两种最重要的形式:miimiixgxBxgxB11)(ln)()(1)(对数障碍函数障碍因子倒数障碍函数min..10xstx1(),1(,)1BxxrGxrxx取则内罚函数为210(1)()10()1*.Grxxxxrrrxrx令得到当时，有两种障碍函数的比较min..10xstx()ln1,(,)ln1BxxGxrxrx取则内罚函数为101()10()1*.Grxxxxrrrxrx令得到当时，有两种障碍函数的比较例:考虑约束优化问题1..2minxtsx)1ln(2),(xrxrxG该问题的对数障碍函数为(,):121(0)11(,)ln2(0)22rrGxrxrrGxrrrrr的最小点为mixgtsxfi,,2,10)(..)(minSxtsxrBxfrxGint..)()(),(minSxtsxBrxfrxGkkint..)()(),(min的障碍因子数列。为严格单调减且趋于其中0kr步骤:。置缩小系数，初始参数，允许误差给定初始点1),1,0(,0int.11)0(krSx。设其极小点为题为初始点，求解下列问以)()1(int..)()(min.2kkkxSxtsxBrxfx。，返回，置令；否则，，则停止计算，得到点若21:)(.31)()(kkrrxxBrkkkkk例:用内点法求解下列问题00..min122121xxxtsxx212121122112121212(,)lnln210,10311118,1184280*(0,0)kkkkkkkkTkGxrxxrxxrxxrrrGGxxxxxxxrxrxrrx解：定义障碍函数令当时，12131118,118428kkrxrxr12()()110.51.2520.50.3090.59530.250.1830.28340.10.0850.10750.000100kkkrxrxrx4x3x2x1求初始内点的迭代步骤。置如取任取0:),1(0,.100)0(krrExn.1,0)(|,1,0)(|.2)()(mixgiTmixgiSkikkik令。，停止计算；否则，转若4.3kSkikkTiikSiikTixgxRrxgrxgrxPkk0)(|~)0()(1)(),(~.4记构造函数。，转得的极小点域内，求障碍函数为初始点，在以6~..),(~min:),(~~.5)1()(kkkkkkxRxtsrxPrxPRx。转，置如取令21:,1010.611kkrrrrkkkk内点罚函数法优点内点罚函数法缺点迭代总在可行域内进行，每一个中间结果都是可行解，可以作为近似解。选取初始可行点较困难，且只适用于含不等式约束的非性性规划问题。