惩罚函数法考试.doc

惩罚函数法 惩罚函数法是一种用来求解约束优化问题的间接解法。 基本思想：将约束优化问题转化为一系列的无约束优化问题来进行求解，逐步逼近目标函数的最优解。该法也称为SUMT（Sequence Unconstrained Minimization Technique）法，亦称为序列无约束极小化方法。采用惩罚函数法进行求解时，是在原目标函数中添加一些与约束函数相关的项，形成一个新的目标函数（惩罚函数），并以它取代原目标函数，然后用无约束优化方法求新目标函数的最优解。 根据惩罚项的函数形式不同，可以分为内点法、外点法和混合法三种。一、 内点法1. 基本原理内点法的特点是将构造的新的无约束目标函数惩罚函数定义在可行域内，并在可行域内求惩罚函数的极值点，即求解无约束问题时的探索点总是在可行域内部，这样，在求解内点惩罚函数的序列无约束优化问题的过程中，所求得的系列无约束优化问题的解总是可行解，从而在可行域内部逐步逼近原约束优化问题的最优解。内点法是求解不等式约束最优化问题的一种十分有效方法，但不能处理等式约束。因为构造的内点惩罚函数是定义在可行域内的函数，而等式约束优化问题不存在可行域空间，因此，内点法不能用来求解等式约束优化问题。对于目标函数为min s.t. （u=1,2,3,m）的最优化问题，利用内点法进行求解时，构造惩罚函数的一般表达式为或者 而对于受约束于的最优化问题，其惩罚函数的一般形式为或式中，-惩罚因子，是递减的正数序列，即 通常取。上述惩罚函数表达式的右边第二项，称为惩罚项，有时还称为障碍项。说明：当迭代点在可行域内部时，有（=1，2，3，4，m），而，则惩罚项恒为正值，当设计点由可行域内部向约束边界移动时，惩罚项的值要急剧增大并趋向无穷大，于是惩罚函数的值也急剧增大直至无穷大，起到惩罚的作用，使其在迭代过程中始终不会触及约束边界。2. 内点法的迭代步骤（1）取初始惩罚因子，允许误差；（2）在可行域内取初始点，令；（3）构造惩罚函数，从点出发用无约束优化方法求解惩罚函数的极值点；（4）检查迭代终止准则：如果满足或则停止迭代计算，并以为原目标函数的约束最优解，否则转入下一步； 根据情况，终止准则还可有如下的形式：或或5）取，转向步骤3）。 递减系数，常取0.1，亦可取0.02。采用内点法应注意的几个问题：（1）初始点的选取初始点必须严格在可行域内，满足所有的约束条件，避免为约束边界上的点。如果约束条件比较简单，可以直接人工输入；若问题比较复杂，可采用随机数的方式产生初始点，具体方程参照复合形法介绍。（2）关于初始惩罚因子的选择。实践经验表明，初始惩罚因子选的恰当与否，会显著地影响内点法的收敛速度，甚至解题的成败。若值选得太小，则在新目标函数即惩罚函数中惩罚项的作用就会很小，这时求的无约束极值，犹如原目标函数本身的无约束极值，而这个极值点又不大可能接近的约束极值点，且有跑出可行域的危险。相反，若值取得过大，则开始几次构造的惩罚函数的无约束极值点就会离约束边界很远，将使计算效率降低。可取150，但多数情况是取。 通常，当初始点是一个严格的内点时，则应使惩罚项在新目标函数中所起的作用与原目标函数的作用相当，于是得倘若约束区域是非凸的且初始点亦不靠近约束边界，则的取值可更小，约为上式算得值的0.10.5倍。内点法的计算程序框图例题：用内点法求 min s.t. （u=1,2,3,m）的约束最优解。（取0.001）解：构造内点惩罚函数为用极值条件进行求解，联立上式求得，由于约束条件的限制，可得无约束极值点为当取1，0.1,0.01,0时，可得最优解为，编程方式实现：1. 惩罚函数function f=fun(x,r)f=x(1,1)2+x(2,1)2-r*log(x(1,1)-1);2. 步长的函数function f=fh(x0,h,s,r)%h为步长%s为方向%r为惩罚因子x1=x0+h*s;f=fun(x1,r);3. 步长寻优函数function h=fsearchh(x0,r,s)%利用进退法确定高低高区间，利用黄金分割法进行求解h1=0;%步长的初始点st=0.001; %步长的步长h2=h1+st;f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);if f1f2 h3=h2+st; f3=fh(x0,h3,s,r); while f2f3 h1=h2; h2=h3; h3=h3+st; f2=f3; f3=fh(x0,h3,s,r); endelse st=-st; v=h1; h1=h2; h2=v; v=f1; f1=f2; f2=v; h3=h2+st; f3=fh(x0,h3,s,r); while f2f3 h1=h2; h2=h3; h3=h3+st; f2=f3; f3=fh(x0,h3,s,r); endend%得到高低高的区间a=min(h1,h3);b=max(h1,h3);%利用黄金分割点法进行求解h1=1+0.382*(b-a);h2=1+0.618*(b-a);f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);while abs(a-b)0.0001 if f1f2 a=h1; h1=h2; f1=f2; h2=a+0.618*(b-a); f2=fh(x0,h2,s,r); else b=h2; h2=h1; f2=f1; h1=a+0.382*(b-a); f1=fh(x0,h1,s,r); endendh=0.5*(a+b);4. 迭代点的寻优函数function f=fsearchx(x0,r,epson)x00=x0;m=length(x0);s=zeros(m,1);for i=1:m s(i)=1; h=fsearchh(x0,r,s); x1=x0+h*s; s(i)=0; x0=x1;endwhile norm(x1-x00)epson x00=x1; for i=1:m s(i)=1; h=fsearchh(x0,r,s); x1=x0+h*s; s(i)=0; x0=x1; endendf=x1;5. 主程序clearclcx0=2;2; %给定初始点r=1;c=0.1;epson=0.001;x1=fsearchx(x0,0.1,epson);while norm(x0-x1)epson x0=x1; r=r*c; x1=fsearchx(x0,r,epson) ; enddisp 函数的最优解为x1 运行结果：函数的最优解为x1 = 1.0475 -0.0005二、外点法1. 外点法的基本原理外点法既可以用来求解不等式约束的优化问题，还可以求解等式约束的优化问题。外点法的特点是将惩罚函数定义于约束可行域之外，且求解无约束问题的探索点是从可行域外部逼近原目标函数的约束最优解的。对于目标函数受约束于的最优化设计问题，利用外点法求解时，作为无约束新目标函数的惩罚函数，其一般表达式为式中：右边第二项-惩罚项： -构造惩罚项函数的指数，其值将影响函数等值线在约束面处的性质，一般取。 -惩罚因子，是大于零的一个递增数列，即应满足：在惩罚项中： 由此可见，当探索点在可行域内时，惩罚项为零；若不在可行域内，则不为零，且愈大，则受到的“惩罚”亦愈大。因此，要使极小，必须迫使式中的惩罚项等于零，亦即要求满足约束条件，即迫使。这就保证了在可行域内与是等价的，即当约束条件中尚包括的等式约束时，构建惩罚函数为：。对惩罚函数求无约束极值，其结果将随给定的惩罚因子的值而异。可以将惩罚函数无约束极值问题的最优解看作是以为参数的一条轨迹，当取时，点列就沿着这条轨迹趋于原目标函数的约束最优解。因此，外点法是随着惩罚因子（参数）的递增序列，使惩罚函数的无约束极值点从可行域外部向原目标函数的约束最优点逼近，直至达到最优点。 外点法是通过一系列递增的惩罚因子来求惩罚函数一系列的无约束极值，并使之逐渐逼近原目标函数的约束最优解的一种方法。这一系列的无约束极值点是从可行域外向约束边界逼近的。并且随着惩罚因子的增加，由求解一个惩罚函数的极小值转入到求解另一个惩罚函数的极小值的过程中，式中的惩罚项之值将逐渐减小，直至为零（到达约束面上时），因此它又称为衰减函数。 由于外点法的上述探索特点，使之很适用于等式约束的最优化问题。因为在这种情况下，凡是不满足等式约束条件的探索点均是外点，随着探索过程的进行在求解惩罚函数极小值的过程中，必然要求最后将惩罚项压缩为零，从而使惩罚函数的无约束极值点等于原目标函数的约束最优点。 外点法的迭代步骤： 1）选择参数 初始惩罚因子； 允许误差（均应大于零）； 递增系数（，可取8）； 初始点（可在可行域外部或内部任意选择，不论怎样选择，的无约束极值点均在可行域外）； 惩罚因子的控制量，当时即可判别是否达到收敛精度要求。 令计算次数。 2）从点出发，用无约束最优化方法求解：得其中 3）计算点违反约束的最大量： 4）检验迭代终止准则：如果满足则可认为点已接近约束边界，停止迭代。否则转入下一步。 5）检验？ 若，再用靠近约束面附近的条件极值点的移动距离作为迭代终止准则来检验，即当时，停止迭代： 若或式不成立，则取，并转向步骤2）。 外点法的计算程序框图如下图所示：外点法的计算程序框图 应该指出：由于迭代次数有限，当达到一定收敛精度时，即可认为已达到最优点。因此，外点法最后得到的最优点严格地说还是一个“外点”。如果工程设计需要一个严格的“内点”，则可将原约束边界向可行域内平移一个距离，称约束裕量（-），一般推荐，以保证得到的最优点为“内点”。三、混合法鉴于内点法和外点法各有优缺点，因此在惩罚函数法中又出现了所谓混合法。它是将内点法和外点法的惩罚函数形式结合在一起，用来求解既有不等式约束又有等式约束条件的最优化问题。例如求解原目标函数极小值：根据混合法的基本思想，作为新目标函数的惩罚函数，其惩罚项由两部分组成，一部分反映不等式约束的影响并以内点法的构造形式列出；另一部分反映等式约束的影响并以外点法的构造形式列出，即混合法惩罚函数的一般表达式为即所构造的混合法的惩罚函数，同时含有障碍函数和衰减函数。根据Fiacco等建议的关系式将惩罚因子统一用表示，则混合法的惩罚函数又可表达为或当受约束于时，则混合法的惩罚函数的表达式为或 混合法与内点法及外点法一样，属于序列无约束极小化方法中的一种。利用上述式子构造混合法的惩罚函数时，其求解具有内点法的特点。这时，其初始点应为内点：而值可参照内点法选取；其迭代程序则与内点法的相类似。 混合法的迭代步骤： 1）选取初始惩罚因子的值，为了简化计算，常取；规定允许误