资源描述：
《最优化方法及其Matlab程序设计课件之罚函数法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、最优化方法及其Matlab程序设计马昌凤2010年3月22日目录第九章罚函数法19.1外罚函数法............................19.2内点法...............................109.3乘子法...............................219.4乘子法的Matlab实现......................38ii第九章罚函数法从本章开始,我们讨论约束优化问题的求解方法.首先介绍求解约束优化问题的经典算法—罚函数法.其基本思想是:根据约束条件的特点将其转化为某种惩罚函数加到目
2、标函数中去,从而将约束优化问题转化为一系列的无约束优化问题来求解.本章主要介绍外罚函数法、内点法和乘子法.9.1外罚函数法我们首先通过一个简单的例子来说明罚函数的构造.1第九章罚函数法回目录9.1外罚函数法例9.1求解约束优化问题:min?(?)=(?1−1)2+(?2−1)2,s.t.?1+?2=1.解由等式约束得?2=1−?1,代入目标函数得到一个无约束的单变量极小化问题min?(?221)=(?1−1)+?1,其全局极小点为?*=0.5,从而得到原问题的全局极小点为?*=1(0.5,0.5)?.现在要使构造的罚函数?¯(?)满足⎧⎪⎨=0,?1
3、+?2−1=0,?¯(?)⎪⎩>0,?1+?2−1̸=0,只要令?¯(?)=(?1+?2−1)2即可.现在考察目标函数和上述罚函数的组·2·第九章罚函数法回目录9.1外罚函数法合?(?,?)=?(?)+??¯(?)=(?2221−1)+(?2−1)+?(?1+?2−1),其中?>0是充分大的正数,称为罚参数或罚因子.求这个组合函数的极小点.由??(?,?)??(?,?)==0,??1??2得⎧⎪⎨(1+?)?1+??2=1+?,⎪⎩??1+(1+?)?2=1+?.求解上述方程组得?+1?1(?)=?2(?)=.2?+1令?→+∞,有(︀)︀?(︁11
4、)︁??→*1(?),?2(?),=?.22·3·第九章罚函数法回目录9.1外罚函数法这样,我们就从无约束优化问题极小点的极限得到了原问题的极小点.下面我们将这种思想方法推广到一般约束的优化问题.考虑⎧⎪⎪?⎪⎪min?(?),?∈R,⎨s.t.ℎ?(?)=0,?∈?={1,···,?},(9.1)⎪⎪⎪⎪⎩??(?)≥0,?∈?={1,···,?}.记可行域为?={?∈R?
5、ℎ?(?)=0(?∈?),??(?)≥0(?∈?)}.构造罚函数∑︁?∑︁??¯(?)=ℎ2[min{0,??(?)}]2(9.2)?(?)+?=1?=1和增广目标函数?(?,
6、?)=?(?)+??¯(?),(9.3)其中?>0是罚参数或罚因子.不难发现,当?∈?时,即?为可行点时,?(?,?)=?(?),此时目标函数没有受到额外惩罚;而当?̸∈?时,即?为不可行点时,?(?,?)>?(?),时目标函数受到了额外的惩罚.?>0越大,·4·第九章罚函数法回目录9.1外罚函数法受到的惩罚越重.当?>0充分大时,要使?(?,?)达到极小,罚函数?¯(?)应充分小才可以.从而?(?,?)的极小点充分逼近可行域?,而其极小值自然充分逼近?(?)在?上的极小值.这样求解一般约束优化问题(9.1)就可以化为求解一系列无约束的优化问题min
7、?(?,??),其中{??}是正数序列,且??→+∞.从例9.1可以看出,当?→∞时,?(?,?)的极小点?(?)→?*,但2?+21?1(?)+?2(?)−1=−1≠=0,2?+12?+1即?(?)̸∈?,也就是说?(?)是从可行域的外部趋于?*的.因此上述的罚函数法也称为外罚函数法(或外点法).下面给出外罚函数法的详细算法步骤.算法9.1(外罚函数法)步0给定初始点?0∈R?,终止误差0≤?≪1.?1>0,?>1.令?:=1.·5·第九章罚函数法回目录9.1外罚函数法步1以??−1为初始点求解子问题min?(?,??)=?(?)+???¯(?)
8、.(9.4)?∈R?令其极小点为??.步2若???¯(??)≤?,停算,输出?*≈??作为近似极小点.步3令??+1:=???,?:=?+1,转步1.注由上述算法可知,外罚函数法结构简单,可以直接调用无约束优化算法的通用程序,因而容易编程实现.缺点是:(1)??往往不是可行点,这对于某些实际问题是难以接受的;(2)罚参数??的选取比较困难,取的过小,可能起不到“惩罚”的作用,而取得过大则可能造成?(?,??)的Hesse阵的条件数很大,从而带来数值技术上的困难;(3)注意到?¯(?)一般是不可微的,因而难以直接使用利用导数的优化算法,从而收敛速度缓慢
9、.下面讨论算法9.1的收敛性.我们首先证明下面的引理.引理9.1设{??}是由算法9.1产生的迭代序列.若?
