第三章罚函数法及改进算法
第3章罚函数法及改进算法
3、1 引言
罚函数法就是解决约束优化问题得重要方法,它得基本思想就是用无约束问题代替约束问题,因而无约束问题得目标函数必须就是原来得目标函数与约束函数得某种组合,类似线性规划中得M法求初始可行解,在原来得目标函数上加上由约束函数组成得一个“惩罚项”来迫使迭代点逼近可行域,所以称为罚函数法。这样把约束问题转化成求解一系列得无约束极小点,通过有关得无约束问题来研究约束极值问题,从而使问题变得简单。许多非线性约束优化方法都要用罚函数作为评价函数来评价一个点得好坏,这在选择新点确定步长等方面都起着重要得作用,不同得罚项对算法影响很大,根据罚项得不同可以分为以下几类:
外罚函数法
对于问题
(3-1)
(3-2)
(3-3) 其中为线性连续函数。
定义外罚函数为:
(3-4)
(3-5) 通常取,这样定义得外罚函数法,当为可行点就是,;当不就是可行点时,。而且离可行域越远得值越大,它优点就是允许从可行域得外部逐步逼近最优点,但其明显得缺点就是它需要求解一系列无约束极小化问题,计算工作量很大,且由于其收敛速度仅就是线性得,往往需要较长得时间才能找到问题得近似解,
再考虑到实际中所使用得终止准则,若实现不当,则算法很难找到约束问题得一个较好可行解,从而不适用于那些要求严格可行性得问题。
内罚函数法
它就是针对不等式约束(3-1)(3-3)提出得,基本思想就是在约束区域得边界筑起一道“墙”来,当迭代点靠近边界时,函数值陡然增大,于就是最优点被挡在可行域内部,这样产生得点列每个点都就是可行点。通常定义内罚函数为:
(3-6)
(3-7) 要减弱得影响,故令逐渐增大。内罚函数法得好处就是每次迭代得点都就是可行点,当迭代到一定阶段时,可以被接受为一个较好得近似最优解。但就是内点罚函数法要求初始点位于可行域得内部,除特殊情况外,确定这样一个初始点并非易事。此外,由于内点罚函数不就是处处有定义或不一定存在全局极小,故无约束最优化问题中得线性搜索方法不再适用,另外,当接近可行域边界时,内点罚函数法必须修正通常得线性搜索方法。
由于内点罚函数法不能处理等式约束,且寻求初始可行点得计算工作量往往太大。因此,在实际中,为了求解一般得非线性约束优化问题,人们往往将内点罚函数法与外点罚函数法结合起来适用。
混合罚函数法
混合罚函数法就是针对问题(3-1)-(3-3)提出来得,当初始点给定后,对等式约束与不被满足得那些不等式约束用外罚函数法,而被满足得那些不等式约束用内罚函数法。
通常定义混合罚函数为:
(3-8)
(3-9)
精确罚函数法
对于外点罚函数法与内点罚函数法来说,其工作量很大,收敛慢得主要
原因就是它们需要求解一系列得无约束优化问题,而导致相应罚函数得无约束极小化运算越来越难于精确执行,效率差则就是因为需要罚因子趋于无穷大或零所带来得罚函数呈病态问题。由此自然想到,能否设计出一种罚函数,使得只要令其中得罚参数取适当得有限值后,该罚函数得无约束极小点就恰好就是原约束问题得最优解,从而克服外、内点罚函数法得缺点呢？通常称这样得罚函数为精确罚函数。
对问题(3-1)-(3-3),定义如下
,
,
对于罚函数
其中就是罚因子。如果
则在二阶充分条件
,,
得假定下可证就是罚函数得局部严格极小点。所以罚函数也常称为精确罚函数。同理,罚函数也就是精确罚函数。
乘子罚函数法
内外罚函数法得缺点就是需要罚因子趋于无穷大才能使求解罚函数得极小与求解原向题等价。乘子罚函数法具有不要求初始点为严格内点,甚至不要求其为可行点得特点,它利用近似Lagrange乘子,求其近似解,并且逼近最优解,而不需要无穷大得罚因子,因此对它得研究有重要得理论与实用价值。
最早得乘子罚函数(又称为增广Lagrange函数)就是由Henstenes(1969)针对等式约束问题(3-1)(3-2)导出得,其形式为:
(3-10) 增广Lagrange函数得另一种等价形式就是在1969年由Powell提出得,它提出对进行平移,即用代替,就是参数,这种平移得好处就是不破坏得方向,由此Powell(1969)得到罚函数:
(3-11) 如果定义,则知式(3-10)与(3-11)只相差与无关得项,由于式(3-10)与(3-11)等价,故罚函数(3-10)也称为Henstenes-Powell罚函数。
我们瞧到通常都就是用二次罚函数作为罚项,因此称之为二次罚函数乘子法。然而,它得缺点就是容易引起罚因子过大,造成罚函数得Hesse矩阵严重病态。
许多非线性约束优化方法都要用某个罚函数作为评价函数来评价一个点得好坏,这在选择新点确定步长等方面都起着重要得作用,因此对不同罚项得研究具有重要得理论与实际价值。近年来,许多研究者试图通过改变罚项构造出新得罚函数,有效地避免罚因子过大引起得罚函数得Hesse矩阵严重病态得情况。
3、2 优化中得罚函数法
对一般约束最优化问题
(3-12)
(3-13)
(3-14) 定义1称
(3-15) 为问题(3-12)-(3-14)得优化罚函数,为罚因子,其中罚项
(3-16) 其中且满足如下性质:
(1) 在中连续可微且为对称凸函数;
(2) 对,;当且仅当时,;
(3),。
若定义
则就是可行点当且仅当。
我们通过得极小点(其中为一定值),得到相应无约束极小点,序列来逼近约束问题(3-12)-(3-14)得极小点。
罚函数算法:
步 1 选定初始点为;选取初始惩罚因子(可取),惩罚因子得放大系数(可取);置。
步2 以为初始点,求解无约束问题,
其中,设其极小点为。
步3 若,则就就是所要求得最优解,停止;否则转下一步。
步4 置;,转步2。
由罚项得特点,当趋向于无穷时,随着得不断增大,对每个不可行点得惩罚也不断增大并趋向于无穷。因此,在对应于得无约束极小化问题得最优解处,得值应不断减小,从而保证逐步趋于可行并最终达到问题(3-12)-(3-14)得最优解。由,得定义及极小点得含义,我们很容易证明下列结论。
引理1 给定,就是(3-15)得解,则也就是约束问题
(3-17)
(3-18) 得解,其中。
证明由得性质知在就是增函数,且,又因为为对称函数,所以,,由此可得
对任何满足式(3-18),由得定义,我们有
(3-19) 所以
(3-20) 故知就是问题(3-17)-(3-18)得解。
证毕。
由以上引理可知,若取充分小,则当算法迭代结束时,就是问题(3-12)- (3-14)得近似解。
引理2对于由算法所产生得序列总有,
(3-21)
(3-22)
(3-23) 其中。
证明由与可知,
又因为就是得极小点,所以对于任意总有,特别有
。
由此可证得(3-21)。
因为与分别使与取极小,所以有
由上式可得
由此可得
由于,所以(3-22)成立。
最后,由式(3-21)与(3-22)得式(3-23)成立。
证毕。
定理1设非线性约束问题(3-12)-(3-14)得最优解存在,设由算法产生,且罚参数序列单调递增且趋于,则得任何极限点都就是问题(3-12)-(3-14)得可行域上得最优解。
证明设,又设就是问题(3-12)-(3-14)得最优解,由于就是无约束问题
得解,由于可行,即,故有
即
由此可得,由于,。故得
,且。
即可行,且,但就是问题(3-12)-(3-14)得解,因此也就是问题(3-12)-(3-14)得解。
证毕。
我们现在对于优化中得罚函数法进行一般类型得概况,并证明其收敛性,但就是需要说明得就是其中不同种类得罚函数法在其收敛速度各有其不同。
3、3 改进得罚函数法及收敛性
3、3、1 改进得罚函数算法
罚函数法就是解决约束优化问题得重要方法,它得基本思想就是把约束优化问题转化成求解一系列得无约束极小化问题。通过有关得无约束问题来研究约束极值问题,经常采用得方法之一就是在原来得目标函数上加上由约束函数组成得一个“惩罚项”来迫使迭代点逼近可行域,这种方法称为罚函数法。如何选取罚函数,以加速迭代算法得收敛速度,一直就是约束优化问题研究得热点问题。
罚函数作为评价函数来评价一个点得好坏,这在选择新点确定步长等方面都起着重要作用,不同罚项得选取,构成不同得罚函数,必然会对算法产生不同得影响,因此对不同罚项得研究具有重要得理论与实用价值。
对一般约束最优化问题
(3-24)
(3-25)
(3-26) 通常使用得外函数形式为:
其中罚项为:,。为参数,若取,我们称上述罚函数为二次罚函数。
问题(3-24)-(3-26)得可行域为
显然,当为可行点时,;当不就是可行点时,,而且离可行域越远得值越大。它得优点就是允许从可行域得外部逐步逼近逼近最优点,但按上述定义得罚函数得缺点就是:需要罚因子趋于无穷大,才可能使求解罚函数得极小与求解原问题等价。
为了有效得改善这种罚函数,我们试图构造一种能够加速迭代算法收敛得外罚函数法。本文提出一种用双曲正弦函数作罚项得罚函数,并由此构建了双曲正弦罚函数法,不仅证明了该罚函数与算法得合理性及迭代点列得收敛性,而且做了数值实验。结果表明本文中所提出得罚函数及对应得算法可以在罚因子与二次罚函数方法中得罚因子相同得情况下,有着更快得收敛速度。
定义1称
(3-27) 为问题(3-24)-(3-26)得双曲正弦罚函数,为罚因子,其中罚项
(3-28) 其中,;,。
若定义
则就是可行点当且仅当。
我们通过一系列双曲正弦函数得极小点,其中为一定值,得到相应无约束极小点,序列来逼近约束问题(3-24)-(3-26)得极小点。
双曲正弦罚函数算法:
步 1 选定初始点为;选取初始惩罚因子(可取),惩罚因子得放大系数(可取);置。
步2 以为初始点,求解无约束问题
其中
设其极小点为。
步3 若,则就就是所要求得最优解,停止;否则转下一步。
步4 置;,转步2。
3、3、2 收敛性证明及数值试验
引理1 设函数与由定义1定义,由算法产生,且罚参数序列单调递增,则
证明
由得定义知
上面得两式相加,得
因此,即成立。
由得
即成立。
由以及得定义得
即成立。
证毕。
引理2 设函数与由定义1定义,由算法产生,且罚参数序列单调递增,记,则也就是约束问题
(3-29)
得解。
证明设就是问题(3-29)得可行点,我们有
因此就是问题(3-29)得解。
证毕。
定理1设非线性约束问题(3-24)-(3-26)得最优解存在,设由算法产生,且罚参数序列单调递增且趋于,则得任何极限点都就是问题(3-24)-(3-26)得可行域上得最优解。
证明设,又设就是问题(3-24)-(3-26)得最优解,由于就是无约束问题,得解,由于可行,即,故有
即
由此可得,由于,。故得,且。即可行,且,但就是问题(3-24)-(3-26)得解,因此也就是问题(3-24)-(3-26)得解。
证毕。
我们通过数值实验来检验本算法得有效性
在以下“次数”得就是求解相应无约束问题得次数,“”与“”分别表示双曲正弦罚函数法与二次罚函数法。就是程序结束时所取罚因子,用matlab 编程实现。
表3-1两种方法得数值比较:
Table 3-1 the numerical parison of the two methods
由以上结果可以瞧出本文中构造得双曲正弦罚函数较二次罚函数法有明显得改进:其在相同较大罚因子得条件下,双曲法得次数明显减少。
3.4本章小结
本文主要就是介绍不等式优化问题得罚函数法,为了改进算法,将罚函数法中得罚项用双曲正弦函数代替,提出了一种罚函数得改进算法,并进行了收敛性证明,同时与二次罚函数法进行数值试验比较,说明了改进算法在收敛速度上有一定程度得改进。