华中农业大学现代设计方法课件第二章-第五节

现代设计方法第二章优化设计1§2.5约束优化方法概述惩罚函数法复合形法现代设计方法第二章优化设计2一、概述与无约束优化问题不同的是，约束优化问题的目标函数的最小值是函数在有约束条件所限定的可行域内的最小值，并不一定是目标函数的自然最小值。约束优化方法是用来求解如下非线性约束优化问题的数值迭代算法。),2,1(0)(),2,1(0)(..)(minpvXhmuXgtsRXXfvun现代设计方法第二章优化设计3根据处理约束条件的不同方式，求解这类问题的方法分为直接法和间接法。直接法在迭代过程中逐点考察约束的可行域，并使迭代点始终局限于可行域之内的算法称为直接法。常用的直接法有：复合形法、可行方向法、约束坐标轮换法、网格法、随即方向搜索法、随机实验法等。现代设计方法第二章优化设计4间接法把约束条件引入目标函数，是约束优化问题转化为相对简单的二次规划问题或线性规划问题求解的算法称为间接法。常用的间接法有消元法、拉格朗日乘子法、惩罚函数法和序列线性规划法等。现代设计方法第二章优化设计5二、惩罚函数法1.概述惩罚函数法是求解约束优化问题的间接法的一种。它是将目标函数和约束条件构造成一个新的目标函数，将约束最优化问题转化为无约束最优化问题，然后利用各种有效的无约束最优化解法求解而得到约束最优化的近似解。这是一种使用广泛的有效的间接解法。现代设计方法第二章优化设计6基本思路：将不等式和等式约束函数和待定系数（称为加权因子）经加权转化后，和原目标函数一起组成一个新的目标函数（惩罚函数），然后对它求最优解。),2,1(0),,2,1(0pvXhmuXgvukr),,2,1(0),,2,1(0..minpvXhmuXgtsRXXfvun对优化问题：现代设计方法第二章优化设计7把其中不等式和等式约束函数值经加权处理后，和原目标函数结合新的目标函数：()()()()121211min,,pmkkkkuvuvXrrfXrGgXrHhX这一新目标函数即为惩罚函数。对应的优化问题就为无约束优化问题。惩罚函数中的后两项称为惩罚项。称为惩罚因子或加权因子。()()12,kkrr现代设计方法第二章优化设计8惩罚项满足下列要求：(1)当满足约束条件时，惩罚项的值很小或为0；(2)当不满足约束条件时，惩罚项的值很大，即对不满足约束条件的点的函数值进行惩罚。新目标函数中，惩罚因子是一系列的按一定规则变化的值。当按照一定的法则改变数值时，就构成了一系列的无约束优化问题，求解就可得到一系列的无约束的迭代点，使其一步步迭代不断地逼近原约束优化问题的最优解。()()12,kkrr现代设计方法第二章优化设计9数学证明：当惩罚函数满足时，上述惩罚函数在过程中所产生的极小点序列将逐渐逼近于愿约束问题的最优解。即()()11()()21()()()12lim[()]0lim[()]0lim(,,)()0mkkukupkkvkvkkkkrGgXrHhXXrrfXk()kX(0)(1)()(1),,,,,kkXXXX()*limkkXX现代设计方法第二章优化设计10因此，惩罚函数法又称序列无约束极小化方法，常称SUMT(sequentialunconstrainedminimizationtechnique)。根据惩罚项的构成形式，惩罚函数法可分为：内点惩罚函数法外点惩罚函数法混合惩罚函数法现代设计方法第二章优化设计112.外点惩罚函数法（又称外点法）对于约束优化问题：),2,1(0)(),2,1(0)(..)(minpvXhmuXgtsRXXfvun外点惩罚函数法构造惩罚函数的形式为：pvvkmuukkXhrXgrXfrX12)(12)()(,0max,现代设计方法第二章优化设计12分析：①对于不等式约束，当满足约束条件时，惩罚项为0；当不满足约束条件时，惩罚项大于0，这相当于给不满足约束条件的迭代点在函数值上给予惩罚，以此来使迭代点逐步向可行域边界靠近；②对于等式约束，也可以得出类似的结论。因此，外点法既可处理不等式约束，也可处理等式约束。()0ugX()kX()0vhX现代设计方法第二章优化设计13为了进一步理解外点法，我们考虑一种只有不等式约束的情况，此时，惩罚函数(1)特征与内点法相反，外点法将惩罚函数定义于约束可行域之外，且求解无约束问题的一系列迭代点是从可行域外部逼近原目标函数的约束最优解。外点法可用来求解含不等式约束和等式约束的优化问题。2()()1,max0,mkkuuXrfXrgX现代设计方法第二章优化设计14从上式可以看出，在可行域内，约束函数值小于零，，惩罚项也等于零；在可行域外，惩罚项大于零，惩罚项可分以下两种情况：此时可以清楚地看出，外点法的惩罚项是定义于可行域之外的。事实上，外点法的迭代过程也是从可行域外一步步向可行域边界逼近的。这正是外点法名称的由来。00),(maxXgu00),(max,0)(XgXguu()2()10,max,00ukmkuuufXgXXrfXrgXgX(当时)(当时)现代设计方法第二章优化设计15惩罚项的大小还与惩罚加权因子有关。当惩罚因子按一个递增的正数序列变化时，依次求解所对应的无约束极小化问题，将得到一个极小点序列随着逐步增大，这个极小点序列将逐步逼近原约束优化问题的最优解。)(kr012()(1)kkrrrrr(0)(1)()(1),,,,,kkXXXX)(kr现代设计方法第二章优化设计16(2)迭代步骤步骤一给定初始点、收敛精度、初始惩罚因子和惩罚因子递增系数，置；步骤二构造惩罚函数步骤三求解无约束优化问题，得令)0(Xrc0kpvvkmuukkXhrXgrXfrX12)(12)()(,0max,),(min)(krX*X*)1(XXk现代设计方法第二章优化设计17步骤四判断收敛精度：若满足条件则令，结束计算；否则，令，转步骤二继续迭代。)()()()()()1()()1(kkkkkXfXfXfXX)()(,)1(*)1(*kkXfXfXX1,)()1(kkcrrkk现代设计方法第二章优化设计18(3)举例用外点法求解约束优化问题：收敛准则：12211221min..0()0fXxxstgXxxgXx(1)()0.10.01kkXX，约束容限＝解释约束容限：如果(为给定的约束容限)，则认为点落在约束边界上，亦即它是可行点。()()(),kkuXgX满足－(3)X现代设计方法第二章优化设计19解：①利用外点法惩罚法构造无约束优化问题②此例只是为了说明外点法的思路，用微分法求解上述无约束优化问题。在可行域内：知在可行域内无极值点。12()22()212121(min,()()kkkxxXrxxrxxrx可行域内）（可行域外）01,0121xx现代设计方法第二章优化设计20在可行域外，令从上面两式解得可见，对于不同的惩罚因子值，可以得到不同的极小点。()2()11211()212214()2012()0kkkrxxxrxxrxxx12()()2()111,2(1)4(1)2kkkxxrrr现代设计方法第二章优化设计21③取进行迭代计算，迭代结果如下：点满足点距收敛准则，同时，它在约束容限范围内，因此，终止迭代！输出结果。(0)(1)()()1,10kkkrrCrr(1)(1)(1)(2)(2)(2)(2)(1)(3)(3)(3)(3)(2)1(0.25,0.4375),()0.687510,(0.0455,0.0479),()0.0934,0.44100(0.00495,0.00498),()0.00993,0.059TTrXfXrXfXXXrXfXXX当时，当时当时，(3)X现代设计方法第二章优化设计22(4)选择外点法惩罚因子按下式递增：式中：C—惩罚函数，通常C=5－10。外点法惩罚因子的合理取值很重要，若太大，惩罚项的作用就会很大，使惩罚函数的等值线变形或偏心，求极值将会很困难；若太小，将增加迭代次数，计算效率降低。多数情况下，取=1，C=10时结果较好。()kr1kkCrr)0(r)0(r)0(r)0(r现代设计方法第二章优化设计233.内点惩罚函数法（又称内点法，限制在可行域内）(1)特征该法是求解不等式约束最优化问题的一种有效的方法，但不能处理等式约束，其特点是将新的无约束目标函数——惩罚函数定义在可行域内。在可行域内，序列迭代点逐步逼近约束边界上的最优点。这样，求解无约束问题时的搜索点总是保持在可行域内部。现代设计方法第二章优化设计24对于约束优化问题内点法求解时，惩罚函数的形式为：),2,1(0)(..)(minmuXgtsRXXfun适应于有平方项或适应于无平方项或或muuumuuumuukkmuukkXgInXgGXgXgGXgInrXfrXXgrXfrX11111,1,现代设计方法第二章优化设计25式中—惩罚加权因子，是递减的正数序列c—惩罚因子的缩减系数，即而和为障碍项。kr1kkcrr0210rrrmuukXgr11muukXgInr1现代设计方法第二章优化设计26由于内点法的迭代过程在可行域内进行，障碍项的作用是阻止迭代点越出可行域。若搜索过程中迭代点X保持为可行点，满足约束条件，则障碍项必为正值，当X远离约束边界时，惩罚函数是相当小的正值，这是惩罚作用很小，但当迭代点靠近某一约束边界时，则障碍项的值急剧增大并趋向无穷大，于是惩罚函数也随之急剧增大至无穷大。muukXgr11krX,0XgukrX,现代设计方法第二章优化设计27用内点法求解约束优化问题：收敛准则：点距准则，00..min12221121xXgxxXgtsxxXf0.01举例现代设计方法第二章优化设计28解：①构造惩罚函数：②用解析法极值条件求解，令联立求解得：122121,xInxxInrxxrXkk0110121221)(212211)(1xxrxxxxxrxkk)(2)(2)(116181,4181kkkrrxrx现代设计方法第二章优化设计29迭代过程(取)(0)(1)()()1,0.5kkkrrcrr238.0,135.0,103.081466.0,283.0,183.04109.1,782.0,309.02175.1,25.1,5.01)3(3)3()2(2)2()1(1)1()0(0)0(XfXrXfXrXfXrXfXrTTTT时，当时，当时，当时，当按点距收敛准则，需要迭代多少次，请同学们自己判断。现代设计方法第二章优化设计30③当时，可知，就是所求约束优化问题的最优解。从上面的例子可以看出，序列最优点是以为参数的点列轨迹。因内点法将惩罚函数定义在可行域内，故点要严格满足全部的约束条件，且应选择离约束边界较远些，即应使。()0kr