第6章-约束优化方法总结课件.ppt

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

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

3、存在多个局部最优解，当选择的初始点不同，而搜索到不同的局部最优解。3）要求可行域有界的非空集。a)可行域是凸集；b)可行域是非凸集间接解法的求解思路：将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。121211,mljkjkxf xG gxH hx 新目标函数加权因子然后对新目标函数进行无约束极小化计算。间接解法是目前在机械优化设计中得到广泛应用的一种有效方法。其特点是:1)由于无约束优化方法的研究日趋成熟，已经研究出不少有效的无约束最优化方法和程序，使得间接解法有了可靠的基础。目前，这类算法的计算效率和数值计算的

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

5、用的产生随机数的数学模型3536371232,2,2rrr首先令取r=2657863，按一下步骤计算：令5rr若3rr则3rrr若则2rrr2rr1rrr1rr若则则1/qr r（0，1）之间的随机数在任意(a,b)区间内的随机数()xaq ba二、初始点的选择 随机方向法的初始点x0必须是一个可行点，既满足全部不等式约束条件。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即iiiaxb2）在区间（0，1）内产生n个伪随机数iq3）计算随机点x的各分量()iiiiixaq ba4）判别随机点x是否可行，若随机点可行，用x代替x0为初始点；若非可行点，转到步骤2）重新产生随

6、机点，只到可行为止。三、可行搜索方向的产生产生可行随机方向的方法：从k个随机方向中，选取一个较好的方向。其计算步骤为：121211.jjjnjjinirrerr jir1）在(-1,1)区间内产生伪随机数，得随机单位向量je2)取一试验步长a0，按下式计算k个随机点00jjxxa e3）检验k个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的点XL。4)比较XL 和X0两点的目标函数值，若f(XL)f(X0)，则步长0 缩小，转步骤1）重新计算，直至f(XL)f(X0)为止。如果0 缩小到很小，仍然找不到一个XL，使f(XL)f(X0)则说明X0是

7、一个局部极小点，此时可更换初始点，转步骤1）。产生可行搜索方向的条件为：00min1,2,.,LjLjLgxf xf xjkf xf x则可行搜索方向为：0Ldxx四、搜索步长的确定四、搜索步长的确定步长由加速步长法确定。第三节第三节 复合形法复合形法复合形法是求解约束优化问题的一种重要的直接解法。它的基本思路是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状没改变一次，就向最优点移动一步，直至逼近最优点。由于复合形的形状不必保

8、持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。初始复合形生成的方法：1）由设计者决定k个可形点，构成初始复合形。设计变量少时适用。2）由设计者选定一个可形点，其余的k-1个可形点用随机法产生。()iixar ba11LcjjxxL110.5LcLcxxxx3）由计算机自动生成初始复合形的所有顶点。二、复合形法的搜索方法二、复合形法的搜索方法1.反射1）计算复合形各顶点的目标函数值，并比较其大小，求出最好点XL、最坏点XH 及 次坏点XG，即:min1,2,.,:max1,2,.,:max1,2,.,jLLjHHjGGxf xf xjkxf xf

9、xjkxf xf xjk jH2）计算除去最坏点XH 外的（k-1）个顶点的中心XC 111Lcjjxxk3）从统计的观点来看，一般情况下，最坏点XH和中心点XC的连线方向为目标函数的下降方向。RCCHxxa xx4）判别反射点XR的位置 若XR 为可行点，则比较XR 和XH 两点的目标函数值，如果f(XR)=f(XH),则将缩小0.7倍，重新计算新的反射点，若仍不行，继续缩小，直至f(XR)1。内点法的特点：1初始点必须为严格内点2不适于具有等式约束的数学模型 3迭代过程中各个点均为可行设计方案 4一般收敛较慢 5初始罚因子要选择得当6罚因子为递减，递减率c有0c1。三、混合惩罚函数法1.混

10、合惩罚函数法及其算法步骤 在构造惩罚函数时，可以同时包括障碍项与惩罚项，并将惩罚因子统一用r（k）表示：21111,mlkjkjx rf xrhxgxr 由于内点法容易处理不等式约束优化设计问题，而外点法又容易处理等式约束优化设计问题，因而可将内点法与外点法结合起来，处理同时具有等式约束和不等式约束的优化设计问题。这种同时处理等式和不等式约束的惩罚函数法称为混合惩罚函数法。混合惩罚函数法与前述内点法和外点法一样，也属于序列无约束极小化(SUMT)方法中的种方法。第六节第六节 增广乘子法法增广乘子法法一一.等式约束问题的拉格朗日乘子法等式约束问题的拉格朗日乘子法qvvRDXXhXFn,.,2,1

11、,0)(),(mins.t.qXhXFXL1)()(),(1.1.建立拉氏函数建立拉氏函数2.2.在最优点处有如下在最优点处有如下n+q n+q 个方程成立个方程成立qvvniiLxL,.,2,1,.,2,1,0,0其解为其解为),(XqvvpuuRDXXhXgXFn,.,2,1,.,2,1,0)(,0)(),(mins.t.二二.含不等式约束问题的拉格朗日乘子法含不等式约束问题的拉格朗日乘子法1.1.建立拉氏函数建立拉氏函数 再用前述方法建立拉氏函数再用前述方法建立拉氏函数 对不等式约束引入松弛变量对不等式约束引入松弛变量 ,使之成为等式约束使之成为等式约束:uz0)(2uuzXgpu,.,

12、2,1)()()(),(211uupuuqzXgXhXFZXL2.2.在最优点处有如下在最优点处有如下 n+q+2p n+q+2p 个方程成立个方程成立puuuupuuuuqvvvniizzLzXgLXhLxL,.,2,1,.,2,12,.,2,1,.,2,1)02(,0)0)(,0)0)(,0,0其解为其解为),(ZX)()()(),(211uupuuqzXgXhXFZXL三三.等式约束的增广乘子法等式约束的增广乘子法 采用拉格朗日乘子法时求解有难度采用拉格朗日乘子法时求解有难度,而罚函数法当迭而罚函数法当迭代点接近边界时函数常有病态代点接近边界时函数常有病态,此法的思路是把两者结此法的思路

13、是把两者结合起来合起来.其增广拉格朗日函数为其增广拉格朗日函数为:22121)()()()(),(),(uupuqkkzXgXhrZXLZrXA特点特点:1.初始点可为非可行点初始点可为非可行点;,2.因增加了可调参数因增加了可调参数 ,其收敛速度和稳定性都其收敛速度和稳定性都优于罚函数法优于罚函数法.第七节第七节 非线性规划问题的线性化解法非线性规划问题的线性化解法线性逼近法线性逼近法 线性规划问题是数学规划中提出较早的一类问题，它的求解方法在理论和算法上也较成熟，在实际工作中有比较广泛的应用。因此，自然就会想到，对一些非线性规划问题，可否把非线性函数线性化，再用线性规划方法求解?回答自然是

14、肯定的。这类方法如序列线性规划法、割平面法、小步梯度法等。第八节第八节 广义简约梯度法广义简约梯度法思路：利用约束条件消去非独立变量，使问题简化，再沿简化后的目思路：利用约束条件消去非独立变量，使问题简化，再沿简化后的目标函数的负梯度方向搜索标函数的负梯度方向搜索.一一 简约梯度法简约梯度法1.1.问题问题0)(minXbAXXF s.t.nRDX)1(nmRbm2.2.简约梯度简约梯度1）将问题降维将问题降维基向量（状态）基向量（状态）021 TBmBBBxxxX式中式中TNBXXX,将将X X分成两部分分成两部分：0)(21 TmnNNNNxxxX非基向量非基向量（决策决策)对应的系数矩阵

15、也分成两部分对应的系数矩阵也分成两部分CBA,式中式中，B B为对应于为对应于X XB B的的m m 阶方阵阶方阵，且必须为满秩矩阵且必须为满秩矩阵；C C为为对应于对应于X XN N的的 阶矩阵阶矩阵；)(mnm于是于是，NBNBCXBbBXbCXBX11（1 1）故故)(),(),()(NNNBNBXXXXFXXFXF87654321321xxx87635421321xxx2 2）求简约梯度）求简约梯度)()()()()()()(1NBTNBTNBNNXFXFCBXFXFXXXXG（2 2）式中式中,TmnNNBmBTNBxFxFxFxFXFXFXF.)(),()()(113 3.迭代计算

16、迭代计算1 1）迭代公式）迭代公式)()()1(kNkNkNSXX)()()(kNkNXGX（3 3）)(),(),()(NNNBNBXXXXFXXFXFNBCXBbBX11*(1)在迭代中需保证各分量值大于或等于零在迭代中需保证各分量值大于或等于零;(2)当当 且且 时时,因因 ,必有必有 ,不可行不可行.0)(kNlx0)()(kNlXg00)1(kNlx写成分量的形式：写成分量的形式：)1(kNix)()()(kNikNiXgx)(,.,2,1,0mni（4 4）迭代方向应作修正迭代方向应作修正：)(0)()(kNikNiXgs0)(kNlx0)()(kNlXg(当当 ,时时)(在一般情

17、况下在一般情况下)（5 5）2 2）步长因子的确定）步长因子的确定)1(kix)()(kikisxni,.,2,1(1)若各分量值若各分量值 大于零大于零,则只要则只要 均能保证变量均能保证变量 非负非负,此时可取最优步长此时可取最优步长0)(kis.(2)若若 ,由于必须使由于必须使0)(kis)1(kix0)()(kikisx（6 6）故故)()(kikisx,于是有于是有min0)()(max)(时当kiskikisx.0,max之间进行只能在故作一维搜索时3）确定确定 的方法的方法)1(kBX)(11)(kNkBCXBbBX由由(1)(1)有有*通过通过(3)(3)和和(7)(7)可完

18、成一次完整的迭代可完成一次完整的迭代.)1(11)1(kNkBCXBbBX)()()(11kNkNSXCBbB)()()(1)(kBkBkNkBSXSCBX（7 7）由由(3)(3)()(1)(kNkBSCBS)()()1(kNkNkNSXX)()()(kNkNXGX(允许部分变量的上允许部分变量的上下界为下界为 )二二 广义简约梯度法简介广义简约梯度法简介1 1.问题问题iiivbxXhXFa0)()(mins.t.s.t.nRDXmv,.,2,1ni,.,2,1(可引入松弛变量将不可引入松弛变量将不等式约束变为等式约束等式约束变为等式约束)2 2.解法特点解法特点1)1)和和 之间的关系难以用简单的式子表达之间的关系难以用简单的式子表达,一般采用一般采用牛顿迭代法解非线性方程组获得牛顿迭代法解非线性方程组获得;BXNX2)2)求简约梯度用到的求简约梯度用到的 可用复合函数求导的方法求得可用复合函数求导的方法求得.)(NBXX