华中农业大学现代设计方法第二章第五节.ppt

《华中农业大学现代设计方法第二章第五节.ppt》由会员分享，可在线阅读，更多相关《华中农业大学现代设计方法第二章第五节.ppt（41页珍藏版）》请在三一办公上搜索。

1、1,2.5 约束优化方法,概述 惩罚函数法 复合形法,2,一、概述 与无约束优化问题不同的是，约束优化问题的目标函数的最小值是函数在有约束条件所限定的可行域内的最小值，并不一定是目标函数的自然最小值。约束优化方法是用来求解如下非线性约束优化问题的数值迭代算法。,3,根据处理约束条件的不同方式，求解这类问题的方法分为直接法和间接法。直接法 在迭代过程中逐点考察约束的可行域，并使 迭代点始终局限于可行域之内的算法称为直 接法。常用的直接法有：复合形法、可行方向法、约束坐标轮换法、网格法、随即方向搜索法、随机实验法等。,4,间接法 把约束条件引入目标函数，是约束优化问题转 化为相对简单的二次规划问题

2、或线性规划问题 求解的算法称为间接法。常用的间接法有消元法、拉格朗日乘子法、惩罚函数法和序列线性规划法等。,5,二、惩罚函数法 1.概述 惩罚函数法是求解约束优化问题的间接法的一种。它是将目标函数和约束条件构造成一个新的目标函数，将约束最优化问题转化为无约束最优化问题，然后利用各种有效的无约束最优化解法求解而得到约束最优化的近似解。这是一种使用广泛的有效的间接解法。,6,基本思路：将不等式和等式约束函数 和待定系数（称为加权因子）经加权转化后，和原目标函数一起组成一个新的目标函数（惩罚函数），然后对它求最优解。,对优化问题：,7,把其中不等式和等式约束函数值经加权处理后，和原目标函数结合新的目

3、标函数：,这一新目标函数即为惩罚函数。对应的优化问题就为无约束优化问题。惩罚函数中的后两项称为惩罚项。称为惩罚因子或加权因子。,8,惩罚项满足下列要求：(1)当满足约束条件时，惩罚项的值很小或为0；(2)当不满足约束条件时，惩罚项的值很大，即对不满足约束条件的点的函数值进行惩罚。新目标函数中，惩罚因子 是一系列的按一定规则变化的值。当按照一定的法则改变数值时，就构成了一系列的无约束优化问题，求解就可得到一系列的无约束的迭代点，使其一步步迭代不断地逼近原约束优化问题的最优解。,9,数学证明：当惩罚函数满足时，上述惩罚函数在 过程中所产生的极小点 序列将逐渐逼近于愿约束问题的最优解。即,10,因此

4、，惩罚函数法又称序列无约束极小化方法，常称SUMT(sequential unconstrained minimization technique)。根据惩罚项的构成形式，惩罚函数法可分为：内点惩罚函数法 外点惩罚函数法 混合惩罚函数法,11,2.外点惩罚函数法（又称外点法）对于约束优化问题：,外点惩罚函数法构造惩罚函数的形式为：,12,分析：对于不等式约束，当 满足约束条件时，惩罚项为0；当不满足约束条件时，惩罚项大于0，这相当于给不满足约束条件的迭代点在函数值上给予惩罚，以此来使迭代点逐步向可行域边界靠近；对于等式约束，也可以得出类似的结论。因此，外点法既可处理不等式约束，也可处理等式约束

5、。,13,为了进一步理解外点法，我们考虑一种只有不等式约束的情况，此时，惩罚函数(1)特征 与内点法相反，外点法将惩罚函数定义于约束可行域之外，且求解无约束问题的一系列迭代点是从可行域外部逼近原目标函数的约束最优解。外点法可用来求解含不等式约束和等式约束的优化问题。,14,从上式可以看出，在可行域内，约束函数值小于零，惩罚项也等于零；在可行域外，惩罚项大于零，惩罚项可分以下两种情况：此时可以清楚地看出，外点法的惩罚项是定义于可行域之外的。事实上，外点法的迭代过程也是从可行域外一步步向可行域边界逼近的。这正是外点法名称的由来。,15,惩罚项的大小还与惩罚加权因子 有关。当惩罚因子按一个递增的正数

6、序列变化时，依次求解所对应的无约束极小化问题，将得到一个极小点序列 随着 逐步增大，这个极小点序列将逐步逼近原约束优化问题的最优解。,16,(2)迭代步骤步骤一 给定初始点、收敛精度、初始惩罚因子 和惩罚因子递增系数，置；步骤二 构造惩罚函数步骤三 求解无约束优化问题，得 令,17,步骤四 判断收敛精度：若满足条件则令，结束计算；否则，令，转步骤二继续迭代。,18,(3)举例 用外点法求解约束优化问题：收敛准则：,解释约束容限：如果(为给定的约束容限)，则认为点 落在约束边界上，亦即它是可行点。,19,解：利用外点法惩罚法构造无约束优化问题此例只是为了说明外点法的思路，用微分法求解上述无约束优

7、化问题。在可行域内：知在可行域内无极值点。,20,在可行域外，令从上面两式解得 可见，对于不同的惩罚因子值，可以得到不同的极小点。,21,取 进行迭代计算，迭代结果如下：点 满足点距收敛准则，同时，它在约束容限范围内，因此，终止迭代！输出结果。,22,(4)选择 外点法惩罚因子按下式递增：式中：C惩罚函数，通常C=510。外点法惩罚因子 的合理取值很重要，若 太大，惩罚项的作用就会很大，使惩罚函数的等值线变形或偏心，求极值将会很困难；若 太小，将增加迭代次数，计算效率降低。多数情况下，取=1，C=10时结果较好。,23,3.内点惩罚函数法（又称内点法，限制在可行域内）(1)特征 该法是求解不等

8、式约束最优化问题的一种有效的方法，但不能处理等式约束，其特点是将新的无约束目标函数惩罚函数定义在可行域内。在可行域内，序列迭代点逐步逼近约束边界上的最优点。这样，求解无约束问题时的搜索点总是保持在可行域内部。,24,对于约束优化问题 内点法求解时，惩罚函数的形式为：,25,式中 惩罚加权因子，是递减的正数序列 c惩罚因子的缩减系数，即而 和 为障碍项。,26,由于内点法的迭代过程在可行域内进行，障碍项的作用是阻止迭代点越出可行域。若搜索过程中迭代点X保持为可行点，满足约束条件，则障碍项 必为正值，当X远离约束边界时，惩罚函数 是相当小的正值，这是惩罚作用很小，但当迭代点靠近某一约束边界 时，则

9、障碍项 的值急剧增大并趋向无穷大，于是惩罚函数也随之急剧增大至无穷大。,27,用内点法求解约束优化问题：收敛准则：点距准则，,举例,28,解：构造惩罚函数：用解析法极值条件求解，令联立求解得：,29,迭代过程(取),按点距收敛准则，需要迭代多少次，请同学们自己判断。,30,当 时，可知，就是所求约束优化问题的最优解。从上面的例子可以看出，序列最优点 是以为参数的点列轨迹。因内点法将惩罚函数定义在可行域内，故点 要严格满足全部的约束条件，且应选择离约束边界较远些，即应使。,31,(2)初始惩罚因子 的选择 的选择会影响到迭代计算能否正常进行以及计算效率的高低，值应适当。若 太大，则开始几次构造的

10、惩罚函数的无约束极值点会离约束边界很远，将增加迭代次数，使计算效率降低。若 太小，惩罚函数中的障碍项的作用就会很小，使惩罚函数性态变坏，甚至难以收敛到原约束目标函数的极值点。,32,目前，还没有一定的有效方法，往往要经过多次试算，才能确定一个适当的。多数情况下，一般取=1，然后根据试算的结果，加以调整；或按经验公式：选取值。,33,(3)惩罚因子的缩减系数C的选择 在构造序列惩罚函数时，惩罚因子 是一个逐次递减到0的数列，相邻两次迭代的惩罚因子关系式为：其中，C惩罚因子的缩减系数，0C1，通常取值为：0.10.7。,一般来说，C值的大小对收敛速度无明显影响，在迭代过程中不起决定性作用。,34,

11、(4)收敛条件 内点法的收敛条件为：,35,(5)内点法的迭代步骤如下 步骤一 选，可行初始点 不应在边界上，最好不 要靠近任何一个约束边界；步骤二 选，令k=0（迭代次数）；步骤三 构造惩罚函数，选某一适当的无约束优 化方法，求，得到点，令步骤四 判断迭代点是否收敛，若满足收敛条件，迭代终止，约束最优解为：否则，令 转步骤三。,36,5.混合惩罚函数法（又称混合法）这种方法是将内点法和外点法的惩罚函数形式结合在一起，扬长避短，可用来求解同时具有等式约束和不等式约束函数的优化问题。对于约束优化问题：,37,混合法求解时，惩罚函数的形式为：障碍项，惩罚因子为按内点法选取，即 障碍项，惩罚因子为，

12、当 时，,满足外点法对惩罚因子的要求。,38,可见，混合法对不等式约束采用内点法构造惩罚项，对等式约束采用外点法构造惩罚项。混合法的求解特点与内点法相同，迭代过程在可行域内进行，初始点，惩罚因子初始值、惩罚因子缩减系数均可参考内点法选取。,39,二、复合形法 数学基础：梯度法、方向导数、kt条件 适用条件：目标函数和约束函数均为n维一阶连续可微函数、可行域是连续闭集、求解不等式约束的一种直接解法。可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接解法，它是求解大型约束优化问题的主要方法之一。其收敛速度快，效果好，但程序比较复杂，直接算法，计算困难且工作量大。,40,【本节思考题】1.可行方向、下降方向的几何意义。2.最优下降可行方向的确定方法。3.惩罚函数法的基本思想。4.内点法和外点法分别是如何定义惩罚函数的？5.内点法、外点法、混合法分别有什么特点？,41,【作业】,1.用可行方向法求解以下线性规划问题：,2.用外点法求解：,