现代设计方法-优化设计5-约束优化

1、现代设计方法优化设计部分优化设计部分黄正东，吴义忠二0一三年二月本章主要内容本章主要内容 优化设计概述优化设计概述 优化设计的数学基础优化设计的数学基础 一维探索优化方法一维探索优化方法 无约束优化方法无约束优化方法 约束问题优化方法约束问题优化方法 优化设计若干问题优化设计若干问题 优化设计概述优化设计概述 优化设计的数学基础优化设计的数学基础 一维探索优化方法一维探索优化方法 无约束优化方法无约束优化方法 约束问题优化方法约束问题优化方法 优化设计若干问题优化设计若干问题 单纯形与复合形法单纯形与复合形法 随机随机方向法方向法 可行方向法可行方向法 SQPSQP方法方法 惩惩罚函数法罚函数

2、法 约束问题优化方法约束问题优化方法 直接法直接法复合形法随机方向法可行方向法序列二次规划 间接法间接法 惩罚函数法直接法：直接法：在可行域内迭代找一序列点，每步降低目标函数值，直至达到最优解。间接法：间接法：将约束问题 变换为一序列无约束问题、或简单的约束问题，这些子问题的解收敛于原问题的解。1. 无约束单纯形法(1) (1) 算法思想算法思想从初始单纯形开始，逐个去除最大值，翻滚（收缩或压从初始单纯形开始，逐个去除最大值，翻滚（收缩或压缩单纯形）朝着最小值逼近，直到单纯形边长小于精缩单纯形）朝着最小值逼近，直到单纯形边长小于精度值。度值。单纯形单纯形（SimplexSimplex）概念概念

3、: : n n维空间中的维空间中的n+1n+1面面体体无约束单纯形法-（1）反射f(xf(xh h)=maxf(x)=maxf(x0 0), f(x), f(x1 1), ), ,f(x,f(xn n) ) - - 高点高点f(xf(xl)=minf(x)=minf(x0 0), f(x), f(x1 1), ), ,f(x,f(xn n) - ) - 低点低点x x= =nhiiinx, 01-除最高点外的所有点的形心除最高点外的所有点的形心xhx2x1xxrx xr r= =x x+a(+a(x x-x-xh h) )-反射点，反射点，a a反射系数，一般取反射系数，一般取 a=1.a=1

4、.无约束单纯形法-（2）扩张分三种分三种情况情况产生产生新新点点: :x xe e= =x x+y(x+y(xr r- -x x) )若若f(xf(xr r) ) f(xf(xe e),),则则x xe e -x-xh h否则，否则， x xr r - x- xh h1 1。如果。如果f(xf(xl)f(x)f(xr), ), 进一步扩展进一步扩展 扩展系数扩展系数y1, y1, 一般一般y=2.y=2.xhx2xlxxrxef f(x xr r)比所有单纯形点上值小比所有单纯形点上值小不进一步扩展不进一步扩展, ,避免狭窄单纯形避免狭窄单纯形无约束单纯形法分三种分三种情况情况产生产生新新点点

5、: :2 2。如果如果maxf(xmaxf(xi i),i),i hh f(xf(xr) ) f(xf(xl),),则则 x xr r - x- xh hxhx2x1xxrf f(x xr r)在单纯形点上值之间在单纯形点上值之间, ,但最少比第二最大但最少比第二最大值小值小.3 3。如果如果f(f(x xr r)maxf(x)maxf(xi i),),i i h h,则则 f( f(x xh h)=minf()=minf(x xh h),f(),f(x xr r) 收缩收缩x xc c= =x x+b+b( (x xh h- -x x), 0b1), 0b-x xh h 4.4.如果如果f(

6、xf(xc c) ) f(f(x xh h) ), ,x xc c -x xh h（上图上图） 否则否则（反射点和收缩点函数值都比较大（反射点和收缩点函数值都比较大），），以以x xl为中心压缩整个为中心压缩整个单纯形（极小值点在压缩的单纯单纯形（极小值点在压缩的单纯性内）：性内）： x xi i=x=xi i+0.5(x+0.5(xl-xi), ), i i=0,1,2,=0,1,2,n,n无约束单纯形法无约束单纯形法-（4）压缩）压缩xhx2xlx2xhf f(x xr r) 最少最少比第二最大比第二最大值大值大.2. 复合形法(1) (1) 算法思想算法思想对于n维变量空间,单纯形是n+

7、1个顶点.复合形法是多个单纯形合并成的超多面体,顶点数n+1.复合形法与单纯形极为相似,其不同之处:1.复合形法不限制顶点个数为n+1,复合形法顶点个数是k, 2nkn+1.2.2.复合形法需要检查顶点的可行性复合形法需要检查顶点的可行性, , 即是否满足约束即是否满足约束. .初始复合形法生成初始复合形法生成1.1.随机测试找到一个可行点随机测试找到一个可行点2.2.随机生成其它点随机生成其它点3.3.计算可行点的中心点计算可行点的中心点4.4.中心点不可行时中心点不可行时, ,不计最远点不计最远点 重新计算中心重新计算中心5.5.将不可行点向中心拉靠将不可行点向中心拉靠6.6.初始复合形初

8、始复合形（1） 计算(2) (2) 算法算法 ( (反射、扩张、收缩、压缩）反射、扩张、收缩、压缩）XhXgXlXc,.,2 , 1),(min)(,.,2 , 1),(max)(,.,2 , 1),(max)(kjXfXfhjkjXfXfkjXfXfjljgjh)(11 ,.,2, 1hjkjjcXkX（2） 计算最高点次高点最低点最高点之外其它点的中心Step 1Step 1： 反射反射成功反射的条件是：g(Xr) f(Xh) 若f(Xr)相对于f(Xh)下降较多，如f(Xr) f(Xg)，则执行扩张步骤：0 . 1)(crreXXXXXhXgXlXcXrXe若f(Xe) f(Xc)， 则

9、执行收缩步骤：7 . 0, 1)(取hchkXXXX若f(Xk)5时,可取k2n.3. 随机方向法（1）在可行域内选一初始点x(0),以给定的步长a=a(0),沿某随机选取的方向S(1)取探索点x=x(0)+aS(1),若该点同时符合下降性（f(x)m(取50-100)次随机采样，均未找到成功的探索方向S(i)，则将步长a减半。（4）若步长aeps均未找到成功的探索方向S(i)，结束。无一维搜索无一维搜索算法思想：算法思想：随机方向法生成随机方向：生成随机方向：endyrandnifori);1 ,1(12 );1 ,0()1 ,0( ,.,2 ,1 4. 可行方向法可行方向法是用梯度去求解约

10、束非线性最优化问题的一种有代表性的直接解法，是求解大型约束优化问题的主要方法之一。其收敛速度快，效果好，但程序比较复杂，计算困难且工作量大。数学基础：梯度法、方向导数、K-T条件 线性规划，线性规划，约束一维搜索约束一维搜索适用条件：目标函数和约束函数一阶连续可微, 只有不等式约束。可行方向法 在可行域内选择一个初始点，当确定了一个可行方向S(k)和适当步长后，按公式进行迭代计算，通过调整可行方向，使其既不超出可行域，又使目标函数值有所下降，经过若干次迭代，使迭代点逐步逼近约束最优点。 (1)算法思路)()()()1(kkkkSXX(2)产生可行方向的条件可行条件方向S(k)可行，是指沿该方向

11、作微小移动后，所得到的新点应是可行点。 01g02g04g03g)(kX)(kS01g02g04g03g)(kX)(kS)()(2kXg01g02g04g03g)(kX)(kS)()(2kXg)()(3kXg可行的含义： 若点X(k)在J个约束面的交集上（即点X(k)有J个起作用约束），要满足可行条件，方向S(k)应和这J个约束函数在点X(k)的梯度 的夹角均大于等于900，若用向量关系式表示为： )()(kkuIuXg)( 0)()()(kkTkiIiSXg可行条件可行条件下降条件 方向下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的，而且下降的愈快愈好，显然，如果负梯度方向是

12、可行方向，那么沿负梯度方向进行移动最有利。 满足下降条件的方向S(k)应和目标函数在点X(k)的梯度 交成钝角。用向量关系式可表示为：)(kXf0)()(kTkSXf下降条件下降条件 综上所述，可行方向就是既满足可行条件，又满足下降条件的方向。用向量关系式表示为： )( 0)()()(kkTkuIuSXg0)()(kTkSXf可行条件可行条件下降条件下降条件同时满足上面两个条件的方向称为可行方向，又称为下降可行方向。可行方向很多，哪一个最快最优呢？可行方向很多，哪一个最快最优呢？最佳下降可行方向最佳下降可行方向 在一个点的所有下降可行方向中，使目标函数取得最大下降量的方向称为最佳下降可行方向，

13、显然，当点X(k)处于可行域内时，目标函数的负梯度方向就是最佳下降可行方向，当点X(k)处于几个起作用约束的交点或交线上，即 kkikkiIiXgIiXg00)()(合的起作用约束的下标集为点）（kkXI式 和 只能提供下降可行方向的范围，而不能直接给出最佳下降可行方向，但是可以在满足上述可行条件的前提下，通过方向导数极小化（保证最佳）的求解得到最佳下降可行方向。)(0)()()(kkTkiIiSXg 目标函数在S方向的方向导数反映了目标函数值沿S方向的变化情况。方向导数越大，则目标函数值增加越快，反之，方向导数越小，目标函数值下降越快。 无约束情况下，负梯度方向是最好的方向。0)()(kTk

14、SXf目标函数f(X)在点 X(k)的方向导数SXfSXfT(k)(k)由于梯度 是常数向量，则方向导数是S的线性函数，故最佳可行方向的寻求可归结为以下线性线性规划规划问题。 )(kXf ), 2 , 1( 11)(0. .min)()(nisIjSXgtsSXfSikTkjTk 为为常常数数向向量量式式中中，)(21,kuTnXgsssS 每次尽量沿着每次尽量沿着负梯度的方向！负梯度的方向！约束梯度法约束梯度法序列线性规划法序列线性规划法（4）可行方向法的迭代步骤1）给定初始内点X(0)，收敛精度和约束允差，置k=0；2）确定点X(k)的起作用约束集合 当Ik为空集（表示约束都不起作用），且

15、点X(k)在可行域内时，如果 ，则令 ,终止计算;否则,令 ，转（5）； 当为非空时（表示有起作用约束），转（3）；muXguXIkukk, 2 , 1,)()( )(kXf，)(*kXX )(*kXfXf kkXfS3）收敛判断：点X(k)是否满足K-TK-T条件条件； 令 ，解出 若 ，输出 ，终止迭代； 若 ，转4）. 00ukuIuukXgXfk 0kuIuukXgXfku 0全全大大于于u，)(*kXX )(*kXfXf0不不全全大大于于u4）求解线性规划问题 得到S*，令S(k)=S*（最佳下降可行方向）；5）在方向S(k)上进行约束一维搜索约束一维搜索得点X(k+1)，令k=k+

16、1，转（2）。 ), 2 , 1( 11)(0. .min)()(nisIuSXgtsSXfSikTkuTk (3)约束一维搜索 所谓约束一维搜索是指求解一元函数约束极小点的算法，与前面讲的一维搜索相比，其特点在于：确定初始区间时，对产生的每一个探测点都进行可行性判断，如果违反了某个或某些约束条件，就必须减小步长因子，以使新的探测点落在最近的一个约束曲面上或约束曲面的一个允许的区间内。 约束容限：约束容限：如果如果 ( (给定的约束容给定的约束容限限) )，则认为点，则认为点X(k)落在约束边界上，亦即它是可行点。落在约束边界上，亦即它是可行点。 ( )( )(),kkuXgX满足*4. SQ

17、P法（序列二次规划）（约束拟牛顿法，约束变尺度法）每次尽量沿着拟每次尽量沿着拟牛顿的方向！牛顿的方向！可行条件可行条件5. 惩罚函数法 内点法 外点法 混合法 惩罚函数法是求解约束优化问题的间接法的一种。它是将目标函数和约束条件构造成一个新的目标函数，将约束最优化问题转化为无约束最优化问题，然后利用各种有效的无约束最优化解法求解而得到约束最优化的近似解。这是一种使用广泛的有效的间接解法。1.惩罚函数法的基本思路 将不等式约束 、等式约束 和待定系数 （加权因子）经加权转化后，与原目标函数f(X)一起组成一个新的目标函数 （惩罚函数），然后对它求最优解。 ), 2 , 1(0muXgu ), 2

18、 , 1(0pvXhv kr krX, ), 2 , 1(0), 2 , 1(0. .minpvXhmuXgtsRXXfvun 对于优化问题对于优化问题把其中不等式和等式约束函数值经加权处理后，和原目标函数结合新的目标函数: ( )( )( )( )121211min,pmkkkkuvuvX rrfXrG gXrH hX惩罚函数惩罚函数 惩罚函数中的后两项称为惩罚项。惩罚项满足下列要求： 当满足约束条件时，惩罚项的值很小或为0； 当不满足约束条件时，惩罚项的值很大，即对不满足约束条件的点的函数值进行惩罚。 新目标函数中， 称为惩罚因子或加权因子，它们是一系列的按一定规则变化的值。当按照一定的法

19、则改变 的数值时，就构成了一系列的无约束优化问题，求解这些优化问题可得到一系列的无约束的迭代点，使其一步步迭代，不断地逼近原约束优化问题的最优解。 )(2)(1kkrr、)(2)(1kkrr、数学上可以证明：当惩罚函数满足( )( )11( )( )21( )( )( )12lim()0lim()0lim(,)()0mkkukupkkvkvkkkkrG gXrH h XX rrf X时，上述惩罚函数在 过程中产生的极小点序列将逐渐逼近于原约束优化问题的最优解。即 k (0)(1)( )(1),kkXXXX( )*limkkXX 惩罚函数法又称序列无约束极小化方法，常称SUMT（ sequent

20、ial unconstrained minimization technique）。根据惩罚项的构成形式，惩罚函数法可分为：外点惩罚函数法内点惩罚函数法混合惩罚函数法。 2.外点惩罚函数法), 2 , 1(0)(), 2 , 1(0)(. .)(minpvXhmuXgtsRXXfvun pvvkmuukkXhrXgrXfrX12)(12)()(, 0max,外点惩罚函数法构造惩罚函数的形式为： 对于约束优化问题 分析： 对于不等式约束 ，当 满足约束条件时，惩罚项为0；当不满足约束条件时，惩罚项大于0，这相当于给不满足约束条件的迭代点在函数值上给予惩罚，以此来使迭代点逐步向可行域边界靠近； 对

21、于等式约束 ，也可以得出类似的结论。()0ugX ( )kX()0vh X 外点法既可处理不等式约束，也可处理等式约束。外点法既可处理不等式约束，也可处理等式约束。 为了进一步理解外点法，我们考虑一种只有不等式约束的情况，此时，惩罚函数1 1）特征）特征 2( )( )1,max 0,mkkuuX rfXrgX根据对惩罚项性质的分析，惩罚项可分以下两种情况：( )2( )10,max,00ukmkuuufXgXX rfXrgXgX (当时) (当时) 可以清楚地看出，外点法的惩罚项是定义于可行域之外的。事实上，外点法的迭代过程是从可行域外一步步向可行域边界逼近的。这正是外点法名称的由来。 惩罚

22、项的大小还与惩罚加权因子r(k)有关。当惩罚因子按一个递增的正数序列变化时，依次求解所对应的无约束极小化问题，将得到一个极小点序列 随着r(k)逐步增大，这个极小点序列将逐步逼近原约束优化问题的最优解。 012( )(1)kkrrrrr(0)(1)( )(1),kkXXXX2） 选择 外点法惩罚因子按下式递增： 式中：C惩罚因子递增系数，通常C=510。 外点法惩罚因子 的合理取值很重要， 若 太大，惩罚项的作用就会很大，使惩罚函数的等值线变形或偏心，求极值将会很困难；若 太小，将增加迭代次数，计算效率降低。 多数情况下，取 ，C=10时效果较好。 ( )kr 1kkCrr)0(r)0(r)0

23、(r1)0(r3）迭代步骤步骤1 给定初始点 、收敛精度 、初始惩罚因子r(0)和惩罚因子递增系数 ，约束容限，并置 ；步骤2 构造惩罚函数步骤3 求解无约束优化问题 ，得 ,令 )0(Xc0k pvvkmuukkXhrXgrXfrX12)(12)()(, 0max,),(min)(krX*X*)1(XXk步骤4 判断收敛精度：若满足条件 则令 ，结束计算；否则，令 ，转步骤2，继续迭代。)()()()()()()()()1()()()1(kukkkkukkXgXfXfXfXgXX与与或或与与)()(,)1(*)1(*kkXfXfXX1,)()1(kkcrrkk例. 用外点法求解约束优化问题：

24、收敛准则： (1)( )0.10.01kkXX，约束容限 01.min1xXgtsxXf3.内点惩罚函数法1）特征 该法是求解不等式约束最优化问题的一种有效的方法，但不能处理等式约束，其特点是将新的无约束目标函数惩罚函数定义在可行域内。在可行域内，序列迭代点逐步逼近约束边界上的最优点。这样，求解无约束问题时的搜索点总是保持在可行域内部。 ), 2 , 1(0. .minmuXgtsRXXfun 对于约束优化问题对于约束优化问题内点法求解时，惩罚函数的形式为 muuumuuumuukkmuukkXgXgGXgXgGXgrXfrXXgrXfrX1111ln 1 ln, 1, 或惩罚项的特点：惩罚项

25、的特点：当迭代点在可行域内且远离边界时，两种惩罚项 和 都是很小的正值，这时候惩罚作用很小；当迭代点靠近边界时，则惩罚项的值急剧增大并趋向无穷大，于是惩罚函数值也随之急剧增大并趋向无穷大。这样等于在约束边界筑起一道“屏障”，使迭代点始终不能超出可行域。 muukXgr11 )(lnXgruk惩罚因子的特点：惩罚因子的特点：内点惩罚函数法的惩罚因子r(k)是一个递减的正数序列， ，c是惩罚因子的缩减系数，即当惩罚因子 时，才能求得在约束边界上的最优解。 1kkcrr 0210 rrr0)(kr2）初始惩罚因子r(0)的选择 初始惩罚因子的选择会影响到迭代计算能否正常进行以及计算效率的高低，r(0

26、)的值应适当。 若r(0)太大，则开始几次构造的惩罚函数的无约束极值点会离约束边界很远，将增加迭代次数，使计算效率降低。 若r(0)太小，惩罚函数中的障碍项的作用就会很小，使惩惩罚函数性态变坏罚函数性态变坏，甚至难以收敛到原约束目标函数的极值点。 目前，还没有一定的有效方法，往往要经过多次试算，才能确定一个适当的r(0)。 多数情况下，一般取r(0)1 ，然后根据试算的结果，加以调整； 或按经验公式取值 muuXgXfr100)0(1使惩罚项和原目标使惩罚项和原目标函数在惩罚函数中函数在惩罚函数中的作用相当。的作用相当。3）罚因子缩减系数C的选择 在构造序列惩罚函数时，惩罚因子r(k)是一个逐次递减到0的数列，相邻两次迭代的惩罚因子关系式为：其中，c是惩罚因子的缩减系数，通常取值为0.1-0.7。 1kkcrr一般来说，一