现代设计方法课件第5节

现代设计方法第三章优化设计OptimizationDesign现代设计方法本章主要内容优化设计概述优化问题的数学分析基础一维探索优化方法无约束多维问题的优化方法约束问题的优化方法多目标函数的优化方法LINGO在优化设计中的应用现代设计方法3.5约束问题的优化方法约束优化方法是用来求解如下非线性约束优化问题的数值迭代算法。),2,1(0)(),2,1(0)(..)(minpvXhmuXgtsRXXfvun根据处理约束条件的不同方式，求解这类问题的方法分为直接法和间接法。现代设计方法直接法：在迭代过程中逐点考察约束的可行域，并使迭代点始终局限于可行域之内的算法称为直接法。常用的直接法有：随机试验、随机方向搜索法、复合形法、可行方向法、约束坐标轮换法、网格法等；间接法：把约束条件引入目标函数，使约束优化问题转化为相对简单的二次规划问题或线性规划问题求解的算法称为间接法，常用的间接法有消元法、拉格朗日乘子法、惩罚函数法和序列线性规划法等。现代设计方法一、约束优化问题的直接法在可行域内按照一定的准则，直接探索出问题的最优点，而无须将约束问题转换成无约束问题去求优的方法，称为约束优化问题的直接法。约束条件常常使得可行域非凸集出现众多的局部极值点，不同的初始点往往会导致探索点逼近不同的局部极值点，因此需要多次变更初始点进行多路探索。现代设计方法1.随机试验法（统计模拟试验法）基本思想：利用计算机产生的伪随机数，从设计方案集合中分批抽样。每批抽样均包含若干方案，对每个方案都做约束检验，不满足则重抽，满足则按照它们的函数值的大小进行排列，取出前几个或者几十个相差不是很大的函数值，然后再做下批试验。当每批抽样试验的前几个函数值不再明显变动时，则可认为它已经按照概率收敛于某一最优方案。现代设计方法迭代算法:（8个步骤）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为每批试验中的方案数(设计变量可能取到的值的个数)。现代设计方法4）约束条件的检验，gu(x1(k),x2(k),…,xn(k))≤0(u=1，2，…，m)。5）计算试验点的函数值，并循环转向2）进行N次。6）将N个试验点的函数值按大小排序，找出最优点及其函数值，即f(X(L))=min{f(X(k))(k=1,2,…,N)}实验点:X(k)=[x1(k),x2(k),,xn(k)]现代设计方法7）确定前p个最好的试验点的均值Xi和均方根差i，当Xi基本不变动或者i≤时，得到近似最优点，否则转向下一步。8）构造新的试验区间[Xi-3i,Xi+3i]，并转向3）。现代设计方法2.随机方向探索法当采用随机方向为探索方向时，称为随机方向探索法，该方法一般包括初始点、探索方向和探索步长随机选择三部分。现代设计方法约束随机方向探索法的基本原理现代设计方法迭代步骤：（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))方向以适当步长(试探)向前跨步，得到新点X(1)。现代设计方法3）如果f(X(1))f(X(L))，则以X(1)为新的初始点，转向2）重复前面的过程，否则，以较小的试验步长向前探索，直到目标函数值不再下降而又符合约束条件为止。然后将探索得到的新点作为下一次的初始点，重复2）和3）。4）当同一次迭代的初始点和末点的函数值满足收敛准则时，则停止迭代，并取X*=X(k);f(X*)=f(X(k))现代设计方法3.可行方向法可行方向法是用梯度法去求解约束非线性最优化问题的一种有代表性的解法，是求解大型约束优化问题的主要方法之一。其收敛速度快，效果好，但程序比较复杂，计算困难且工作量大。数学基础：梯度法、方向导数、k—t条件适用条件：目标函数和约束函数均为n维一阶连续可微函数、可行域是连续闭集、不等式约束现代设计方法在可行域内选择一个初始点，当确定了一个可行方向S(k)和适当步长后，按公式X(k+1)=X(k)+(k)S(k)进行迭代计算，通过调整可行方向，使其既不超出可行域，又使目标函数值有所下降，经过若干次迭代，使迭代点逐步逼近约束最优点。(1)可行方向法的基本思路现代设计方法(2)产生可行方向的条件可行条件方向S(k)可行，是指沿该方向作微小移动后，所得到的新点应是可行点(在可行域内)。01g02g04g03g)(kX)(kS01g02g04g03g)(kX)(kS)()(2kXg01g02g04g03g)(kX)(kS)()(2kXg)()(3kXgX(k)内点X(k)边界点X(k)角点现代设计方法可行的含义：若点X(k)在J个约束面的交集上（即点X(k)有J个起作用约束），要满足可行条件，方向S(k)应和这J个约束函数在点X(k)的梯度gu(X(k))(uIk)的夹角均大于等于900，若用向量关系式表示为：[gu(X(k))]TS(k)0(uIk)可行条件现代设计方法下降条件方向下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的，而且下降的愈快愈好，显然，如果负梯度方向是可行方向，那么沿负梯度方向进行移动最有利。满足下降条件的方向应和目标函数在点X(k)的梯度f(X(k))交成钝角。用向量关系式可表示为[f(X(k))]TS(k)0下降条件现代设计方法综上所述，可行方向就是既满足可行条件，又满足下降条件的方向。用向量关系式表示为：)(0)()()(kkTkuIuSXg0)()(KTkSXf可行条件下降条件同时满足上面两个条件的方向称为可行方向，又称为下降可行方向。可行方向很多，哪一个最快最优呢？现代设计方法/2/2可行下降方向所在的区域几何意义现代设计方法假设现已由初始点沿着目标函数的负梯度方向，找到处于约束条件边界上的点，此时目标函数的梯度为f(X(k))，约束条件gi(X)≤0的梯度为gi(X(k))，并设下一步的迭代方向为S(k)。要求沿S(k)方向迭代时，既能满足使目标函数值有所下降的条件，即[f(X(k))]TS(k))0，又能满足约束条件，即[gu(X(k))]TS(k))0，则S(k)必须位于阴影区。现代设计方法最佳下降可行方向在一个点的所有下降可行方向中，使目标函数取得最大下降量的方向称为最佳下降可行方向，显然，当点X(k)处于可行域内时，目标函数的负梯度方向就是最佳下降可行方向，当点X(k)处于几个起作用约束的交点或交线上，即kkukkuIuXgIuXg00)()(Ik为X(k)的起作用约束的下标集合。现代设计方法式[gu(X(k))]TS(k)0(uIk)和[f(X(k))]TS(k)0只能提供下降可行方向的范围，而不能直接给出最佳下降可行方向，但是可以在满足上述可行条件的前提下，通过方向导数极小化（保证最佳）的求解得到最佳下降可行方向。目标函数在S方向的方向导数反映了目标函数值沿S方向的变化情况。方向导数越大，则目标函数值增加越快，反之，方向导数越小，目标函数值下降越快。现代设计方法目标函数f(X)在点X(k)的方向导数SXfSXfT(k)(k)由于梯度f(X(k))是常数向量，则方向导数是S的线性函数，故最佳可行方向的寻求可归结为以下线性规划问题。),,2,1(11)(0..min)()(nisIuSXgtsSXfSikTkuTk式中，S=[s1,s2,sn]T，gu(X(k))为常数向量。现代设计方法(3)约束一维搜索所谓约束一维搜索是指求解一元函数约束极小点的算法，与前面讲的一维搜索相比，其特点在于：确定初始区间时，对产生的每一个探测点都进行可行性判断，如果违反了某个或某些约束条件，就必须减小步长因子，以使新的探测点落在最近的一个约束曲面上或约束曲面的一个允许的区间内。约束容限：如果X(k)满足-gu(X(k))(给定的约束容限)，则认为点X(k)落在约束边界上(可行点)。现代设计方法02g01g2x1xo0a1a2a3a3a1a2a3a3afxo)(1af)(2af)(3af)(3af1a2a3a3afxo)(1af)(2af)(3af)(3af若得到的相邻三个探测点都是可行点，而且函数值呈“大—小—大”变化，则与前述一维搜索相同，两端点所决定的区间就是初始区间，接着缩小区间得到一维极小点。若最后得到的探测点落在约束曲面的一个容限之内，而且函数值比前一点的小，则该点就是一维极小点，不需再进行区间缩小计算。-f(3)现代设计方法4.可行方向法的迭代步骤1）给定初始内点X(0)，收敛精度和约束容限，置k=0；2）确定点X(k)的起作用约束集合（每一个迭代点的Ik不一样，因此需要确定每一个迭代点的Ik）；muXguXIkukk,,2,1,,)()(现代设计方法当Ik为空集（表示约束都不起作用），且点X(k)在可行域内时，如果，则令X*=X(k),f(X*)=f(X(k)),终止计算;否则,令S*=-f(X(k))，转5）；当Ik非空时（表示有起作用约束），转3）；(点X(k)在某些约束边界上，判断是否为极值点，即是否满足K-T条件))(kXf现代设计方法3）收敛判断：点X(k)是否满足k—t条件；令，解出u若u全大于0，输出X*=X(k),f(X*)=f(X(k))，终止迭代；（X(k)即为极值点）若u不全大于0，转4）；（X(k)不是极值点，寻找最佳可行下降方向，按最佳下降可行方向迭代搜索，y因此需要构造线性规划问题）00ukuIuukXgXfk0kuIuukXgXfk现代设计方法4）求解线性规划问题min(S)=[f(X(k))]TSs.t[gu(X(k))]TS0-1si1(i=1,2,,n)得到S*，令S(k)=S*（最佳下降可行方向）；5）在方向S(k)上进行约束一维搜索得点X(k+1)，令k=k+1，转2）。现代设计方法Eg:用可行方向法求解约束优化问题,=0.02；=0.010)(0)(055)(02)(..64222)(min241321221121212221xXgxXgxxXgxxXgtsxxxxxxXf16.7)()(3124,3135)2(*)2(XfXfXXT*求解结果现代设计方法解:(1)取，计算得：TX0,004,3,00kIXf点X(k)在某些约束边界上,因此需要判断是否为极值点,即是否满足K-T条件。注:如何求Ik？Ik为X(k)起作用的约束的下标集合。64624,424,01221210XXTTxxxxxfxfXf010,1,02103XXTTxfxfXg101,0,02104XXTTxfxfXg现代设计方法令，有即解得3=-4，4=-6，不满足K-T条件（X(0)不是极值点，寻找最佳可行下降方向，按最佳下降可行方向迭代搜索