北邮最优化理论与算法PPT课件：13_惩罚函数法

1、13， 罚函数法最优化理论与算法13 惩罚函数法考虑约束问题 ( ),( )( )ijf x g xh x其中和连续. min( ). . ( )0,1,., ( )0,1,2,.ijf xstg ximh xjl（13.1.1） min( ). . ( )0, ( )0f xstg xh x向量形式11 ( )( ),.,( ) ( )=( ( ),.( )tmtlg xg xgxh xh xg x其中13 惩罚函数法( )0,1,.,. ( )0,1,.,ijg ximdxh xjl令问题的可行域为： 如何求解约束问题？可行方向法：沿下降可行方向搜索其他方法？序列无约束优化算法：通过求解一

2、系列无约束问题的解来近似约束问题的解。罚函数法是序列无约束问题算法的典型代表。13.1 外点惩罚函数法但由于f在可行域d的边界不连续.因此难以直接由求解f的极小值来求问题(13.1.1)的极小点.罚函数法的基本思想基本思想是构造辅助函数f,把原来的约束问题转化为求极小化辅助函数的无约束问题易见约束问题(13.1.1)的解等价于min ( ), nf xxr的解( ),( ),f x xdf xxd例如可以定义函数f:rnr为13.1 外点罚函数法于是构造辅助函数极为重要！于是构造辅助函数极为重要！外点法的基本思想基本思想是构造辅助函数: (0)nfrr(13.1.1),.fdff函数在可行域

3、的内部的取值与问题的目标函数的取值相等 而在可行域的外部取值远远大于目标函数的值,min( )(13.1.1).,min( )( ).fxfxx 换言之 对可行域外部点的目标函数值加以惩罚 使得无约束问题的解是约束问题的近似解且当时问题的解趋于约束问题的解13.1 外点罚函数法 min( ). . ( )0,1,2,.jf xsth xjl（13.1.2）对于约束问题1min( , ) (13.1.4)f x于是(13.1.2)转化为:211( , )( )( ) (13.1.3)ljjf xf xhx可定义辅助函数:参数是很大的正数.13.1 外点罚函数法 min( ). . ( )0,1,

4、2,.if xstg xim对于不等式约束问题(13.1.5)221( , )( )(max0,( ) (13.1.6)miif xf xg x可定义辅助函数:参数是很大的正数.2min( , ) (13.1.7)f x于是(13.1.2)转化为:13.1 外点罚函数法( , )( )( ) (13.1.8)f xf xp x对于一般形式的问题(13.1.1).可定义辅助函数0,00,0( ), ( ).0,00,0yyyyyy11( )( )+( ) (13.1.9)mlijijp xg xh x其中p(x)具有如下形式:连续函数和满足13.1 外点罚函数法连续函数和的典型取法有 (max0

5、,( ) = ( ) (1,1)ijg xh x于是把约束问题(13.1.1)转化为无约束问题其中是很大的正数,p(x)是连续函数min( , )( )( ) (13.1.10)f xf xp x13.1 外点罚函数法21 min( ) . . ( )10 (13.1.11) f xxstg xx 例该问题的可行域d=-,-1,最优解x*= -121221( , )( )(max0,( ) 21 +(max0, (13.1.121) )2miif xf xg xxx令min( , )( )2f xx 的解为( )1*,2xx 13.1 外点罚函数法罚因子的选取非常重要罚因子的选取非常重要!1,

6、 (13.1.13)min (sum),.t( )kkkkfxxxp:取一趋向无穷大的严格递增正数列从某个 开始 对每个求解 从而得到一个极小点的序列在适当条件下 此序列收敛于约束问题的最优解 一般的策略是序列无约束极小化方法 ( )13.1 外点罚函数法(0)1(1)( )( )( ) 1,1,0,1.2, min ( )( )3,(),;.:1,2kkkkkkkxckxf xp xxp xxckkk+1给定初点初始罚因子放大系数允许误差 置以为初点 解无约束问题 得极小点为若停止 得点否则,令 置点法转外13.1 外点罚函数法1.3 收敛性证明:先证1( )(1)1( )( )(1)1(1

7、)(1)1)(13.1.11,(,)(,)2, (0,)()3,()(,)kkkkkkkkkkkkkkf xf xxp xp xf xf xx设和分引别为取罚因子和时无约束问题的极小点 则下列各式成理立( )1( ,),.( , )kkkkxf xf x根据是的极小点由的定义13.1 外点罚函数法证2( )( )( )(1)(1)(1)( )1(1)1(,)()() ()() ()() (,)kkkkkkkkkkkkkf xf xp xf xp xf xp xf x( )(1)1( ,)( ,),kkkkxxf xf x因为和分别为和极小点 则( )( )(1)(1)k()()()()kkkk

8、kf xp xf xp x(13.1.14)(1)(1)( )( )1k+1()()()()kkkkkf xp xf xp x（13.1.15）13.1 外点罚函数法将上两式的两端分别相加并整理得(13.1.16)( )(1)1k1k() ()() ()kkkkp xp x1k,k由故(13.1.17)( )(1)()()kkp xp x最后证3.:( )( ,),kkxf x因为的极小点 则( )( )(1)(1)k()()()()kkkkkf xp xf xp x(13.1.18)13.1 外点罚函数法由(13.1.17)和(1.18)可得:( )( )k( ), (), (,) ()kk

9、kf xf xp x由上引理知 若迭代不终止 则为非减序列,为非增序列.( )(1)()()kkf xf x( )( )( ) (13.1.1),0, (13.1.3)( ,), ( )(,)() (13.1.19)13.1.2kkkkkkxf xxkf xf xf x设 是问题的最优解 且对任意的由定义的存在极小点则对每一个 成立引理13.1 外点罚函数法( )k( )( )( )( ): (0,(,)()()()(13.1.20)kkkkkkkp xf xf xp xf x证明由于则 (13.1.1),( ),( )0 xp xp x 由于 是问题的最优解 从而是可行点由的定义 有 由(1

10、3.1.20)-(13.1.21)知(13.1.19)成立.( )k( )(1)k( )k( ,),( )( )( ) ()()13121 (,)kkkkkxf xf xf xp xf xp xf x又为的极小点 则 (. )13.1 外点罚函数法( )( )()( ),1,., (13.1.22)( ),1,2,., ,(13.1.13),(),(13.1.1).jijkkkkg ximsxh xjlkxxx 是紧的 又设是趋向 的严格递增正数列且对每个问题存在最优解则存在一个收敛子序列并且任何这样的收敛子序列的极限都是问题的最优解th13.1.3 设问题(13.1.1)的可行域s非空,且,

11、使得集合证明:根据假设,s是紧集,f(x)是连续函数,因此问题(13.1.1)存在. x最优解13.1 外点罚函数法于是故可设:根据p(x)的定义,当xs,p(x)=0,当xs,时,p(x)0.k( ),lim()0 (13.1.26)kkkp x 由于当时故 ( )( )lim(,) (13.1.23)lim() (13.1.24)kkkkkf xff xf( )lim() (13.1.25)kkkp xff由引理13.1.1和1.2可知,( )( ) (,) ()kkkf xf x和均为单调增有上界序列13.1 外点罚函数法()lim (13.1.27)jjkkxx设 注意到(13.1.2

12、6),可以断言,对每个.存在正整数k(),使得当kk()时有 . ( )kxs()( )( ),( ),.jkkkkkxssx于是,存在充分大的正整数使得所有满足的点又知是紧集 故存在收敛子列由(13.1.16)可知( )0p x ,.xs因此13.1 外点罚函数法 ( )( ) (13.1.28)f xf x由(13.1.28)和(1.29)可知()()( )jkf xf x,( )( )(13.1.29)jkf xf x 令故 (13.1.1),x由于 是问题的最优解 则13.1.2,jk根据引理对每一有( )( )(13.1.30)f xf x 13.1 外点罚函数法 ( )( )ff

13、xf x另一方面,由于f(x)连续,则又考虑到(13.1.24)和(13.1.30),则( )( )k,()(,) (13.1.31)kkf xf xff此外由得( )(,)( ),kkf xf x由故,(13.1.1).x因此是问题的最优解()lim()( ) jjkkf xf x( ) (13.1.32)ff xf13.1 外点罚函数法于是由(13.1.25)得(13.1.33)( )klim()0 (13.1.34)kkp xff( )k().kp x此即作为终止准则的原因13.2 内点罚函数法13.2.1 基本思想基本思想 min( ). . ( )0,1,2,.if xstg xim

14、(13.2.1)因此,此方法适用于下列不等式约束的问题:( ),( )(1,.,).if x g x im其中是连续函数记可行域为 ( )0,1,2,. (13.2.2)isx g xim0 ( )0,1,2,. isx g xim 严格可行域内点法产生的点列从可行域的内部逼近问题的解13.2 内点罚函数法内点罚函数法的基本思想:构造辅助(光滑)函数f000,., min( , )0,( )(13.2.1).( , )smin( , )sxssff xsxf xf xs该函数在严格可行域 以外的取值为无穷大 且当点 从趋于 的边界时 函数值趋于无穷大这样 无约束问题的解一定在 内。我们希望当时

15、 上述无约束问题的解趋于问题的解辅助函数在 的边界筑起了一道很高的墙,把无约束问题的解挡住了可行域 的内部.,因此 内点法也称为障碍函数法.13.2 内点罚函数法保持迭代点含于可行域内部的方法是定义障碍函数障碍函数其中b(x)是连续函数,当点x趋向可行域边界时,b(x). 是很小的正数.( , )( )( ) (13.2.3)f xf xb x min( , ). . int (13.2.4)f xstxs这样,当x趋向边界时,函数f(x,)趋于无穷大;否则,由于很小,则函数f(x,)的取值近似f(x).因此可通过求解下列问题得到原问题的近似解:13.2 内点罚函数法1( )log( ) (1

16、3.2.6)miib xg x 两种最重要的形式:11( ) (13.2.5)( )miib xg x13.2 内点罚函数法2.2 计算步骤(0)1(1)( )( )( )1,int ,0,01 ,1.2, min ( )( )3,(),;.:1,2kkkkkkkxskxf xb xxb xxkkk+1给定初始内点允许误差 初始参数缩小系数（ ， ） 置以为初点 解无约束问题 得极小点为若停止 得点否则,令 置转13.2 内点罚函数法312121 min (1)12. . 10 0 xxstxx 定义障碍函数例13.2.1 用内点法求解下列问题用解析法求解问题3k12k12111( ,)(1)

17、()121f xxxxxkmin ( ,). f xstxs13.2 内点罚函数法解得令k12kk( ,)( 12,)xx x2k1211k2221(1)04(1)10fxxxfxx k0(1,0),kxx当时，x是问题的最优解。13.2 内点罚函数法2.3. 收敛性( )k: (,).kf x证明 先证是单调减有下界的序列( )13.2.1 (13.2.1),int, (13.2.3)( ,)int,(13.2.1).kthsf xsxxxkk设在问题中 可行域内部非空且存在最优解,又设对每一个由定义的在内存在极小点 并且内点法产生的序列存在子列收敛到则 是问题的最优解( )(1)11int

18、( ,)( ,),kkkkkkxxsf xf x设,分别为和极小点由于,则13.2 内点罚函数法设x*是问题(13.2.1)的最优解.又知( )( ),()( *)kkxf xf x由于是可行点 则 (13.2.8)(1)(1)(1)11( )( )1( )( )( )(,)()() ()() ()() (,)kkkkkkkkkkkkkf xf xb xf xb xf xb xf x( )( )(,)()kkkf xf x13.2 内点罚函数法故有从而(13.2.9)( )(,)( *)kkf xf x( ) (,).:kkf x为单调减有下界序列从而存在极限( *)gf x( *).gf x下证,( *).( ),*intgf xf xxxxs如若不然由于是连续函数 故存在正数使得当且时有13.2 内点罚函数法即(13.2.10)k1( )( *)4b xgf x( )k,(,)(13.2.10),kk