《约束优化方法》PPT课件.ppt

《《约束优化方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《约束优化方法》PPT课件.ppt（99页珍藏版）》请在三一办公上搜索。

1、第六章 约束优化方法,根据求解方式的不同，可分为直接解法和间接解法两类。,机械优化设计的问题，大多属于约束优化设计问题，其数学模型为：,直接解法是在满足不等式约束的可行设计区域内直接求出问题的约束最优解。,属于这类方法的有：随机方向法、复合形法、可行方向法等。,间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。,由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。,间接解法中具有代表性的是惩罚函数法、增广乘子法。,直接解法的基本思想：,在由m个不等式约束条件gu(x)0所确定的可行域内，选择一个初

2、始点x(0)，然后确定一个可行搜索方向S，且以适当的步长沿S方向进行搜索，取得一个目标函数有所改善的可行的新点x(1)，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算：,x(k+1)x(k)+(k)S(k)(k=0,1,2,)逐步趋向最优解，直到满足终止准则才停止迭代。,直接解法的原理简单，方法实用，其特点是：,1）由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好的设计点。,2）若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部最优解，当选择的初始点不同，而搜索到不同的局部最优解。,3）要求可行域有界的

3、非空集。,a)可行域是凸集；b)可行域是非凸集,间接解法的求解思路：,将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。,新目标函数,加权因子,然后对新目标函数进行无约束极小化计算。,间接解法是目前在机械优化设计中得到广泛应用的一种有效方法。其特点是:,1)由于无约束优化方法的研究日趋成熟，已经研究出不少有效的无约束最优化方法和程序，使得间接解法有了可靠的基础。目前，这类算法的计算效率和数值计算的稳定性也都有较大的提高。,2)可以有效地处理具有等式约束的约束优化问题。,3)间接解法存在的主要问题是，选取加权因子较为困

4、难。加权因子选取不当，不但影响收敛速度和计算精度，甚至会导致计算失败。,第二节随机方向法,随机方向法的基本思路：,在可行域内选择一个初始点，利用随机数的概率特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为搜索方向d。,从初始点x0出发，沿d 方向以一定步长进行搜索，得到新点X，新点x应满足约束条件且f(x)f(x0)，至此完成一次迭代。,基本思路如图所示。,随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。,一、随机数的产生,下面介绍一种常用的产生随机数的数学模型,骤计算：,令,在任意(a,b)区间内的随机数,二、初始点的选择,随机方向法的

5、初始点x0必须是一个可行点，既满足全部不等式约束条件。,初始点可以通过随机选择的方法产生。,1）输入设计变量的下限值和上限值，即,2）在区间（0，1）内产生n个伪随机数,3）计算随机点x的各分量,4）判别随机点x是否可行，若随机点可行，用x代替x0为初始点；若非可行点，转到步骤2）重新产生随机点，只到可行为止。,三、可行搜索方向的产生,产生可行随机方向的方法：从k个随机方向中，选取一个较好的方向。其计算步骤为：,2)取一试验步长a0，按下式计算k个随机点,3）检验k个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的点XL。,4)比较XL 和X0两点

6、的目标函数值，若f(XL)f(X0)，则步长0 缩小，转步骤1）重新计算，直至f(XL)f(X0)为止。如果0 缩小到很小，仍然找不到一个XL，使f(XL)f(X0)则说明X0是一个局部极小点，此时可更换初始点，转步骤1）。,产生可行搜索方向的条件为：,则可行搜索方向为：,四、搜索步长的确定,步长由加速步长法确定。,第三节 复合形法,复合形法是求解约束优化问题的一种重要的直接解法。,它的基本思路是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合

7、形，复合形的形状没改变一次，就向最优点移动一步，直至逼近最优点。,由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。,初始复合形生成的方法：,1）由设计者决定k个可形点，构成初始复合形。设计变量少时适用。,2）由设计者选定一个可形点，其余的k-1个可形点用随机法产生。,3）由计算机自动生成初始复合形的所有顶点。,二、复合形法的搜索方法,1.反射,1）计算复合形各顶点的目标函数值，并比较其大小，求出最好点XL、最坏点XH 及 次坏点XG，即,2）计算除去最坏点XH 外的（k-1）个顶点的中心XC,3）从统计的观点来看，一般情况下，

8、最坏点XH和中心点XC的连线方向为目标函数的下降方向。,4）判别反射点XR的位置,若XR 为可行点，则比较XR 和XH 两点的目标函数值，如果f(XR)=f(XH),则将缩小0.7倍，重新计算新的反射点，若仍不行，继续缩小，直至f(XR)f(XH)为止。,若为非可行点，则将缩小0.7倍，直至可行为止。然后再重复可行点的步骤。,2.扩张,3.收缩,4.压缩,第四节 可行方向法,约束优化问题的直接解法中，可行方向法是最大的一类，它也是求解大型约束优化问题的主要方法之一。这种方法的基本原理是在可行域内选择一个初始点X0，当确定了一个可行方向d和适当的步长后，按下式,进行迭代计算。在不断调整可行方向的

9、过程中，使迭代点逐步逼近约束最优点。,可行方向法的搜索策略,可行方向法的搜索策略,产生可行方向的条件,产生可行方向的条件,可行方向的产生方法,满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向，其方法主要有优选方向法和梯度投影法两种。,可行方向的产生方法,步长的确定,步长的确定,步长的确定,步长的确定,收敛条件,可行方向法的计算步骤,第五节 惩罚函数法,惩罚函数法是一种很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式和不等式约束函数经加权后，和原目标函数结合为新的目标函数惩罚函数。,将约束优化问题转换为无约束优化问题。求解无约束优

10、化问题的极小值，从而得到原约束优化问题的最优解。,加权转化项,惩罚函数法是按一定的法则改变加权因子的值，构成一系列的无约束优化问题，求一系列无约束最优解，并不断地逼近原约束优化问题的最优解。因此又称序列无约束极小化方法。常称SUMT方法。,根据它们在惩罚函数中的作用，分别称障碍项和惩罚项。,障碍项的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可形域。,惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时，在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。,按照惩罚函数在优化过程中迭代点是否可行，分为：内点法、外点法及混合法。,一、内点惩罚函数法,内点法将新目标函数定义于可行域内

11、，这样它的初始点及后面的迭代点序列必定在可行域内。,采用内点法只能求解具有不等式约束的优化问题。,转化后的惩罚函数形式为：,障碍项,障碍项的作用是阻止迭代点越出可行域。,例6-5 用内点法求问题,约束最优解。,用内点法求解，首先构造内点惩罚函数：,用解析法对函数求极小值。,求解得,不满足约束条件，舍去。无约束极值点为：,下面介绍内点法中的初始点、惩罚因子初值及其缩减系数的选取和收敛条件的确定。,1.初始点的选取,初始点应选离约束边界较远的可行点。程序设计时，一般，考虑具有人工输入、和计算机自动生成可行初始点的两种功能。,2.惩罚因子的初值的选取,惩罚因子的初值选取应适当，否则会影响迭代计算的正

12、常进行。太大会影响迭代次数，太小会使惩罚函数的形态变坏，难以收敛到极值点。,1）取r0=1，根据试算的结果，再决定增加或减少r0 值。,2）按经验公式,计算r0 值。这样选取的r0，可以是惩罚函数中的障碍项和原目标函数的值大致相等，不会因障碍项的值太大则其支配作用，也不会因障碍项的值太小而被忽略掉。,3.惩罚因子的缩减系数c的选取,在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为：,惩罚因子的缩减系数通常的取值范围：之间。,4.收敛条件,内点法是将惩罚因数定义于可行域内，而外点法与内点法不同，是将惩罚项函数定义于可行区域的外部。序列迭代点从可行域外部逐渐

13、逼近约束边界上的最优点。,二、外点惩罚函数法,外点法可以用来求解含不等式和等式约束的优化问题。,对于约束优化问题,惩罚因子，它是由小到大。,惩罚项,由惩罚项可知，当迭代点不可行时，惩罚项的值大于零。,当迭代点离约束边界越远时，惩罚项愈大，这可看成是对迭代点不满足约束条件的一种惩罚。,转化后的外点惩罚函数的形式为：,例6-6 用外点法求问题,约束最优解。,首先构造外点惩罚函数：,用解析法求解,求解得,外点法惩罚银子按下式递增,递增系数，通常取c=5-10。,与内点法相反计算r0 值。选取的r0 太大则会使惩罚函数等值线偏心或变形，难以取得极小值。但r0太小，势必增加迭代次数。,经验计算一般取r0

14、=1，c=10常常可以取得满意的效果。,也可以通过经验公式获得r0 值,外点法的特点：1初始点可以任选，但应使各函数有定义 2对等式约束和不等式约束均可适用 3仅最优解为可行设计方案 4一般收敛较快 5初始罚因子要选择得当 6惩罚因子为递增，递增率c有c1。,内点法的特点：1初始点必须为严格内点2不适于具有等式约束的数学模型 3迭代过程中各个点均为可行设计方案 4一般收敛较慢 5初始罚因子要选择得当6罚因子为递减，递减率c有0c1。,三、混合惩罚函数法,1.混合惩罚函数法及其算法步骤,在构造惩罚函数时，可以同时包括障碍项与惩罚项，并将惩罚因子统一用r（k）表示：,由于内点法容易处理不等式约束优

15、化设计问题，而外点法又容易处理等式约束优化设计问题，因而可将内点法与外点法结合起来，处理同时具有等式约束和不等式约束的优化设计问题。,这种同时处理等式和不等式约束的惩罚函数法称为混合惩罚函数法。混合惩罚函数法与前述内点法和外点法一样，也属于序列无约束极小化(SUMT)方法中的种方法。,第六节 增广乘子法法,一.等式约束问题的拉格朗日乘子法,s.t.,1.建立拉氏函数,2.在最优点处有如下n+q 个方程成立,其解为,s.t.,二.含不等式约束问题的拉格朗日乘子法,1.建立拉氏函数,再用前述方法建立拉氏函数,对不等式约束引入松弛变量,使之成为等式约束:,2.在最优点处有如下 n+q+2p 个方程成

16、立,其解为,三.等式约束的增广乘子法,采用拉格朗日乘子法时求解有难度,而罚函数法当迭代点接近边界时函数常有病态,此法的思路是把两者结合起来.其增广拉格朗日函数为:,特点:,1.初始点可为非可行点;,2.因增加了可调参数,其收敛速度和稳定性都优于罚函数法.,第七节 非线性规划问题的线性化解法线性逼近法,线性规划问题是数学规划中提出较早的一类问题，它的求解方法在理论和算法上也较成熟，在实际工作中有比较广泛的应用。因此，自然就会想到，对一些非线性规划问题，可否把非线性函数线性化，再用线性规划方法求解?回答自然是肯定的。这类方法如序列线性规划法、割平面法、小步梯度法等。,第八节 广义简约梯度法,思路：

17、利用约束条件消去非独立变量，使问题简化，再沿简化后的目标函数的负梯度方向搜索.,一 简约梯度法,1.问题,s.t.,2.简约梯度,1）将问题降维,基向量（状态）,式中,将X分成两部分：,非基向量（决策),对应的系数矩阵也分成两部分,式中，B为对应于XB的m 阶方阵，且必须为满秩矩阵；C为对应于XN的 阶矩阵；,故,2）求简约梯度,（2）,式中,3.迭代计算,1）迭代公式,（3）,*(1)在迭代中需保证各分量值大于或等于零;,(2)当 且 时,因,必有,不可行.,写成分量的形式：,（4）,迭代方向应作修正：,(当,时),(在一般情况下),（5）,2）步长因子的确定,(1)若各分量值 大于零,则只要 均能保证变量 非负,此时可取最优步长,(2)若,由于必须使,（6）,故,于是有,3）确定 的方法,由(1)有,*通过(3)和(7)可完成一次完整的迭代.,（7）,(允许部分变量的上下界为),二 广义简约梯度法简介,(可引入松弛变量将不等式约束变为等式约束),2.解法特点,1)和 之间的关系难以用简单的式子表达,一般采用牛顿迭代法解非线性方程组获得;,2)求简约梯度用到的 可用复合函数求导的方法求得.,