现代设计方法ppt课件第5节

《现代设计方法ppt课件第5节》由会员分享，可在线阅读，更多相关《现代设计方法ppt课件第5节（71页珍藏版）》请在装配图网上搜索。

1、现代设计方法现代设计方法第三章第三章 优化设计优化设计Optimization Design第三章 优化设计现代设计方法现代设计方法本章主要内容本章主要内容 优化设计概述优化设计概述 优化问题的数学分析基础优化问题的数学分析基础 一维探索优化方法一维探索优化方法 无约束多维问题的优化方法无约束多维问题的优化方法 约束问题的优化方法约束问题的优化方法 多目标函数的优化方法多目标函数的优化方法 LINGO在优化设计中的应用在优化设计中的应用本章主要内容现代设计方法现代设计方法3.5 约束问题的优化方法约束问题的优化方法约束优化方法是用来求解如下非线性约束优化问题约束优化方法是用来求解如下非线性约束

2、优化问题的数值迭代算法。的数值迭代算法。根据处理约束条件的不同方式，求解这类问题的方根据处理约束条件的不同方式，求解这类问题的方法分为法分为直接法和间接法直接法和间接法。3.5 约束问题的优化方法约束优化方法是用来求解如下非线性现代设计方法现代设计方法直直接接法法：在在迭迭代代过过程程中中逐逐点点考考察察约约束束的的可可行行域域，并并使使迭迭代代点点始始终终局局限限于于可可行行域域之之内内的的算算法法称称为为直直接接法法。常常用用的的直直接接法法有有：随随机机试试验验、随随机机方方向向搜搜索索法法、复复合合形形法法、可可行行方方向向法法、约约束束坐坐标轮换法、网格法等；标轮换法、网格法等；间间

3、接接法法：把把约约束束条条件件引引入入目目标标函函数数，使使约约束束优优化化问问题题转转化化为为相相对对简简单单的的二二次次规规划划问问题题或或线线性性规规划划问问题题求求解解的的算算法法称称为为间间接接法法，常常用用的的间间接接法法有有消消元元法法、拉拉格格朗朗日日乘乘子子法法、惩惩罚罚函函数数法法和和序列线性规划法等。序列线性规划法等。直接法：在迭代过程中逐点考察约束的可行域，并使迭代点始终局限现代设计方法现代设计方法一、一、约束优化问题的直接法约束优化问题的直接法在可行域内按照一定的准则，在可行域内按照一定的准则，直接探索直接探索出问题的最出问题的最优点，而无须将约束问题转换成无约束问题

4、去求优优点，而无须将约束问题转换成无约束问题去求优的方法，称为约束优化问题的直接法。约束条件常的方法，称为约束优化问题的直接法。约束条件常常使得常使得可行域非凸集可行域非凸集出现出现众多的局部极值点众多的局部极值点，不同不同的初始点的初始点往往会导致探索点往往会导致探索点逼近不同的局部极值点逼近不同的局部极值点，因此需要多次变更初始点进行多路探索。因此需要多次变更初始点进行多路探索。一、约束优化问题的直接法现代设计方法现代设计方法1.随机试验法（统计模拟试验法）随机试验法（统计模拟试验法）基本思想：基本思想：利用计算机产生的利用计算机产生的伪随机数伪随机数，从设计方，从设计方案集合中案集合中分

5、批抽样分批抽样。每批抽样均包含。每批抽样均包含若干方案若干方案，对，对每个方案都做约束检验，不满足则重抽，满足则按每个方案都做约束检验，不满足则重抽，满足则按照它们的照它们的函数值的大小进行排列函数值的大小进行排列，取出前几个或者，取出前几个或者几十个几十个相差不是很大的函数值相差不是很大的函数值，然后再做下批试验。，然后再做下批试验。当每批抽样试验的当每批抽样试验的前几个函数值不再明显变动前几个函数值不再明显变动时，时，则可认为它已经按照概率则可认为它已经按照概率收敛收敛于某一于某一最优方案最优方案。1.随机试验法（统计模拟试验法）现代设计方法现代设计方法迭代算法迭代算法:（8个步骤）个步骤

6、）1）选定每个设计变量的选定每个设计变量的上下限上下限ai,bi，(i=1,2,n)，其中，其中，n 为方案中的设计变量数。为方案中的设计变量数。2）产生）产生0,1区间区间内服从内服从均匀分布均匀分布的一个的一个伪随机数列伪随机数列ri。3）形成随机试验点形成随机试验点 xi(k)=ai+ri(k)(bi-ai)(xi即为设计变即为设计变量量)；i=1,2,n；k=1,2,N；其中，其中，N 为每批试验为每批试验中的中的方案数方案数(设计变量可能取到的值的个数设计变量可能取到的值的个数)。迭代算法:（8个步骤）现代设计方法现代设计方法4）约束条件的检验，）约束条件的检验，gu(x1(k),x

7、2(k),xn(k)0(u=1，2，m)。5）计算试验点的函数值，并循环转向）计算试验点的函数值，并循环转向 2）进行）进行 N 次次。6）将）将 N 个个试验点的函数值按大小排序，找出试验点的函数值按大小排序，找出最优最优点点及其函数值，即及其函数值，即 f(X(L)=minf(X(k)(k=1,2,N)实验点实验点:X(k)=x1(k),x2(k),xn(k)4）约束条件的检验，gu(x1(k),x2(k),现代设计方法现代设计方法7）确定前）确定前 p 个最好的试验点的均值个最好的试验点的均值 Xi 和均方根差和均方根差 i，当当 Xi 基本不变动基本不变动或者或者 i 时，得到近似最优

8、点，否则时，得到近似最优点，否则转向下一步。转向下一步。8）构造新的试验区间）构造新的试验区间Xi-3 i,Xi+3 i，并转向，并转向 3）。）。7）确定前 p 个最好的试验点的均值 Xi 和均方根差 现代设计方法现代设计方法2.随机方向探索法随机方向探索法当采用当采用随机方向随机方向为探索方向时，称为随机方向探索为探索方向时，称为随机方向探索法，该方法一般包括法，该方法一般包括初始点初始点、探索方向探索方向和和探索步长探索步长随机选择三部分。随机选择三部分。2.随机方向探索法现代设计方法现代设计方法约束随机方向探索法的基本原理约束随机方向探索法的基本原理约束随机方向探索法的基本原理现代设计

9、方法现代设计方法迭代步骤迭代步骤：（4步）步）1）在可行域内选取一个初始点在可行域内选取一个初始点 X(0)。并检验约束条。并检验约束条件是否满足，如满足则转下一步，否则重新选取件是否满足，如满足则转下一步，否则重新选取 X(0)。2）产生产生N个个随机单位向量随机单位向量e(j)(j=1,2,N),在以在以X(0)为中心，以为中心，以H0为半径的超球面上产生为半径的超球面上产生 N 个随机点个随机点 X(j)=X(0)+H0e(j)，并判断出，并判断出函数值最小的点函数值最小的点X(L)。如果如果 f(X(L)f(X(0)，则继续则继续沿沿 f(X(L)-f(X(0)方向方向以适当步长以适当

10、步长(试探试探)向前跨步向前跨步，得到新点，得到新点 X(1)。迭代步骤：（4步）现代设计方法现代设计方法3）如果如果 f(X(1)f(X(L)，则以，则以 X(1)为新的初始点，转为新的初始点，转向向2）重复前面的过程，否则，以较小的试验步长向）重复前面的过程，否则，以较小的试验步长向前探索，直到前探索，直到目标函数值不再下降目标函数值不再下降而又而又符合约束条件符合约束条件为止。然后将探索得到的新点作为下一次的初始点，为止。然后将探索得到的新点作为下一次的初始点，重复重复2）和）和3）。）。4）当同一次迭代的初始点和末点的函数值满足收敛当同一次迭代的初始点和末点的函数值满足收敛准则时，则停

11、止迭代，并取准则时，则停止迭代，并取 X*=X(k);f(X*)=f(X(k)3）如果 f(X(1)f(X(L)，则以 X(1)为现代设计方法现代设计方法3.3.可行方向法可行方向法可行方向法是用可行方向法是用梯度法梯度法去求解约束非线性最优化问去求解约束非线性最优化问题的一种有代表性的题的一种有代表性的解法解法，是求解大型约束优化问，是求解大型约束优化问题的主要方法之一。其收敛速度快，效果好，但程题的主要方法之一。其收敛速度快，效果好，但程序比较复杂，计算困难且工作量大。序比较复杂，计算困难且工作量大。数学基础：数学基础：梯度法、方向导数、梯度法、方向导数、kt条件条件适用条件：适用条件：目

12、标函数和约束函数均为目标函数和约束函数均为n维一阶连续可维一阶连续可微函数、可行域是连续闭集、不等式约束微函数、可行域是连续闭集、不等式约束3.可行方向法可行方向法是用梯度法去求解约束非线性最优化问题现代设计方法现代设计方法在可行域内选择一个初始点，当确定了一个可行方在可行域内选择一个初始点，当确定了一个可行方向向S(k)和适当步长和适当步长 后，按公式后，按公式X(k+1)=X(k)+(k)S(k)进行迭代计算，通过进行迭代计算，通过调整可行方向调整可行方向，使其既，使其既不超出不超出可行域可行域，又使，又使目标函数值有所下降目标函数值有所下降，经过若干次迭，经过若干次迭代，使迭代点逐步逼近

13、代，使迭代点逐步逼近约束最优点约束最优点。(1)可行方向法的基本思路可行方向法的基本思路在可行域内选择一个初始点，当确定了一个可行方向S(k)和适当现代设计方法现代设计方法(2)产生可行方向的条件产生可行方向的条件 可行条件可行条件方向方向S(k)可行，是指沿该方向作微小移动后，所得到可行，是指沿该方向作微小移动后，所得到的新点应是的新点应是可行点可行点(在可行域内在可行域内)。X(k)内点内点X(k)边界点边界点X(k)角点角点(2)产生可行方向的条件 可行条件X(k)内点X(k)边界现代设计方法现代设计方法可行的含义：可行的含义：若点若点X(k)在在J个约束面的交集上（即点个约束面的交集上

14、（即点X(k)有有J个起个起作用约束），要满足可行条件，方向作用约束），要满足可行条件，方向S(k)应和这应和这J个个约束函数约束函数在点在点X(k)的梯度的梯度 gu(X(k)(u Ik)的的夹角夹角均大于等于均大于等于900，若用向量关系式表示为：，若用向量关系式表示为：gu(X(k)TS(k)0 (u Ik)可行条件可行条件可行的含义：可行条件现代设计方法现代设计方法下降条件下降条件方向下降条件是指方向下降条件是指沿该方向作微小移动沿该方向作微小移动后，所得后，所得新新点的目标函数值是下降的点的目标函数值是下降的，而且，而且下降的愈快愈好下降的愈快愈好，显然，如果显然，如果负梯度方向负梯

15、度方向是可行方向，那么沿负梯度是可行方向，那么沿负梯度方向进行移动最有利。方向进行移动最有利。满足下降条件的方向应和满足下降条件的方向应和目标函数目标函数在点在点X(k)的梯度的梯度 f(X(k)交成钝角。用向量关系式可表示为交成钝角。用向量关系式可表示为 f(X(k)TS(k)/2可行下降方向所在的区域几何意义可行下降方向所在的区域几何意义/2可行下降方向所在的区域几何意义现代设计方法现代设计方法假设现已由初始点沿着目标函数的假设现已由初始点沿着目标函数的负梯度方向负梯度方向，找到，找到处于约束条件边界上的点处于约束条件边界上的点，此时目标函数的梯度为，此时目标函数的梯度为 f(X(k)，约

16、束条件，约束条件gi(X)0 的梯度为的梯度为 gi(X(k)，并设，并设下一步的迭代方向为下一步的迭代方向为 S(k)。要求沿。要求沿 S(k)方向迭代时，既方向迭代时，既能满足使目标函数值有所下降的条件，能满足使目标函数值有所下降的条件，即即 f(X(k)TS(k)0，又能满足约束条件，即，又能满足约束条件，即 gu(X(k)TS(k)0，则，则 S(k)必须位于必须位于阴影区阴影区。假设现已由初始点沿着目标函数的负梯度方向，找到处于约束条件边现代设计方法现代设计方法 最佳下降可行方向最佳下降可行方向在一个点的所有下降可行方向中，在一个点的所有下降可行方向中，使目标函数取得使目标函数取得最

17、大下降量的方向最大下降量的方向称为称为最佳下降可行方向最佳下降可行方向，显然，显然，当点当点X(k)处于可行域内时，目标函数的处于可行域内时，目标函数的负梯度方向负梯度方向就就是最佳下降可行方向，当点是最佳下降可行方向，当点X(k)处于几个起作用约束处于几个起作用约束的交点或交线上，即的交点或交线上，即 Ik为为X(k)的起作用约束的下标集合。的起作用约束的下标集合。最佳下降可行方向Ik为X(k)的起作用约束的下标集合。现代设计方法现代设计方法式式 gu(X(k)TS(k)0 (u Ik)和和 f(X(k)TS(k)0 只能提供只能提供下降可行方向的范围下降可行方向的范围，而，而不能直接给出最

18、佳下降可行方向，但是可以在满足上不能直接给出最佳下降可行方向，但是可以在满足上述可行条件的前提下，通过述可行条件的前提下，通过方向导数极小化方向导数极小化（保证最（保证最佳）的求解得到最佳下降可行方向。佳）的求解得到最佳下降可行方向。目标函数在目标函数在S方向的方向导数反映了方向的方向导数反映了目标函数值沿目标函数值沿S方方向的变化情况向的变化情况。方向导数越大，则目标函数值增加越方向导数越大，则目标函数值增加越快快，反之，方向导数越小，目标函数值下降越快。，反之，方向导数越小，目标函数值下降越快。式 gu(X(k)TS(k)0 (uIk现代设计方法现代设计方法目标函数目标函数f(X)在点在点

19、 X(k)的的方向导数方向导数由于梯度由于梯度 f(X(k)是常数向量，则是常数向量，则方向导数是方向导数是S的线的线性函数性函数，故最佳可行方向的寻求可归结为以下线性，故最佳可行方向的寻求可归结为以下线性规划问题。规划问题。式中，式中，S=s1,s2,snT，gu(X(k)为常数向量。为常数向量。目标函数f(X)在点 X(k)的方向导数由于梯度f(X(k现代设计方法现代设计方法(3)约束一维搜索约束一维搜索所谓约束一维搜索是指求解所谓约束一维搜索是指求解一元函数约束极小点一元函数约束极小点的算的算法，与前面讲的一维搜索相比，其特点在于：确定初法，与前面讲的一维搜索相比，其特点在于：确定初始区

20、间时，始区间时，对产生的每一个探测点都进行可行性判断对产生的每一个探测点都进行可行性判断，如果违反了某个或某些约束条件，就必须如果违反了某个或某些约束条件，就必须减小步长因减小步长因子子，以，以使新的探测点落在最近的一个约束曲面上使新的探测点落在最近的一个约束曲面上或或约约束曲面的一个允许的区间内束曲面的一个允许的区间内。约束容限：约束容限：如果如果X(k)满足满足-gu(X(k)(给定的约给定的约束容限束容限)，则认为点，则认为点X(k)落在约束边界上落在约束边界上(可行点可行点)。(3)约束一维搜索所谓约束一维搜索是指求解一元函数约束极现代设计方法现代设计方法n 若若得得到到的的相相邻邻三

21、三个个探探测测点点都都是是可可行行点点，而而且且函函数数值值呈呈“大大小小大大”变变化化，则则与与前前述述一一维维搜搜索索相相同同，两两端端点点所所决决定定的的区区间间就就是是初初始始区区间间，接接着着缩缩小小区区间间得得到到一维极小点。一维极小点。n 若最后得到的探测点落在约束曲面的一个容限之内，若最后得到的探测点落在约束曲面的一个容限之内，而且而且函数值比前一点的小函数值比前一点的小，则该点就是一维极小点，则该点就是一维极小点，不需再进行区间缩小计算。不需再进行区间缩小计算。-f(3)若得到的相邻三个探测点都是可行点，而且函数值呈“大小大现代设计方法现代设计方法4.可行方向法的迭代步骤可行

22、方向法的迭代步骤1）给定初始内点）给定初始内点X(0)，收敛精度，收敛精度 和约束容限和约束容限，置，置k=0；2）确定点）确定点X(k)的起作用约束集合的起作用约束集合（每一个迭代点的（每一个迭代点的Ik不一样，因此需要确定每一个迭代点的不一样，因此需要确定每一个迭代点的Ik）；4.可行方向法的迭代步骤1）给定初始内点X(0)，收敛精度现代设计方法现代设计方法当当Ik为空集（表示约束都不起作用），且为空集（表示约束都不起作用），且点点X(k)在可在可行域内时行域内时，如果，如果 ，则令，则令X*=X(k),f(X*)=f(X(k),终止计算终止计算;否则否则,令令 S*=-f(X(k)，转，

23、转5）；）；当当Ik非空时（表示有起作用约束），转非空时（表示有起作用约束），转3）；）；(点点X(k)在某些约束边界上，判断是否为极值点，即是否满足在某些约束边界上，判断是否为极值点，即是否满足K-T条件条件)当Ik为空集（表示约束都不起作用），且点X(k)在可行域内时现代设计方法现代设计方法3）收敛判断：点）收敛判断：点X(k)是否满足是否满足kt条件；条件；令令 ，解出，解出 u 若若 u 全大于全大于0，输出，输出 X*=X(k),f(X*)=f(X(k)，终，终止迭代；止迭代；（X(k)即为极值点）即为极值点）若若 u 不全大于不全大于0，转，转4）；（X(k)不是极值点，寻不是极值

24、点，寻找最佳可行下降方向，按找最佳可行下降方向，按最佳下降可行方向最佳下降可行方向迭代搜迭代搜索，索，y因此需要构造线性规划问题）因此需要构造线性规划问题）3）收敛判断：点X(k)是否满足kt条件；现代设计方法现代设计方法4）求解线性规划问题）求解线性规划问题 min (S)=f(X(k)TS s.t gu(X(k)TS0为了进一步理解外点法，我们考虑一种只有不等式约束的情况，此时现代设计方法现代设计方法可可以以清清楚楚地地看看出出，外外点点法法的的惩惩罚罚项项是是定定义义于于可可行行域域之之外外的的。事事实实上上，外外点点法法的的迭迭代代过过程程是是从从可可行行域外域外一步步向一步步向可行域

25、边界可行域边界逼近的逼近的。这正是外点法名称的由来。这正是外点法名称的由来。可以清楚地看出，外点法的惩罚项是定义于可行域之外的。事实上，现代设计方法现代设计方法惩罚项的大小还与惩罚惩罚项的大小还与惩罚加权因子加权因子(k)有关。当惩罚因有关。当惩罚因子按一个递增的正数序列子按一个递增的正数序列(0)(1)(2)(k)(k+1)(1)(2)0n当惩罚因子当惩罚因子(k)0 时，才能求得在约束边界上的时，才能求得在约束边界上的最优解。最优解。惩罚因子的特点：内点惩罚函数法的惩罚因子(k)是一个递减的现代设计方法现代设计方法2 2）初始惩罚因子）初始惩罚因子(0)的选择的选择初始惩罚因子的选择会影响

26、到迭代计算能否正常进初始惩罚因子的选择会影响到迭代计算能否正常进行以及计算效率的高低，行以及计算效率的高低，(0)的的值应适当。值应适当。若若(0)太大，则开始几次构造的惩罚函数的太大，则开始几次构造的惩罚函数的无约束无约束极值点会离约束边界很远极值点会离约束边界很远，将增加迭代次数，使计，将增加迭代次数，使计算效率降低。算效率降低。若若(0)太小，惩罚函数中的太小，惩罚函数中的障碍项的作用就会很小障碍项的作用就会很小，使使惩罚函数性态变坏惩罚函数性态变坏，甚至难以收敛到原约束目标，甚至难以收敛到原约束目标函数的极值点。函数的极值点。2）初始惩罚因子(0)的选择现代设计方法现代设计方法目前，还

27、没有一定的有效方法，往往要经过多次试目前，还没有一定的有效方法，往往要经过多次试算，才能确定一个适当的算，才能确定一个适当的(0)。多数情况下，一般取多数情况下，一般取(0)1 ，然后根据试算的结果，然后根据试算的结果，加以调整；加以调整；或按经验公式取值或按经验公式取值 使惩罚项和原目标函使惩罚项和原目标函数在惩罚函数中的作数在惩罚函数中的作用相当。用相当。目前，还没有一定的有效方法，往往要经过多次试算，才能确定一个现代设计方法现代设计方法3 3）惩罚因子缩减系数）惩罚因子缩减系数c c的选择的选择在构造序列惩罚函数时，在构造序列惩罚函数时，惩罚因子惩罚因子(k)是一个逐次递是一个逐次递减到

28、减到0 0的数列，相邻两次迭代的惩罚因子关系式为：的数列，相邻两次迭代的惩罚因子关系式为：(k)=c (k-1)其中，其中，c是惩罚因子的缩减系数，通常取值为是惩罚因子的缩减系数，通常取值为0.10.7。一般来说，一般来说，c值的大小对收敛速度无明显影响，在迭值的大小对收敛速度无明显影响，在迭代过程中不起决定性作用。代过程中不起决定性作用。3）惩罚因子缩减系数c的选择一般来说，c值的大小对收敛速度无现代设计方法现代设计方法4 4）收敛条件）收敛条件内点法的收敛准则为：内点法的收敛准则为：或或相对值差相对值差准则准则点距准则点距准则4）收敛条件或相对值差准则点距准则现代设计方法现代设计方法5）内

29、点法的迭代步骤：）内点法的迭代步骤：步骤步骤1：选选X(0)，可行初始点，可行初始点 X(0)不应在边界上不应在边界上，最好，最好不要靠近任何一个约束边界不要靠近任何一个约束边界；步骤步骤2：选选 (0)、c、1或或 2，令，令k=0（迭代次数）；（迭代次数）；步骤步骤3：构造惩罚函数构造惩罚函数(X,(k)，选某一适当的无约，选某一适当的无约束优化方法，求束优化方法，求 min(X,(k)，得到，得到 X*(k)，令令 X(k+1)=X*(k)；步骤步骤4：判断迭代点是否收敛，若满足收敛条件，迭代判断迭代点是否收敛，若满足收敛条件，迭代 终止，约束最优解为：终止，约束最优解为：X*=X(k+

30、1),f(X*)=f X(k+1)否则，令否则，令 (k+1)=c(k)，k=k+1，转步骤，转步骤3。5）内点法的迭代步骤：现代设计方法现代设计方法6 6）举例）举例用内点法求解约束优化问题：用内点法求解约束优化问题：min f(X)=x1+x2 s.t g1(X)=x12-x2 0 g2(X)=-x1 0收敛准则：点距准则，收敛准则：点距准则，=0.01=0.01 6）举例用内点法求解约束优化问题：现代设计方法现代设计方法4.混合惩罚函数法混合惩罚函数法这种方法是将内点法和外点法的惩罚函数形式结合在这种方法是将内点法和外点法的惩罚函数形式结合在一起，扬长避短，可用来求解同时具有一起，扬长避

31、短，可用来求解同时具有等式约束等式约束和和不不等式约束函数等式约束函数的优化问题。的优化问题。对于约束优化问题对于约束优化问题 min f(X)X Rn s.t gu(X)0 (u=1,2,m)hv(X)0 (v=1,2,p)4.混合惩罚函数法这种方法是将内点法和外点法的惩罚函数形式现代设计方法现代设计方法混合法求解时，惩罚函数的形式为：混合法求解时，惩罚函数的形式为：惩罚项，惩罚因子为按内点法选取，即：惩罚项，惩罚因子为按内点法选取，即 (0)(1)(2)0 ：惩罚项，惩罚因子为：惩罚项，惩罚因子为 ，(k)0时，时，,满足外点法对惩罚因子的要求。满足外点法对惩罚因子的要求。混合法求解时，惩

32、罚函数的形式为：现代设计方法现代设计方法可见，混合法对可见，混合法对不等式约束不等式约束采用采用内点法内点法构造惩构造惩罚项，对罚项，对等式约束等式约束采用采用外点法外点法构造惩罚项。构造惩罚项。混合法的求解特点与内点法相同，混合法的求解特点与内点法相同，迭代过程在迭代过程在可行域内进行可行域内进行，初始点，初始点X(0)，惩罚因子初始值，惩罚因子初始值 (0)、惩罚因子缩减系数均可参考内点法选取。惩罚因子缩减系数均可参考内点法选取。可见，混合法对不等式约束采用内点法构造惩现代设计方法现代设计方法作业作业1.教材教材P127习题习题3-212.分别用内点和外点惩罚函数法求解下列约束优化分别用内点和外点惩罚函数法求解下列约束优化问题：问题：作业1.教材P127习题3-21