第五章约束优化方法

1

第五章约束优化方法

5.1约束优化问题的最优解5.2约束优化问题极小点的条件

5.3常用的约束优化方法

5.3.1约束坐标轮换法5.3.2约束随机方向法5.3.3复合形法5.3.5惩罚函数法2概述约束优化问题最优解最优值最优点约束最优解和无约束最优解无论是在数学模型上还是几何意义上均是不同的概念3等值线等值线族的中心无约束最优解解：等值线的共同中心.数学模型:4数学模型:可行域约束最优解

5无约束最优点约束最优点6约束优化问题的类型

1.不等式约束优化问题(IP型)2.等式约束优化问题(EP型)3.一般约束优化问题(GP型)7约束优化方法分类约束优化方法

约束坐标轮换法直接法：约束随机方向法

复合形法间接法：惩罚函数法

直接法：设法使每一次迭代产生的新迭代点限制在可行域内，且一步一步的降低目标函数值，直至最后获得一个可行域内的约束最优解。间接法：将约束优化问题通过一定形式的变换，转化为无约束优化问题，然后采用约束优化方法进行求解。85.3.1约束坐标轮换法基本思想:与无约束坐标轮换法类似,依此沿坐标轴方向寻优,逐步逼近最优点。9任取一个初始点取初始步长α0沿e1方向检查可行性:适用性:检查......加速步长检查可行性:适用性:10沿e2方向检查可行性:适用性:检查可行性:适用性:检查可行性:适用性:检查可行性:适用性:11沿e1方向检查可行性:适用性:检查可行性:适用性:沿e2方向检查可行性:适用性:检查......12沿坐标轴方向找不到合适的点:缩减初始步长

α0←0.5α0

继续迭代终止准则:

α0≤ε约束坐标轮换法与无约束坐标轮换法的区别：①步长

无约束:最优步长

约束:加速步长②对每一个迭代点的检查

无约束:检查适用性

约束:检查适用性和可行性③终止准则

无约束:点距准则

约束:步长准则13特点:约束坐标轮换法具有算法明了、迭代简单、便于设计者掌握运用等优点。但是，它的收敛速度较慢，对于维数较高的优化问题(例如10维以上)很费机时。另外，这种方法在某些情况下还会出现“死点”的病态，导致输出伪最优点。

避免输出伪最优点的办法:1、输入不同的初始点2、用不同的不长多次计算14基本原理：典型的“瞎子爬山”式的数值选代解法。在可行域内，任选初始点x(0)，以给定的步长a=a0

，沿按某方法产生的随机方向S(1)取探索点x=x(0)+aS(1），若该点同时符合下降性（F(x)<F(x(0)))和可行性（x∈D)则表示x点探索成功。并以它为新的起始点，继续按上面的迭代公式在S(1）方向上获取新的成功探索点……..

5.3.2约束随机方向法155.3.2约束随机方向法任取一个初始点取初始步长α0利用随机函数构成随机方向S(1)

检查可行性:适用性:检查若m个方向都不行,则减小步长:α0←0.5α0终止准则:

α0≤ε16说明当在某个转折点处沿m个(预先限定的次数)随机方向试探均失败，则说明以此点为中心，α0为半径的圆周上各点都不是适用、可行点。此时，可将初始步长α0缩半后继续试探。直到α0≤ε，且沿m个随机方向都试探失败时，则最后一个成功点(如图中的x(3))就是达到预定精度ε要求的约束最优点，迭代即可结束。m是预先规定在某转折点处产生随机方向所允许的最大数目。一般可在50~500范围内选取。约束随机方向法的搜索方向比坐标轮换法要灵活得多。当预定的随机方向限定数m足够大时，它不会像约束坐标轮换法那样出现“病态”而导致输出伪最优点。

17随机搜索方向的产生在（a,b）之间的随机数：yi=ai+

(bi–ai)

（-1,1）之间的随机数：yi=2-1设是在区间(一l，1)上的两个随机数。将它们分别作为坐标轴上的分量所构成的向量即为相应的二维随机向量，其单位向量：同理，n维问题,随机方向的单位向量：在算法语言所使用的函数库中，有一种随机函数RND(X)。利用这一随机函数可在程序运行过程中产生一个0到1之间的随机数。

(i＝l，2，…，n)18约束随机方向搜索法的特点：对目标函数的性态无特殊要求，程序设计简单，使用方便。在维数较少的情况下是一种十分有效的方法，适用于小型问题。195.3.3复合形法基本思想：在可行域中选取K个点作为一复合形（多面体）的K个顶点。比较各点函数值的大小，去掉函数值最大所对应的最坏点，而代之最坏点的映射点构成新的复合形。不断重复上述过程，使复合形不断向最优点移动和收缩，直至满足选代精度为止。

132X0X(R)n+l≤k≤2n20[引例]

设有一约束优化问题的数学模型21一、复合形法的基本思想步骤：第一步：初始复合形的构成

顶点X(1)、X(2)、X(3)第二步：对复合形进行

调优迭代计算顶点X(1)、X(2)、X(3)

F1>F2>F3

↓↓

X(H)

X(L)

坏点好点先求出除坏点外，其余各点构成的图形的形心点X0再求坏点X(H)相对于形心点X0的映射点

X(R)132X0X(R)22步骤：第一步：初始复合形的构成

第二步：对复合形进行调优迭代计算

形心点X0

映射点

X(R)

α:反射系数，一般开始是取α=1.3132检查可行性:适用性:新复合形4点的映射复合形的收缩23二、初始复合形的构成

方法一:试凑法方法二:随机产生(1)产生K个随机点随机数

(i＝l，2，…，n)(2)将非可行点调入可行域123424终止条件:25例:用复合形法求解下例约束最优化问题，迭代精度取

解：取复合形的顶点数:(1)获得初始复合形:本例采用人为给定四个点检验各点是否可行：将各点的坐标值代入以上三个约束方程，均满足约束要求，这四个点为可行点，用作初始复合形的四个顶点26(2)迭代计算获得新复合形计算复合形各顶点目标函数值，

定出最坏点最好点计算除坏点外其余各顶点的中心

将代入诸约束条件均满足，可知在可行城内。

取，求坏点的映射点

在可行域内

27计算并与比较：

用替换，亦即替换构成新的复合形：

比较各点目标函数值，定出最坏点:最好点:

（3）检验迭代终止条件

2829复合形法的特点:

对目标函数及约束函数无特殊要求，适应性强，计算量一般，收敛较快，适用中小型问题。是现有解不等式约束优化问题的一种重要的直接法。305.3.5惩罚函数法将约束优化问题通过一定形式的变换，转化为无约束优化问题，然后采用约束优化方法进行求解转化必须满足条件：1、不破坏原约束问题的约束条件，

2、最优解必须归结到原约束问题的最优解上去。约束优化问题的间接法有:消元法、拉格朗日乘子法、

惩罚函数法等.31minφ(x，r(k)，m(k)) (5.56)x∈Rn式中，φ(x，r(k)，m(k))为增广函数，称为惩罚函数，简称罚函数

将一般约束优化问题数学模型minF(x)x∈Rn：gu(x)≥0，u＝l，2，…，phv(x)=0，v=1，2，…，q转化成为一个如下的无约束优化问题构造的新目标函数一般形式为惩罚函数法惩罚项32按照惩罚函数构成的形式不同，惩罚函数法又分为三种：1、内点惩罚函数法2、外点惩罚函数法3、混合惩罚函数法33一、内点惩罚函数法基本思想：将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近原目标函数约束边界上的最优点。将约束优化问题：

minF(x)x∈:gu(x)≥0(u=12……m)转化为无约束优化问题

其中：r(1)>r(2)>r(3)…>r(k)…>0是一个递减的正值数列：

r(k)＝Cr(k-1)，

0＜C＜1

(k)=0

34内点惩罚函数法的思路:当X由可行域内靠近任一约束边界时,惩罚项值趋于无穷大,所以它就像围墙一样阻止迭代点越出约束边界.条件1：不破坏原约束问题的约束条件35minф(x,r(k))=min{F(x)+r(k)∑（1/gu(x)）}条件2：最优解必须归结到原约束问题的最优解上去36解：若用内点法求解此约束最优化问题，由式知惩罚函数为将函数对求导，得:令:解得无约束极小值的点列为

:例:用内点法求解

的约束最优化问题。

无约束极小值点列相应的惩罚函数值为

3738序列极小点都在可行域内39初始点x(0)的确定

自定法:搜索法

先任取一个设计点x(k)；计算x(k)点的诸约束函数值gu(x(k))，u＝1，2，…，p若：构造：按照该数学模型解出的最优点x*，至少比原设计点x(k)多满足一个约束条件

重复数次，直到所有的约束条件都得到满足，最终可取得在可行域内部的初始点x(0)。40

关于几个参数的选择(1)初始罚因子r(0)的选取一般可取初始罚因子r(0)＝1~50也有建议取：(2)递减系数C的选择

通常建议取C＝0.1~0.541内点惩罚函数法的特点:在给定一个可行初始方案后，能求出一系列逐步得到改进的可行的设计方案。但只适用于解不等式约束优化问题，且初始点须在可行域内。42=

已知约束优化问题:试写出内点罚函数,并选出初始迭代点.内点罚函数:例：43例：桁架设计问题：minF(x)=1.57x1

x=[x1x2]T∈

44设有不等式约束优化问题：构造外点法惩罚函数的常见形式如下：惩罚因子r(k)规定取正。且在优化过程中r(k)取为递增数列

r(k)=Cr(k-1)，C＞1则将保证(k)=∞二、外点惩罚函数法基本思想：将新目标函数定义于可行域外，序列迭代点在可行域外逐步逼近原目标函数约束边界上的最优点。45式中:外点惩罚函数法的思路：可行域内时,新目标函数就是原目标函数,当X位于可行域外时,惩罚项为正值,新目标函数值增大,就构成了对不满足约束条件时的一种”惩罚”.且离可行域越远,惩罚就越严厉.当r(k）不够大时，罚函数（新目标函数）的极小值在可行域外，即惩罚不够，可加大r(k），随着r(k）的增大，使新目标函数）的极小点越来越逼近原目标函数极小点。可行域外可行域内46对于解不等式约束优化问题minF(x)＝xx∈R1

：g1(x)=x－1≥0用外点法构造惩罚函数，具体构造形式如下：写成另一种形式例47令:解得无约束极小值的点列为

:无约束极小值点列相应的惩罚函数值为

求惩罚函数极小点:

48由此可见，当惩罚因子为一递增正值数列时，其极值点离约束最优点愈来愈近，的差值与愈来愈小。当时，，亦即逼近于真正的约束最优解。无约束极值点列随值递增从可行域外向最优点收敛。

49对几个问题的讨论初始点x(0)的选取:外点法的初始点x(0)可以任选，即在可行域与非可行域选取均可。(2)初始罚因子r(0)和递增系数C的选取初始罚因子r(0)选得是否恰当，对算法的成败和计算速度仍有着显著的影响。因此，选取时要谨慎。递增系数C的取值，一般影响不太显著，但也不宜取得过大。通常取C＝5~10。(3)约束容差带用外点法求解时，由于罚函数的无约束最优点列是从可行域外部向约束最优点逼近的，所以最终取得的最优点一定是在边界的非可行域一侧。严格地说，它是一个非可行点。这对某些工程问题可能是不允许的。为了解决这一问题。可在约束边界的可行域一侧加一条容差带，如图5.21。这就相当于将约束条件改为gu(x)－δu≥0，u=1，2，…，p式中的δu是容差量，一般可取δu=10－3~10－4。

50约束容差带。51外点法不但可以解不等式约束优化问题，而且还可以解等式约束优化问题

用外点法求解二维等式约束优化问题：按外点法的基本思想，构造惩罚函数52

外点法的特点外点法既可解不等式约束优化问题，也能解等式约束优化问题，且其初始点x(0)可任选，即在可行域中或非可行域中均可。其缺点是序列无约束最优点是一系列的非可行点，对于工程设计一般是不可取的。为使最终的迭代点能落入可行域，必须设置约束容差带。53例：已知约束优化问题:试写出外点罚函数,并选出初始迭代点.外点罚函数:54三、混合法

用罚函数法解决有等式约束和不等式约束的一般约束（GP型）优化问题的方法，把它称为混合惩罚函数法，简称混合法。

一般约束优化问题的数学模型

minf(x)x∈ÐÐ:gu(x)≥0(u=12……p)hv(x)=0(v=12……q,q<n)55内点形式的混合型惩罚函数法r(k)---递减m(k)---递增初始点必须是严格的内点为了统一用一个内点法惩罚因子,上式也可写成:不等式约束部分按内点法形式处理r(k)---递减56r(k)---递增外点形式的混合型惩罚函数法不等式约束部分按外点法形式处理57如何判断优化结果的正确性:1、约束优化问题，最优点大多位于边界上。2、输入不同的初始点多次计算。3、用不同的方法解。上机：第七周周一和周三晚上18:00-21：001、了解各种方法的基本思想和特点2、P130题237应用实例一、机械优化设计的一般过程机械优化设计的全过程一般可分为如下几个步骤:1)建立优化设计的数学模型。

2)选择适当的优化方法。

3)编写计算机程序。

4)准备必要的初始数据并上机计算。

5)对计算机求得的结果进行必要的分析。其中建立优化设计数学模型是首要的和关键的一步，它是取得正确结果的前提，优化方法的选择取决于数学模型的特点，例如优化问题规模的大小，目标函数和约束函数的性态以及计算精度等。在比较各种可供选用的优化方法时，需要考虑的一个重要因素是计算机执行这些程序所花费的时间和费用，也即计算效率。正确地选择优化方法，至今还没有一定的原则。通常认为，对于目标函数和约束函数均为显函数且设计变量个数不太多的回题，惩罚函数法较好;对函数易于求导的问题，以可利用导数信息的方法为好;对求导非常困难的问题则应选用直接解法，例如复合形法;对于高度非线性的函数，则应选用计算稳定性较好的方法，例如BFGS变尺度法和内点惩罚函数法相结合的方法。编写计算机程序对于使用者来说，已经没有多少工作要做了，因为已有许多成熟的优化方法程序可供选择。使用者只需要将数学模型按要求编写成子程序嵌入已有的优化程序即可。步骤4)和5)对机械设计工作者来说，通常不存在原则上的困难。建立数学模型的基本原则建立数学模型的基本原则是优化设计中的一个重要组成部分。优化结果是否可用，主要取决于所建立数学模型是否能够确切而又简洁地反映工程问题的客观实际。在建立数学模型时，片面地强调确切，往往会使数学模型十分冗长、复杂，增加求解问题的困难程度，有时甚至会使问题无法求解;片面强调简洁，则可能使数学模型过份失真，以致失去了求解的意义。合理的做法是在能够确切反映工程实际问题的基础上力求简洁。设计变量、目标函数和约束条件是组成优化设计数学模型的三要素，下面分别予以讨论。1.设计变量的选择机械设计中的所有参数都是可变的，但是将所有的设计参数都列为设计变量不仅会使问题复杂化，而且是没有必要的。例如材料的机械性能由材料的种类决定，在机械设计中常用材料的种类有限，通常可根据需要和经验事先选定，因此诸如弹性模量、泊松比、许用应力等参数按选定材料赋以常量更为合理;另一类状态参数，如功率、温度、应力、应变、挠度、压力、速度、加速度等则通常可由设计对象的尺寸、载荷以及各构件间的运动关系等计算得出，多数情况下也没有必要作为设计变量。因此，在充分了解设计要求的基础上，应根据各设计参数对目标函数的影响程度认真分析其主次，尽量减少设计变量的数目，以简化优化设计问题。另外还应注意设计变量应当相互独立，否则会使目标函数出现“山脊”或“沟谷”，给优化带来困难。2.目标函数的确定目标函数是一项设计所追求的指标的数学反映，因此对它最基本的要求是能够用来评价设计的优劣，同时必须是设计变量的可计算函数。选择目标函数是整个优化设计过程中最重要的决策之一。有些问题存在着明显的目标函数，例如一个没有特殊要求的承受静载的梁，自然希望它越轻越好，因此选择其自重作为目标函数是没有异议的。但设计一台复杂的机器，追求的目标往往较多，就目前使用较成熟的优化方法来说，还不能把所有要追求的指标都列为目标函数，因为这样做并不一定能有效地求解。因此应当对所追求的各项指标进行细致的分析，从中选择最重要最具有代表性的指标作为设计追求的目标。例如一架好的飞机，应该具有自重轻、净载重量大，航程长，使用经济，价格便宜，跑道长度合理等性能，显然这些都是设计时追求的指标。但并不需要把它们都列为目标函数，在这些指标中最重要的指标是飞机的自重。因为采用轻的零部件建造的自身重量最轻的飞机只会促进其它几项指标，而不会损害其中任何一项。因此选择飞机自重作为优化设计的目标函数应该是最合适的了。若一项工程设计中追求的目标是相互矛盾的，这时常常取其中最主要的指标作为目标函数，而其余的指标列为约束条件。也就是说，不指望这些次要的指标都达到最优，只要它们不致于过劣就可以了。在工程实际中，应根据不同的设计对象，不同的设计要求灵活地选择某项指标作为目标函数。以下的意见可作为选择时的参考。对于一般的机械，可按重量最轻或体积最小的要求建立目标函数;对应力集中现象尤其突出的构件，则以应力集中系数最小作为追求的目标，对于精密仪器，应按其精度最高或误差最小的要求建立目标函数。在机构设计中，当对所设计的机构的运动规律有明确的要求时，可针对其运动学参数建立目标函数;若对机构的动态特性有专门要求，则应针对其动力学参数建立目标函数;而对于要求再现运动轨迹的机构设计，则应根据机构的轨迹误差最小的要求建立目标函数。3.约束条件的确定约束条件是就工程设计本身而提出的对设计变量取值范围的限制条件。和目标函数一样，它们也是设计变量的可计算函数。如前所述，约束条件可分为性能约束和边界约束两大类。性能约束通常与设计原理有关，有时非常简单，如设计曲柄连杆机构时，按曲柄存在条件而写出的约束函数均为设计变量的线性显函数;有时却相当复杂，如对一个复杂的结构系统，要计算其中各构件的应力和位移，常采用有限元法，这时相应的约束函数为设计变量的隐函数，计算这样的约束函数往往要花费很大的计算量。3.约束条件的确定在选取约束条件时应当特别注意避免出现相互矛盾的约束。因为相互矛盾的约束必然导致可行域