最优化理论与算法(第十章)VIP专享

第十章 罚函数法 罚函数是利用目标函数与约束函数一起构成的具有惩罚性质的函数。当约束条件被破坏时，施以惩罚，可以想象，当这种惩罚很大时，将迫使迭代点趋于可行点。 §10.1 外罚函数法 对一般非线性规划问题： 1min( )( )01,,. ( )0,,ieiefxcxims tcximm （10.1） 定义违反约束度函数： () ( )( )1,iiecxcxim （10.2） ()1( )m in{0,( )} ,miiecxcxim。 （10.3） 罚函数一般表示为： ()( )( )(( ))P xfxh cx （10.4） 其中()(( ))h cx是惩罚项，这个函数一般具有 (0)0h，lim( )ch c   。 较常用的形式为： ()( )( )( )P xfxcx （0 称为罚因子） （10.5） 注：1) 在上式中，范数常取为2 ，若取为 或1 会导致( )P x不光滑。 2) 当取2 和1 时，( )P x 的光滑性可由 ()22(( ))(m in{0,( )})icxcx 直接验证。事实上，在“转折点”处，可证得左、右导数均为 0，由此可得()2(( ))cx光滑性，从而( )P x 光滑。 Courant函数是最早使用的罚函数，也是最方便最重要的一种罚函数。其形式为 2()2( ,)( )( )p xfxcx 1221`( )( )(min{0,( )})eemmiiimfxcxcx （10.6） 以下考虑一般的罚函数问题 ()( ,)( )( )p xfxcx （10.7） 并且以后总用()x 表示罚问题  minnxRPx 的解。 引理 1 设210，则必有 21( ())( ())fxfx ()()21( ())( ())cxcx。 注：随着罚因子的增大，惩罚的力度加大， ()x 将越来越靠近可行域（相当于取点范围不断减小），自然( ())fx 会不断增加。 引理 2 令() ( ())cx，则()x 是约束问题 ()min( ). . ( )nxRfxs tcx （10.8） 的最优解。 证明：用反证法证明。若不然，容易构造出一个关于罚函数问题更好的解，导致矛盾。 由于原问题等价于 ()min( ). . ( )0nxRfxs tcx （10.9） 而当  很小时，（10.8）是（10.9）的近似，从而 ()x 可看成是原问题的近似解。特别地，当() ( ())0cx 时，()x 是原问题的精确解。 罚函数法的基本思想是：每次迭代增大罚因子 ，直到() ( )cx缩小到给定的范围内。由于要求解一系列无约束问题，故也称为 SUMT 外点法(Sequen...