[工程科技]第五章 约束优化方法.ppt

如上图，此处的惩罚函数也是由原目标函数F(x)与惩罚 项而组成。惩罚项中包含有可调整的参数r(k)与约束函数。 由惩罚项的构造可知，若迭代点在可行域的内部，惩罚 项的值为0，惩罚函数值与原目标函数值相等；而若在非可 行域（即可行域的外部），惩罚项是以约束函数的平方加 大的，即迭代点违反约束越严重，惩罚项的值增加的越大。 因此，在非可行域内，必有 且罚因子r（k）越 大，惩罚作用越明显。 由图，对于某r(k)值，求出惩罚函数 的最优点 当取罚因子 为递增数列，随k的增加，罚函数的无约束最 优点序列为 该序列将趋近与原约束问题的最优点x*，x*=b。 值得注意的是，尽管 增加直至趋于无穷大，但最终 的近似最优点x*仍在可行域的外部。 即外点法构造的罚函数是使迭代点从可行域的外部逐 渐逼近约束最优点，这正是外点法名称的由来。 ㈡外点罚函数法的形式及特点 先讨论解不等式约束优化问题 设有不等式约束优化问题 u=1，2……，p D： 构造外点法惩罚函数的常见形式 取正,递增 引入罚因子递增系数C1，并令 =∞ 惩罚项 的含义可用另一形式表示 当gu(x) ≥0 （x∈D） 当gu(x) 0 （x∈D） 在可行域内 （包括边界） 在非可行域， 为增函数 外点罚函数的求解过程 用外点罚函数去逼近原目标函数F(x)，构造一个无约束 优化问题模型 x∈Rn 任选初始点x(0)，初始法罚因子r(0)0,罚因子递增系数C1 对于r(k)为某一值，同过对惩罚函数的无约束求优，可 得最优点 。随着k的增大，得无约束最优点列 在k←∞的过程中，点列将趋近于原问题的最优点 实线为原目标 函数等值线 虚线为罚函数 等值线 总结 由上图可见，两种等值线在可行域内部及边界上是重合 的；而在非可行域中，罚函数的等值线升高了。即只有在 可行域外部惩罚项才起到惩罚的作用。r(k)值越大，惩罚作 用越大。 由上b图可知，在起作用约束边界处罚函数等值线变得越 密集和越陡峭。随r(k)的增大，最优点列将越接近于原约束 优化问题的最优点x*。但须注意，近似的最优点是落在边 界处非可行域一侧。 外点法罚函数常用形式除上面介绍的两种，还有 ㈢对几个问题的讨论 （1）初始点x(0)的选取 在可行域及非可行域内均可。 （2）初始罚因子r(0)和递增系数C的选取 选取过小，则序贯无约束求解的次数就增多，收敛速度慢；反之，则在非可行域中，罚函数比原目标函数要大得多，特别在起作用约束边界处产生尖点，函数性态变坏，从而限制了某些无约束优化方法的使用，致使计算失败。 C的选取影响不大，通常C=5~10 （3）约束容差带 最优点在非可行域内，即位一个非可行点，这对某些工 程是不允许的。因此，可在约束边界可行域一侧加一条容 差带。 相当于将约束条件改为 是容差量，通常 ㈣终止准则 随着罚因子 的值不断增大，罚函数的序列无约束最 优点将越来越趋近于原约束优化问题的最优点。 设惩罚函数 的无约束最优点列为 对应的罚函数值为 终止准则可用下述两者之一 ⑴相邻两次惩罚函数无约束最优点之间的距离已足够的小。 设ε1为收敛精度，一般取ε1=10-4~10-5，则需要满足 ⑵相邻两次惩罚函数值得相对变化量已足够小。 设ε2为收敛精度，一般取ε2=10-3~10-4，则需要满足 ⑶求 ，得最优点 ⑷当k=0时转步骤⑸，否则转步骤⑹ ⑸置k←k+1， ，并转步骤⑶ ⑹由终止准则，若满足则转步骤⑺，否则转⑸ ⑺ , 输出最优解(x*,F*)，停止计 算。 算法步骤 ⑴在n维空间任取初始点x（0） ⑵选取初始罚因子r(0),递增系数C，并置k←0 ㈤用外点罚函数法解等式约束优化问题 设有二维约束优化问题 D： h1(x)=x1+x2-10=0 如右图，h1（x）为该约束 问题的可行域，这条直线以 外的整个x1ox2平面为非可 行域。目标函数等值线与该 直线的切点为最优点 最优点 按外点法的基本思想，构造惩罚函数 x∈D x∈D 在可行域上，惩罚项的值为零，惩罚函数值与原目标函数 值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于 原目标函数，即在可行域外惩罚项起到了惩罚作用。 在k←∞的过程中，点列将趋近于原问题的最优点 对于m(k)，随着k的增大，得无约束最优点列 推广到具有一般的