第3章 罚函数法及改进算法3.1 引言罚函数法是解决约束优化问题的重要方法，它的基本思想是用无约束问题代替约束问题，因而无约束问题的目标函数必须是原来的目标函数与约束函数的某种组合，类似线性规划中的M 法求初始可行解，在原来的目标函数上加上由约束函数组成的一个“惩罚项”来迫使迭代点逼近可行域，所以称为罚函数法。
这样把约束问题转化成求解一系列的无约束极小点，通过有关的无约束问题来研究约束极值问题，从而使问题变的简单。
许多非线性约束优化方法都要用罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，不同的罚项对算法影响很大，根据罚项的不同可以分为以下几类：外罚函数法对于问题min ()f x (3-1).s t ()0i c x = 1,2,,;i m =⋅⋅⋅ (3-2)()0i c x ≥ 1,2,,;i m m n =++⋅⋅⋅ (3-3)其中:n f R R →为线性连续函数。
定义外罚函数为:(,)L x σ()()f x P x σ=+()()f x Q x σ=+ (3-4)()Q x =11()min{0,()}m ni i i i m c x c x βα==++∑∑ (3-5) 通常取==2αβ，这样定义的外罚函数法，当x 为可行点是，()0Q x =；当x 不是可行点时，()0Q x >。
而且x 离可行域越远()Q x 的值越大，它优点是允许从可行域的外部逐步逼近最优点，但其明显的缺点是它需要求解一系列无约束极小化问题，计算工作量很大，且由于其收敛速度仅是线性的，往往需要较长的时间才能找到问题的近似解，再考虑到实际中所使用的终止准则，若实现不当，则算法很难找到约束问题的一个较好可行解，从而不适用于那些要求严格可行性的问题。
内罚函数法它是针对不等式约束(3-1)(3-3)提出的，基本思想是在约束区域的边界筑起一道“墙”来，当迭代点靠近边界时，函数值陡然增大，于是最优点被挡在可行域内部，这样产生的点列k x 每个点都是可行点。
通常定义内罚函数为：1(,)()()B x f x B x σσ=+ (3-6)11()()m i i B x c x ==∑ (3-7) 要减弱()B x 的影响，故令σ逐渐增大。
内罚函数法的好处是每次迭代的点都是可行点，当迭代到一定阶段时，可以被接受为一个较好的近似最优解。
但是内点罚函数法要求初始点位于可行域的内部，除特殊情况外，确定这样一个初始点并非易事。
此外，由于内点罚函数不是处处有定义或不一定存在全局极小，故无约束最优化问题中的线性搜索方法不再适用，另外，当接近可行域边界时，内点罚函数法必须修正通常的线性搜索方法。
由于内点罚函数法不能处理等式约束，且寻求初始可行点的计算工作量往往太大。
因此，在实际中，为了求解一般的非线性约束优化问题，人们往往将内点罚函数法与外点罚函数法结合起来适用。
混合罚函数法混合罚函数法是针对问题(3-1)-(3-3)提出来的，当初始点0x 给定后，对等式约束和不被0x 满足的那些不等式约束用外罚函数法，而被0x 满足的那些不等式约束用内罚函数法。
通常定义混合罚函数为：111(,)()()()()i I i P x f x P x c x σσσ∈=++∑ (3-8)2221()()min{0,()}m i i i i I P x c x c x =∈=+∑∑ (3-9)1{()0,1,2,,}i I i c x i m m n =>=++ 2{()0,1,2,,}i I i c x i m m n =≤=++精确罚函数法 对于外点罚函数法和内点罚函数法来说，其工作量很大，收敛慢的主要原因是它们需要求解一系列的无约束优化问题，而导致相应罚函数的无约束极小化运算越来越难于精确执行，效率差则是因为需要罚因子趋于无穷大或零所带来的罚函数呈病态问题。
由此自然想到，能否设计出一种罚函数，使得只要令其中的罚参数取适当的有限值后，该罚函数的无约束极小点就恰好是原约束问题的最优解，从而克服外、内点罚函数法的缺点呢？通常称这样的罚函数为精确罚函数。
对问题(3-1)-(3-3)，定义()()()1()((),())T m C x c x c x ---=如下()()()i i c x c x -=，1,2,,i m =⋅⋅⋅()()min{0,()}i i c x c x -=，1,2,,i m m n =++⋅⋅⋅对于1L 罚函数()11()()()P x f x C x σ-=+ 其中0σ>是罚因子。
如果σλ*∞≥则在二阶充分条件0T d W d *>，0d ∀≠，0T A d *=的假定下可证x *是1L 罚函数的局部严格极小点。
所以1L 罚函数也常称为1L 精确罚函数。
同理，L ∞罚函数()1()()()P x f x C x σ-∞=+也是精确罚函数。
乘子罚函数法内外罚函数法的缺点是需要罚因子趋于无穷大才能使求解罚函数的极小和求解原向题等价。
乘子罚函数法具有不要求初始点为严格内点，甚至不要求其为可行点的特点，它利用近似Lagrange 乘子，求其近似解，并且逼近最优解，而不需要无穷大的罚因子，因此对它的研究有重要的理论和实用价值。
最早的乘子罚函数(又称为增广Lagrange 函数)是由Henstenes(1969)针对等式约束问题(3-1)(3-2)导出的，其形式为:2(,,)()()()2T P x f x c x c x σλσλ=-+ (3-10) 增广Lagrange 函数的另一种等价形式是在1969年由Powell 提出的，它提出对()i c x 进行平移，即用()i i c x θ-代替()i c x ，i θ是参数，这种平移的好处是不破坏()i c x ∇的方向，由此Powell(1969)得到罚函数:21(,,)()()(())2m T i ii P x f x c x c x σλσλθ==-+-∑ (3-11)如果定义i i λσθ=，则知式(3-10)与(3-11)只相差与x 无关的项212m i i σθ=∑，由于式(3-10)与(3-11)等价，故罚函数(3-10)也称为Henstenes-Powell 罚函数。
我们看到通常都是用二次罚函数作为罚项，因此称之为二次罚函数乘子法。
然而，它的缺点是容易引起罚因子过大，造成罚函数的Hesse 矩阵严重病态。
许多非线性约束优化方法都要用某个罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，因此对不同罚项的研究具有重要的理论和实际价值。
近年来，许多研究者试图通过改变罚项构造出新的罚函数，有效地避免罚因子过大引起的罚函数的Hesse 矩阵严重病态的情况。
3.2 优化中的罚函数法对一般约束最优化问题min ()f x (3-12).s t ()0i c x = 1,2,,;i m =⋅⋅⋅(3-13) ()0i c x ≥ 1,2,,;i m m n=++⋅⋅⋅ (3-14) 定义1 称(,)k L x σ()()k f x P x σ=+()()k f x Q x σ=+ (3-15)为问题(3-12)-(3-14)的优化罚函数，0σ>为罚因子，其中罚项11()[(())]{(min[0,()])}m ni i i i m Q x q c x q c x ==+=+∑∑ (3-16) ()q t 其中t R ∈且满足如下性质：(1) ()q t 在R 中连续可微且为对称凸函数；(2) 对∀t R ∈，()0q t ≥；当且仅当0t =时，()0q t =；(3) lim ()t q t →+∞=+∞，lim ()t q t →-∞=-∞。
若定义~()()min[0,()]i i i c x c x c x ⎧=⎨⎩ 1,2,,1,2,,i m i m m n ==++ 则x 是可行点当且仅当()0i c x =。
我们通过(,)k L x σ的极小点(其中k σ为一定值)，得到相应无约束极小点，序列{}k x 来逼近约束问题(3-12)-(3-14)的极小点*x 。
罚函数算法：步1 选定初始点为0x ；选取初始惩罚因子10σ>(可取11σ=)，惩罚因子的放大系数1c >(可取10c =)；置1k =。
步2 以1k x -为初始点，求解无约束问题min (,)n k x RL x σ∈， 其中(,)()()()()k k k L x f x P x f x Q x σσσ=+=+，设其极小点为k x 。
步3 若()k Q x σε<，则k x 就是所要求的最优解，停止；否则转下一步。
步4 置1k k c σσ+=；1k k =+，转步2。
由罚项的特点，当k 趋向于无穷时，随着k σ的不断增大，对每个不可行点的惩罚()k Q x σ也不断增大并趋向于无穷。
因此，在对应于k σ的无约束极小化问题的最优解k x 处，()k Q x σ的值应不断减小，从而保证k x 逐步趋于可行并最终达到问题(3-12)-(3-14)的最优解。
由()Q x ，(,)k L x σ的定义及极小点的含义，我们很容易证明下列结论。
引理1 给定0k σ>，k x 是(3-15)的解，则k x 也是约束问题min ()n x Rf x ∈ (3-17) .s t |()|i i c x μ≤ 1,2,,i n = (3-18) 的解，其中~|()|i i k c x μ=。
证明 由()q x 的性质知在(0,)+∞是增函数，且 ~~(|()|)(|()|)i i k q c x q c x ≥，又因为()q x 为对称函数，所以~~(|()|)(())i i k k q c x q c x =，~~(|()|)(())i i q c x q c x =，由此可得~~(())(())i i k q c x q c x ≥ 对任何x 满足式(3-18)，由k x 的定义，我们有~1()(())n i k i f x q c x σ=+∑~1()(())n i k k k i f x q c x σ=≥+∑ (3-19)所以~~1()()[(())(())]()n i i k k k k k i f x f x q c x q c x f x x σ=≥+-≥∑ (3-20)故知k x 是问题(3-17)-(3-18)的解。
证毕。
由以上引理可知，若取ε充分小，则当算法迭代结束时，k x 是问题(3-12)- (3-14)的近似解。
引理2 对于由算法所产生的序列{}k x 总有，11(,)(,)k k k k L x L x σσ++≥ (3-21)1()()k k Q x Q x +≤ (3-22)1()()k k f x f x +≥ (3-23)其中1k ≥。