约束问题的最优化方法课件

第五章约束问题的最优化方法

§5.1引言

§5.2内点惩罚函数法

§5.3外点惩罚函数法

§5.4混合惩罚函数法

§5.5随机方向搜索法

§5.6复合形法

§5.7可行方向法

§5.8约束优化设计方法小结§5.1引言在机械设计问题中，大多数的优化问题都属于有约束的问题，其数学模型的一般形式为：求解这类问题的方法通常称为约束优化计算方法。根据求解方式的不同可以分为间接解法和直接解法两大类。

间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。

直接解法是在满足不等式约束gu(x)≤0(u＝1，2，…，m)的可行设计区域内直接搜索问题的约束最优解x*和f(x*)。§5.1引言

直接解法：随机方向搜索法、复合形法、可行方向法间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法一.有约束问题解法分类：二.直接解法的基本思想：

合理选择初始点，确定搜索方向，以迭代公式x(k+1)=x(k)+α(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。收敛条件：边界点的收敛条件应该符合K-T条件；内点的收敛条件为：§5.1引言

目的：将有约束优化问题转化为无约束优化问题来解决。

方法：以原目标函数和加权的约束函数共同构成一个新的目标函数Φ(x,r1,r2)，成为无约束优化问题。通过不断调整加权因子，产生一系列Φ函数的极小点序列x(k)*(r1(k),r2(k))k=0,1,2…

，逐渐收敛到原目标函数的约束最优解。

其中：新目标函数：三.间接解法的基本思想：有解的条件：①f(x)和g(x)都连续可微；②存在一个有界的可行域；③可行域为非空集；④迭代要有目标函数的下降性和设计变量的可行性。§5.1引言

新目标函数：其中：

加权因子，即惩罚因子：r1(k)，r2(k)Φ函数的极小点序列x(k)*(r1(k),r2

(k))k=0,1,2…

其收敛必须满足：无约束优化问题：

为惩罚项

§5.2内点惩罚函数法（障碍函数法）一.基本思想：

内点法将新目标函数Φ(x,r)构筑在可行域D内，随着惩罚因子r(k)的不断递减，生成一系列新目标函数Φ(xk,r(k))，在可行域内逐步迭代，产生的极值点xk*(r(k))序列从可行域内部趋向原目标函数的约束最优点x*

。例：求下述约束优化问题的最优点。min.f(x)=xx∈R1s.t

g(x)=1-x≤0X1*X2*X*r=1r(k)10.10.010.001…0X*(r(k))21.3161.11.032…1Ф(x*(r(k)),r(k))31.6321.21.063…1对新目标函数求导，并令其为零，得极值点表达式：新目标函数的值为：极值点随r(k)的递减将沿一直线Ф(x*(r(k)),r(k))=2x*(r(k))-1从域内向x*收敛§5.2内点惩罚函数法三.步骤：选取合适的初始点x(0)

，以及r(0)、c、计算精度ε1、ε2

，令k=0；2.构造惩罚（新目标）函数；3.调用无约束优化方法，求新目标函数的最优解xk*和Φ(xk,r(k))；4.判断是否收敛：运用终止准则①

②若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令并转入第3步，继续计算。§5.2内点惩罚函数法四.几个参数的选择：惩罚因子初始值r(0)

的选择：

过大、过小均不好，建议考虑选择：2.

降低系数c的选择：c的典型值为0.1～0.002。建议先试算。3.

初始点x(0)

的选择：要求：

①在可行域内；②不要离约束边界太近。方法：

①人工估算，需要校核可行性；②计算机随机产生，也需校核可行性。§5.2内点惩罚函数法五.方法评价：

用于目标函数比较复杂，或在可行域外无定义的场合下：由于优化过程是在可行域内逐步改进设计方案，故在解决工程问题时，只要满足工程要求，即使未达最优解，接近的过程解也是可行的；初始点和序列极值点均需严格满足所有约束条件；不能解决等式约束问题。§5.2内点惩罚函数法六.举例：盖板问题bhtstf

设计一个箱形截面的盖板。已知：长度l0=600cm，宽度b=60cm，侧板厚度ts=0.5cm，翼板厚度为tf(cm)，高度为h(cm)，承受最大的单位载荷q=0.01Mpa。

要求：在满足强度、刚度和稳定性等条件下，设计一个最轻结构。设计分析：（最大剪应力、最大弯曲应力、屈曲临界稳定应力、最大挠度、截面的惯性矩等（略）数学模型：单位长度的质量§5.2内点惩罚函数法优化方法：

选用内点惩罚法，惩罚函数形式为：

调用Powell法求序列无约束优化极值，以逐渐逼近原问题的极值点。§5.2内点惩罚函数法4.求解过程分析：§5.3外点惩罚函数法(衰减函数法）一.基本思想：

外点法将新目标函数Φ(x,r)构筑在可行域D外，随着惩罚因子r(k)的不断递增，生成一系列新目标函数Φ(xk,r(k))，在可行域外逐步迭代，产生的极值点xk*(r(k))序列从可行域外部趋向原目标函数的约束最优点x*。例：求下述约束优化问题的最优点。

min.f(x)=xx∈R1s.tg(x)=1-x≤0新目标函数：4§5.3外点惩罚函数法说明：§5.3外点惩罚函数法三.几个参数的选择：r(0)

的选择:r(0)

过大，会使惩罚函数的等值线变形或偏心，求极值困难。r(0)

过小，迭代次数太多。x(0)

的选择：基本上可以在可行域内外，任意选择。递增系数a的选择：

通常选择5～10，可根据具体题目，进行试算调整。§5.3外点惩罚函数法四.步骤：2.构造惩罚（新目标）函数，调用无约束优化方法，求新目标函数的最优解xk*和Φ(xk,r(k))；3.4.判断是否收敛：运用终止准则①②若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令并转入第2步，继续计算。1.选择合适的初始点x(0)，并选择r(0),a,ε1,ε2,δ0，令k=0；§5.3外点惩罚函数法算法框图§5.4混合惩罚函数法一.基本思想：

采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。二.惩罚函数的形式：一般既包括障碍项，也包括衰减项。§5.4混合惩罚函数法其中：§5.5随机方向搜索法一.基本思想：

随机产生初始点，随机产生搜索方向S(k)

，进行搜索。但要确保：①新迭代点在可行域中；②目标函数值的下降性。二.随机数的产生：1.伪随机数：

用数学模型，从计算机（的随机数发生器）中产生的随机数。随机数的特性

有较好的概率统计特性①抽样的随机性；②分布的均匀性；③前后数之间的独立性；④周期性长。§5.5随机方向搜索法四.随机产生搜索方向：x(0)x(m)x(1)x(2)x(j)x(l)H(0)§5.5随机方向搜索法五.步骤：X(k+1)●均是，转判2§5.5随机方向搜索法算法框图§5.5随机方向搜索法六.方法评价：优点：

对目标函数无性态要求；收敛快（当m足够大时）；不受维数影响，维数愈高，愈体现优点。缺点：

对于严重非线性函数，只能得近似解；当m不够大时，解的近似程度大；对于非凸函数，有可能收敛于局部解。例5-4如图所示为平面铰接四杆机构。各杆的长度分别为l1、l2、l3、l4主动杆1的输入角为φ，相应于摇杆3在右极位(杆1与杆2伸直位置)时，主动杆1的初始位置角为φ0；从动杆的输出角为ψ，初始位置角为ψ0

。试确定四杆机构的运动参数，使输出角

°+=900jjm

的函数关系，当曲柄从位置转到时，最佳再现下面给定的函数关系已知l1=1，l4=5，其传动角允许在450≤γ≤1350范围内变化。解:（1）数学模型的建立在这个设计问题中，已经给定了两根杆长：l1＝1，l4＝5，且φ0和ψ0

不是独立的参数，因为所以只剩下两个独立参数l2和l3。因此设计变量取复演预期函数的机构设计问题．可以按期望机构的输出函数与给定函数的均方根误差达到最小来建立目标函数，即或者由于ψ和ψE均为输入角φ的连续函数，为了进行数值计算，可将区间划分为30等分，将上式改写为梯形近似积分计算公式式中ψj——当时机构的实际输出角；

ψEj——复演预期函数当时的函数值，也是欲求机构的理论输出角。下标j为j＝0，1，2，…，30。Ψj值可按下式计算（参见右图）目标函数是个凸函数，其等值线见右图由于要求四杆机构的杆1能做整周转动，且机构的最小传动角γmin≥450最大传动角γ≤1350。所以根据四杆机构的曲柄存在条件，得不等式约束条件为所以得不等式约束条件为：（2）优化计算结果上述设计问题是属于二维的非线性规划问题，有七个不等式约束条件，其中主要的是。现在采用约束随机方向搜索法来求解。§5.6复合形法一.单纯形法：定义：基本思想：

以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，这样不断地迭代，单纯形逐渐逼近最优点。以二维空间中的映射法为例：X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)在n维空间中，由n+1个点组成的图形称单纯形。X*§5.6复合形法二.复合形法：定义：

在n维空间中，由k≥n+1个点组成的多面体称为复合形。基本思想：

以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：

单纯形是无约束优化方法，而复合形可用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。§5.6复合形法三.迭代方法：1.映射法：

例：二维空间中，k=4，复合形是四边形x(1)x(2)x(3)x(4)，计算得：f(x(1))<f(x(2))<f(x(3))<f(x(4)),确定最坏点x(H)=x(4)，次坏点x(G)=x(3)

，最好点x(L)=x(1)

。x(S)为除x(H)以外，各点的几何中心。搜索方向：沿x(H)→

x(S)的方向。步长因子（映射系数）α：α>1，建议先取1.3。映射迭代公式：x(R)=x(S)+α(x(S)

—x(H))

若求得的x(R)在可行域内，且f(x(R))<f(x(H))，则以x(R)代替x(H)组成新复合形，再进行下一轮迭代。●

X(S)X(R)§5.6复合形法2.

变形法一

——

扩张法：变形法二

——

收缩法：

§5.6复合形法四.初始复合形的形成：人工选择初始复合形：随机产生初始复合形：若可行域是非凸集，可能失败，需减小上、下界再进行。§5.6复合形法五.步骤：§5.6复合形法五.步骤：§5.6复合形法§5.6复合形法六.算法框图：§5.6复合形法七.方法评价：

计算简单，不必求导，占内存小；随着维数的增加，效率大大下降；不能解含等式约束的问题；建议：

①初始α取1.3。②n+1≤k≤2n，当n≤5时，k取值接近2n；当n>5时，k的取值可小些。例5-5如图5-21所示为转向梯形机构的计算简图。设M/L=0.5(相当于212型汽车,M=148cm,L=296cm)，当车辆转弯时,为了保证所有车轮都处于纯滚动，要求两转向轮的外角和内角符合（1）函数关系。若假定为已知函数式（1）的自变角,则其因变角为

(2)现在要求确定转向梯形机构的运动学尺寸，使其外角和内角的函数关系，最佳逼近函数关系式(2)。§5.6复合形法§5.6复合形法

解：(1)数学模型的建立设梯形机构转向臀1、3的长度为l1=l3，梯形初始位置角为,机架长度M＝148cm，连杆2长度l2=148-2l1cos,显然l2不是一个独立的参数，而是l1和的函数。于是，梯形机构优化设计只有两个设计变量，即

设机构的输入角(由机构M逆时针计算)为，输出角根据机构运动分析其输出角为（3）（4）§5.6复合形法

式中（5）由此求得因变角为（6）

当α

角在[-300

，300]范围内变化时，若将它分成20等分，根据均方根误差最小来建立目标函数．并用梯形近似公式计算，即得（7）§5.6复合形法式中

——相应于时按式(6)计算的实际内角值；

——相应于时按式(2)计算的预期内角值。在汽车、拖拉机一类的机动车辆中，对转向机构的设计，要求其转向臀不宜过短，通常取，但考虑到空间的布置，转向臂也不能过长，即。同时，对于后置式转向机构，其梯形留延长线的交点，应离前轴0.6L以外。因此，梯形机构的初始角应满足（8）由此，可写出梯形机构设计的约束条件为§5.6复合形法综上所述，梯形转向机构的优化设计问题，是二维4个不等式约束非线性规划问题。(2)求解结果和分析按上述数学模型．可以在设计空间(x1，x2)内画出可行域，如图5-22所示，是一个凸集。取设计变量最忧解的估计上限和下限为：

a1=14.8cm,b1=59.1cma2=1.16rad,b2=1.36rad目标函数值的收敛精度=10-6

，收缩最小正数。顶点数k=2n＝4，结定一个初始点目标函数值f（x）=34.6404x10-4。其余顶点随机产生，即§5.6复合形法

第一次迭代复合形的最好点的坐标为，经过40次迭代，取得最优设计方案在图5-32中给出了迭代次数和日标函数值下降的关系。可见，只要放低收敛的精度．就可以减少迭代次数和计算时间，当然要以取得适用的方案为前提。§5.6复合形法在图5-24中列出了机构最优方案的实际内角和期望内角的函数曲线关系及其误差曲线。§5.7可行方向法一.基本思想：

在第k+1次迭代时，从x(k)

点出发，寻找一个可行的搜索方向和合适的步长因子，从而得到一个可行、目标函数值下降的新点x(k+1)

，再以此点出发，寻找新点，直至满足收敛条件，得到最优点x*。α(k)的选择原则：

使新点x(k+1)

在可行域内。S