资源描述
现代设计方法 第二章 优化设计 1 2.5 约束优化方法 概述 惩罚函数法 复合形法 现代设计方法 第二章 优化设计 2 一、概述 与无约束优化问题不同的是，约束优化问题的目标函数 的最小值是函数在有约束条件所限定的可行域内的最小值， 并不一定是目标函数的自然最小值。 约束优化方法是用来求解如下非线性约束优化问题的数 值迭代算法。 ),2,1(0)( ),2,1(0)(. )(m in pvXh muXgts RXXf v u n 现代设计方法 第二章 优化设计 3 根据处理约束条件的不同方式，求解这类问题 的方法分为 直接法 和 间接法 。 直接法 在迭代过程中逐点考察约束的可行域，并使 迭代点始终局限于可行域之内的算法 称为直 接法。 常用的直接法有： 复合形法 、 可行方向法 、 约束坐 标轮换法 、 网格法 、 随即方向搜索法 、 随机实验法 等。 现代设计方法 第二章 优化设计 4 间接法 把约束条件引入目标函数 ， 是约束优化问题转 化为相对简单的二次规划问题或线性规划问题 求解的算法称为 间接法 。 常用的间接法有 消元法 、 拉格朗日乘子法 、 惩罚函数法 和 序列线性规划法 等。 现代设计方法 第二章 优化设计 5 二 、 惩罚函数法 1.概述 惩罚函数法是求解约束优化问题的间接法的一种 。 它是将目标函数和约束条件构造成一个新的目标函数 ， 将约束最优化问题转化为无约束最优化问题 ， 然后利用各种 有效的无约束最优化解法求解而得到约束最优化的近似解 。 这是一种使用广泛的有效的 间接解法 。 现代设计方法 第二章 优化设计 6 基本思路： 将不等式和等式约束函数 和待定系数 （称为 加权因子 ）经加权转化后，和原目标函 数一起组成一个新的目标函数（ 惩罚函数 ），然后对它求最 优解。 ),2,1(0),2,1(0 pvXhmuXg vu kr ),2,1(0 ),2,1(0. min pvXh muXgts RXXf v u n 对优化问题： 现代设计方法 第二章 优化设计 7 把其中不等式和等式约束函数值经加权处理后 ， 和原目 标函数结合新的目标函数： ( ) ( ) ( ) ( )1 2 1 2 11 m i n , , pm k k k k uv uv X r r f X r G g X r H h X 这一新目标函数即为 惩罚函数 。 对应的优化问题就为无 约束优化问题 。 惩罚函数中的后两项称为 惩罚项 。 称为 惩罚因子 或加权因子 。 ( ) ( )12,kkrr 现代设计方法 第二章 优化设计 8 惩罚项满足下列要求： (1)当满足约束条件时，惩罚项的值很小或为 0； (2)当不满足约束条件时，惩罚项的值很大，即对不满足 约束条件的点的函数值进行惩罚。 新目标函数中，惩罚因子 是一系列的按 一定规则 变化 的值。当按照一定的法则改变数值时，就构成了一系列 的无约束优化问题，求解就可得到一系列的无约束的迭代点， 使其一步步迭代不断地逼近原约束优化问题的最优解。 ( ) ( )12,kkrr 现代设计方法 第二章 优化设计 9 数学证明： 当惩罚函数满足 时，上述惩罚函数在 过程中所产生的极小点 序列 将逐渐逼近于愿约束问题的最优解。即 ( ) ( ) 1 1 ( ) ( ) 2 1 ( ) ( ) ( ) 12 l i m ( ) 0 l i m ( ) 0 l i m ( , , ) ( ) 0 m kk u k u p kk v k v k k k k r G g X r H h X X r r f X k ()kX ( 0 ) ( 1 ) ( ) ( 1 ), , , , ,kkX X X X ( ) *lim k k XX 现代设计方法 第二章 优化设计 10 因此 ， 惩罚函数法又称 序列无约束极小化方法 ， 常称 SUMT(sequential unconstrained minimization technique)。 根据惩罚项的构成形式 ， 惩罚函数法可分为： 内点惩罚函数法 外点惩罚函数法 混合惩罚函数法 现代设计方法 第二章 优化设计 11 2.外点惩罚函数法（又称外点法） 对于约束优化问题： ),2,1(0)( ),2,1(0)(. )(m in pvXh muXgts RXXf v u n 外点惩罚函数法构造惩罚函数的形式为： p v v k m u u kk XhrXgrXfrX 1 2)( 1 2)()( ,0m a x, 现代设计方法 第二章 优化设计 12 分析： 对于不等式约束 ，当 满足约束条件时， 惩罚项为 0；当不满足约束条件时，惩罚项大于 0，这相当于 给不满足约束条件的迭代点在函数值上给予惩罚，以此来使 迭代点逐步向可行域边界靠近； 对于等式约束 ，也可以得出类似的结论。 因此，外点法既可处理不等式约束，也可处理等式约束。 ( ) 0ugX ()kX ( ) 0vhX 现代设计方法 第二章 优化设计 13 为了进一步理解外点法 ， 我们考虑一种只有不等式约束的 情况 ， 此时 ， 惩罚函数 (1)特征 与内点法相反 ， 外点法将惩罚函数定义于约束可行域之外 ， 且求解无约束问题的一系列迭代点是从可行域外部逼近原目标 函数的约束最优解 。 外点法可用来求解含不等式约束和等式约束的优化问题 。 2( ) ( ) 1 , m a x 0 , m kk u u X r f X r g X 现代设计方法 第二章 优化设计 14 从上式可以看出 ， 在可行域内 ， 约束函数值小于零 ， ， 惩罚项也等于零；在可行域外 ， 惩罚项大于零，惩罚项可分以下两 种情况： 此时可以清楚地看出，外点法的惩罚项是定义于可行域 之外的。事实上，外点法的迭代过程也是从可行域外一步步 向可行域边界逼近的。这正是外点法名称的由来。 00),(m a x Xg u 00),(m a x,0)( XgXg uu () 2() 1 0 , m a x , 0 0 u k m k uu u f X g X Xr f X r g X g X ( 当 时 ) ( 当 时 ) 现代设计方法 第二章 优化设计 15 惩罚项的大小还与惩罚加权因子 有关。当惩罚因子 按一个递增的正数序列 变化时，依次求解所对应的无约束极小化问题，将得到一个 极小点序列 随着 逐步增大，这个极小点序列将逐步逼近原约束优化问 题的最优解。 )(kr 0 1 2 ( ) ( 1 )kkr r r r r ( 0 ) ( 1 ) ( ) ( 1 ), , , , ,kkX X X X )(kr 现代设计方法 第二章 优化设计 16 (2)迭代步骤 步骤一 给定初始点 、收敛精度 、初始惩罚因子 和惩罚因子递增系数 ，置 ； 步骤二 构造惩罚函数 步骤三 求解无约束优化问题 ，得 令 )0(X r c 0k p v v k m u u kk XhrXgrXfrX 1 2)( 1 2)()( ,0m a x, ),(m in )( krX *X *)1( XX k 现代设计方法 第二章 优化设计 17 步骤四 判断收敛精度：若满足条件 则令 ，结束计算；否则， 令 ，转步骤二继续迭代。 )( )()( )( )()1( )()1( k kk kk Xf XfXf XX )()(, )1(*)1(* kk XfXfXX 1,)()1( kkcrr kk 现代设计方法 第二章 优化设计 18 (3)举例 用外点法求解约束优化问题： 收敛准则： 12 2 1 1 2 21 m i n . . 0 ( ) 0 f X x x s t g X x x g X x ( 1 ) ( ) 0.1 0.01kkXX ， 约 束 容 限 解释约束容限： 如果 (为给定的约 束容限 )，则认为点 落在约束边界上，亦即它是可行点。 ( ) ( )( ) ,kk uX g X满 足 (3)X 现代设计方法 第二章 优化设计 19 解： 利用外点法惩罚法构造无约束优化问题 此例只是为了说明外点法的思路，用微分法求解上述无约 束优化问题。 在可行域内 ： 知在可行域内 无极值点。 12 ( ) 2 2 ( ) 2 1 2 1 2 1 ( m in , ( ) ( ) k kk xx Xr x x r x x r x 可 行 域 内 ） （ 可 行 域 外 ） 01,01 21 xx 现代设计方法 第二章 优化设计 20 在可行域外 ，令 从上面两式解得 可见，对于不同的惩罚因子值，可以得到不同的极小点。 ( ) 2 ( ) 1 1 2 1 1 ( ) 2 12 2 1 4 ( ) 2 0 1 2 ( ) 0 kk k r x x x r x x r x x x 12 ( ) ( ) 2 ( ) 1 1 1, 2 ( 1 ) 4 ( 1 ) 2k k kxx r r r 现代设计方法 第二章 优化设计 21 取 进行迭代计算，迭代结果如下： 点 满足点距收敛准则，同时，它在约束容限范围内，因此， 终止迭代！输出结果。 ( 0 ) ( 1 ) ( ) ( )1 , 1 0k k kr r C r r ( 1 ) ( 1 ) ( 1 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 1 ) ( 3 ) ( 3 ) ( 3 ) ( 3 ) ( 2 ) 1 ( 0 . 2 5 , 0 . 4 3 7 5 ) , ( ) 0 . 6 8 7 5 1 0 , ( 0 . 0 4 5 5 , 0 . 0 4 7 9 ) , ( ) 0 . 0 9 3 4 , 0 . 4 4 1 0 0 ( 0 . 0 0 4 9 5 , 0 . 0 0 4 9 8 ) , ( ) 0 . 0 0 9 9 3 , 0 . 0 5 9 T T r X f X r X f X X X r X f X X X 当 时 ， 当 时 当 时 ， (3)X 现代设计方法 第二章 优化设计 22 (4) 选择 外点法惩罚因子按下式递增： 式中： C 惩罚函数，通常 C=5 10。 外点法惩罚因子 的合理取值很重要，若 太大，惩 罚项的作用就会很大，使惩罚函数的等值线变形或偏心，求 极值将会很困难；若 太小，将增加迭代次数，计算效率降 低。 多数情况下，取 =1， C=10时结果较好。 ()kr 1 kk Crr )0(r )0(r )0(r )0(r 现代设计方法 第二章 优化设计 23 3.内点惩罚函数法（又称内点法，限制在可行域内） (1)特征 该法是求解 不等式约束 最优化问题的一种有效的方法， 但不能处理等式约束 ，其特点是将新的无约束目标函数 惩罚函数定义在可行域内。 在可行域内，序列迭代点逐步逼近约束边界上的最优点。 这样，求解无约束问题时的搜索点总是保持在可行域内部。 现代设计方法 第二章 优化设计 24 对于约束优化问题 内点法求解时，惩罚函数的形式为： ),2,1(0)(. )(m in muXgts RXXf u n 适应于有平方项或 适应于无平方项或 或 m u uu m u u u m u u kk m u u kk XgInXgG Xg XgG XgInrXfrX Xg rXfrX 1 1 11 1 , 1 , 现代设计方法 第二章 优化设计 25 式中 惩罚加权因子，是递减的正数序列 c 惩罚因子的缩减系数，即 而 和 为 障碍项 。 kr 1 kk crr 0210 rrr m u u k Xgr 1 1 m u u k XgInr 1 现代设计方法 第二章 优化设计 26 由于内点法的迭代过程在可行域内进行，障碍项的作用 是阻止迭代点越出可行域。 若搜索过程中迭代点 X保持为可行点，满足约束条件，则 障碍项 必为正值，当 X远离约束边界时，惩罚函 数 是相当小的正值，这是惩罚作用很小，但当迭代 点靠近某一约束边界 时，则障碍项 的 值急剧增大并趋向无穷大，于是惩罚函数也随之急剧增大至 无穷大。 m u u k Xgr 1 1 krX , 0Xg u krX , 现代设计方法 第二章 优化设计 27 用内点法求解约束优化问题： 收敛准则：点距准则， 0 0. m in 12 2 2 11 21 xXg xxXgts xxXf 0.01 举例 现代设计方法 第二章 优化设计 28 解： 构造惩罚函数： 用解析法极值条件求解，令 联立求解得： 122121, xInxxInrxxrX kk 0 1 1 0 12 1 2 2 1 )( 2 12 2 1 1)( 1 xx r x xxx x r x k k )(2)( 2 )( 1 16 181, 4 181 kkk rrxrx 现代设计方法 第二章 优化设计 29 迭代过程 (取 ) ( 0 ) ( 1 ) ( ) ( )1 , 0 . 5k k kr r c r r 23 8.0,13 5.0,10 3.0 8 1 46 6.0,28 3.0,18 3.0 4 1 09.1,78 2.0,30 9.0 2 1 75.1,25.1,5.01 )3(3)3( )2(2)2( )1(1)1( )0(0)0( XfXr XfXr XfXr XfXr T T T T 时，当 时，当 时，当 时，当 按点距收敛准则，需要迭代多少次，请同学们自己判断。 现代设计方法 第二章 优化设计 30 当 时， 可知， 就是所求约束 优化问题的最优解。 从上面的例子可以看出，序列最优点 是以为参数的点列轨迹。 因内点法将惩罚函数定义在可行域内，故点 要严 格满足全部的约束条件，且应选择离约束边界较远些，即应 使 。 () 0kr 0,0,0 kTk XfX 0,0,0 * kTk XfXfXX krxx , * 0X ),2,1(00 muXg u 现代设计方法 第二章 优化设计 31 (2)初始惩罚因子 的选择 的选择会影响到迭代计算能否正常进行以及计算 效率的高低，值应适当。 若 太大，则开始几次构造的惩罚函数的无约束极 值点会离约束边界很远，将增加迭代次数，使计算效率降低。 若 太小，惩罚函数中的障碍项的作用就会很小， 使惩罚函数性态变坏，甚至难以收敛到原约束目标函数的极 值点。 0r 0r 0r 0r 现代设计方法 第二章 优化设计 32 目前，还没有一定的有效方法，往往要经过多次试算， 才能确定一个适当的 。 多数情况下，一般取 =1，然后根据试算的结果，加 以调整； 或按经验公式： 选取值 。 0r 0r m u u Xg Xf r 1 0 0 )0( 1 0r 现代设计方法 第二章 优化设计 33 (3)惩罚因子的缩减系数 C的选择 在构造序列惩罚函数时，惩罚因子 是一个逐次递 减到 0的数列，相邻两次迭代的惩罚因子关系式为： 其中， C 惩罚因子的缩减系数， 0C1， 通常取值为： 0.1 0.7。 kr )1()( kk Crr 一般来说， C值的大小对收敛速度无明显影响，在迭代过 程中不起决定性作用。 现代设计方法 第二章 优化设计 34 (4)收敛条件 内点法的收敛条件为： ( 1 ) ( 1 ) ( ) ( ) 1( ) ( ) ( 1 ) ( ) 2 , , k k k k kk kk X r X r Xr XX （ 值 差 准 则 ） 或 （ 点 距 准 则 ） 现代设计方法 第二章 优化设计 35 (5)内点法的迭代步骤如下 步骤一 选 ，可行初始点 不应在边界上，最好不 要靠近任何一个约束边界； 步骤二 选 ，令 k=0（迭代次数）； 步骤三 构造惩罚函数 ，选某一适当的无约束优 化方法，求 ，得到点 ，令 步骤四 判断迭代点是否收敛，若满足收敛条件，迭代终止， 约束最优解为： 否则，令 转步骤三。 )0(X )0(X 21)0( , Cr )(, krX )(,m in krX )(* krX ( 1 ) * ( )()kkX X r * ( 1 ) * ( 1 ), ( )kkX X f X f X ( 1 ) ( ) ,1kkr C r k k 现代设计方法 第二章 优化设计 36 5.混合惩罚函数法（又称混合法） 这种方法是将 内点法 和 外点法 的惩罚函数形式结合在一 起，扬长避短，可用来求解同时具有等式约束和不等式约束 函数的优化问题。 对于约束优化问题： ),2,1(0)( ),2,1(0)(. )(m in pvXh muXgts RXXf v u n 现代设计方法 第二章 优化设计 37 混合法求解时，惩罚函数的形式为： 障碍项，惩罚因子为按内点法选取，即 障碍项，惩罚因子为 ，当 时， ,满足外点法对惩罚因子的要求。 p v vk m u u kk Xh rXg rXfrX 1 2 1 )()( 11, m u u k Xgr 1 )( 1 0210 rrr p v vk Xhr 1 21 kr 1 0kr kr 1 现代设计方法 第二章 优化设计 38 可见，混合法对不等式约束采用内点法构造惩 罚项，对等式约束采用外点法构造惩罚项。 混合法的求解特点与内点法相同，迭代过程在 可行域内进行，初始点 ，惩罚因子初始值 、 惩罚因子缩减系数均可参考内点法选取。 0X 0r 现代设计方法 第二章 优化设计 39 二、复合形法 数学基础： 梯度法、方向导数、 k t条件 适用条件： 目标函数和约束函数均为 n维一阶连续可微函 数、可行域是连续闭集、求解不等式约束的一种直接解法。 可行方向法是用梯度去求解约束非线性最优化问题的一种 有代表性的直接解法，它是求解大型约束优化问题的主要方法 之一。其收敛速度快，效果好，但程序比较复杂，直接算法， 计算困难且工作量大。 现代设计方法 第二章 优化设计 40 【 本节思考题 】 1.可行方向、下降方向的几何意义。 2.最优下降可行方向的确定方法。 3.惩罚函数法的基本思想。 4.内点法和外点法分别是如何定义惩罚函数的？ 5.内点法、外点法、混合法分别有什么特点？ 现代设计方法 第二章 优化设计 41 【 作业 】 1.用可行方向法求解以下线性规划问题： T X xx xx xxts xxxf 0,0 0, 2 12. 1)2()1()(m in )0( 21 21 21 2 2 2 1 2.用外点法求解： 03. 12)(m in 2 1 2 2 2 1 xts xxxxf
展开阅读全文