第02章优化设计-2

第2章优化设计(2)ⅡOptimalDesign2.4多维无约束优化方法2.4.3梯度法梯度法是求解多维无约束优化问题的解析法之一。()()(1)()()()()()()()()kkkkkkkkkSfXXXSXfX基于梯度是函数变化率最大的方向，而负梯度则是函数下降最快的方向。沿该方向搜索，使函数值在该点附近下降最快。则梯度法就是取迭代点处的函数负梯度方向作为搜索方向，该法又称最速下降法。梯度法的迭代格式：（2-40）梯度法的基本思想:按上式求得负梯度方向的一个极小点，作为原问题的一个近似最优解；若此解尚不满足精度要求，则再以作为迭代起始点，以处的负梯度方向作为搜索方向，求得该方向的极小点，如此进行下去，直到求得的解满足收敛条件为止。)1(kX(1)()kfX(2)kX)1(kX)1(kX式中为最优步长。关于的梯度法迭代计算步骤见教材。()k()kX112212()102()42()fXxxxfXxxfXx解：由梯度的定义，该目标函数的梯度为：例2-A已知一目标函数为22121212()60104fXxxxxxx，试求在点的梯度。()112()12122()1021021210()42()42211kkxfXxxxfXxxfXx则该函数在点的梯度为()1,2TkX梯度法的终止条件：()||()||kfX()1()()2()()()()()kkkknfXxfXfXxfXx2()()1/21()||()||[()]knkiifXfXx梯度法的特点：(1)算法简单；(2)前后两次迭代方向正交，所以搜索路线是呈直角锯齿形；(3)开始搜索时，收敛速度较快，但当靠近极小点附近，收敛速度越来越慢，这是梯度法的较大缺点。（2-41）2.4.4牛顿法原始牛顿法和阻尼牛顿法两种。其迭代过程是在求目标函数的极小值时，先将它在点附近作泰勒展开，并取二次近似函数式；然后求出这个二次函数的极小点，并以该极小点作为原目标函数的极小点X*的一次近似解；()kX()fX该算法的基本思路：它是以二次函数来逼近原目标函数。牛顿法也是一种解析法，它是梯度法的进一步发展。该法的搜索方向的构造：是根据目标函数的负梯度和二阶偏导数矩阵来构造的。牛顿法分为：若此解不满足精度要求，则可以此近似解作为下一次迭代的初始点，仿照上面的做法，求出二次近似解；照此迭代下去，直至所求出的近似极小点满足精度要求。现用二维问题来加以说明，将目标函数在给定点作泰勒展开，并取二次近似式：()kX()()()()()()()()()[()]()1()()()2kkTkkkkfXXfXfXXXXXHXXX(2-42)()fX为求得二次近似式的极小点，对上式求梯度，并令)(X*X()()()()()()[]0kkkXfXHXXX解之可求得：*()()1()[()]()kkkXXHXfX式中:为海森（Hessian）矩阵的逆矩阵。()1[()]kHX在一般情况下，不一定是二次函数，则所求得的极小点也不一定是原目标函数的真正极小点。但由于在点附近，函数和是近似的，因而可作为的近似极小点。为求得满足精度要求的近似极小点，可将作为下一次迭代的起始点，即得(1)()()1()[()]()kkkkXXHXfX()fX*X*X()fX)(kX()fX)1(kX()fX*X)(X（2-44）()()1()[()]()kkkSHXfX由上式(2-44)可知，牛顿法的搜索方向为（2-45）上式就是原始牛顿法的迭代公式。上式中的搜索方向称为牛顿方向，可见原始牛顿法的步长因子恒取：，因此，原始牛顿法是一种定步长的迭代过程。)(kS()1k牛顿算法对于二次函数是非常有效的，迭代一步就可达到极值点，而这一步根本不需要进行一维搜索。对于高次函数，只有当迭代靠近极值点附近，目标函数近似二次函数时，才会保证很快收敛，否则也可能导致算法失败。为了克服这一缺点，便将迭代公式（2-44）修改为：(1)()()()1()[()]()kkkkkXXHXfX)(k（2-46）上式为修正牛顿法的迭代公式。式中，步长因子又称阻尼因子。修正牛顿法的迭代步骤详见教材。2.4.5变尺度法是在克服了梯度法收敛慢和牛顿法计算量大的缺点基础上而发展起来的一种最有效的解析法。现已得到广泛应用。利用牛顿法的迭代形式，但并不直接计算，而是用一个对称正定矩阵近似地代替。它在迭代过程中不断地改进，最后逼近。这种算法，省去了海森矩阵的计算和求逆，使之计算量大为减少，并且还保持了牛顿法收敛快的优点。()1[()]kHX()kA(*)1[()]HX()1[()]kHX变尺度法：在变尺度法中，较为常用的有：变尺度法特点：●DFP变尺度法●BFGS变尺度法。变尺度法基本思想：1.DFP变尺度法DFP变尺度法是最为常用的一种变尺度算法。该算法的迭代公式为：(1)()()()()()()()()kkkkkkkkXXSXAfX(2-47)式中:变尺度矩阵，是一n×n阶对称正定矩阵，在迭代过程中,它是逐次形成并不断修正，即从一次迭代到另一次迭代是变化的，故称变尺度矩阵。()kA由式(2-47)，不难看出：当（单位矩阵）时：式(2-47)变为梯度法的迭代公式；当时：式(2-47)就变为牛顿法的迭代公式。()kAI()()1[()]kkAHX由此可见，梯度法和牛顿法可以看作变尺度法的一种特例。变尺度矩阵可用下式迭代：(1)()()kkkAAA式中，称作校正矩阵，在DFP变尺度法中它可用下式来计算：()kA()()()()()()()()()()()()[][][][]kkTkkkTkkkTkkTkkXXAggAAXggAg式中:第k次迭代中前后迭代点的向量差；前后迭代点的梯度向量差。()(1)()()(1)()()()kkkkkkXXXgfXfX迭代开始（k＝0）规定：。(0)HI（2-55）（2-54）式（2-55）称为DFP公式，由该式可以看出，变尺度矩阵的确定取决于在第k次迭代中的下列信息：不仅不需求海森矩阵及其求逆矩阵的计算，而且保持了牛顿法收敛速度快和梯度法计算简单的优点。(1)kA●上次的变尺度矩阵，●迭代点的向量差和迭代点的梯度向量差。)(kA)(kX)(kg)()(kXH利用上式求得的校正矩阵代入式(2-54)，可得到变尺度矩阵的DFP递推公式：()()(k)()()(k)(1)()()()()(k)()AAATTkkkkkkTTkkkkXXggAAXggg()kA（2-56）上式常称DFP公式。通过式(2-47)可确定新的搜索方向，进行第k+1次迭代的一维搜索。)(kS因此，DFP变尺度法：)0(X(0)()fXDFP变尺度法的迭代步骤为：(1)给定初始点和收敛精度ε，维数n；(2)计算梯度，取A(0)=I(单位矩阵)，置k=0，(3)构造搜索方向()()()()kkkSAfX)(kS)(k(k)()()()()(X)min(X)kkkkfSfS(1)()kfX(1)()kfX*(1)*(1),()()kkXXfXfX(4)沿方向进行一维搜索，求最优步长，使得到新迭代点(5)计算，进行收敛判断：若，则令，停止迭代，输出最优解；否则，转下一步(6)；(1)()()()kkkkXXS()()()(1),,;kkkkXgAA(1)()(1)(1)(1)(1)()kkkkkkAAASAfX1kkDFP变尺度法的计算框图，见图2-32。并令，转步骤(3)。(7)计算：构造新的变尺度矩阵和搜索方向：(6)检查迭代次数，若k=n，则令，并转入步骤(2)；若kn，则转下步(7)；(0)(1)kXX图2-32DFP变尺度法的计算框图2.BFGS变尺度法计算实践表明：由于DFP变尺度法在计算变尺度矩阵的公式中，其分母含有近似矩阵A(k)，使之计算中容易引起数值不稳定，甚至有可能得到奇异矩阵A(k)。BFGS变尺度法与DFP变尺度法的迭代步骤相同，不同之点，只是校正矩阵的计算公式不一样。BFGS变尺度法的变尺度矩阵迭代公式仍为(1)()()kkkAAA(2-57)为了克服DFP变尺度法计算稳定性不够理想的缺点，Broydon等人在DFP法的基础上提出了另一种变尺度法称为BFGS变尺度法。但其中的校正矩阵的计算公式为()()()()()()()()()()()()()()()()()()1{}TTkkkkkTkkkTTkkkkTTkkkkkkXXgAgAXXXgXgAgXXgA(2-58)上式中，所使用的基本变量、、与DFP变尺度法相同。由上式可见，BFGS变尺度法的校正矩阵的分母中不再含有近似矩阵。)(kX)(kg)(kA)(kA)(kA)(kA)(kABFGS法与DFP法具有相同性质，这两种方法都是使每次迭代中目标函数值减少，并保持的对称正定性，则一定逼近海森矩阵的逆矩阵。在于计算中它的数值稳定性强，所以它是目前变尺度法中最受欢迎的一种算法。BFGS法的优点:2.5约束优化方法工程中的大量优化设计问题，都是约束优化问题，这类问题的一般数学模型为：min(),..()01,2,,()01,2,,,nuvfXXRstgXumhXvpn求解这类问题的方法称约束优化方法，所求得的最优点X*称为约束最优点。约束优化算法大致可归纳为两大类：（2-59）●直接解法●间接解法这类方法的基本思想：在约束的可行域内直接搜索出它的约束最优解。属于这类方法的主要有：网格法，可行方向法，复合形法等。这类方法的基本思想：将复杂的约束问题转化为一系列无约束优化问题，即按一定原则构造一个新的目标函数，并以它的最优化解去逐步逼近原约束问题的最优解。约束问题通过这种方法的处理，就可以采用无约束优化方法求解。()X本节主要介绍：复合形法和惩罚函数法。属于这类方法的主要有：消元法、简约梯度法、复合形法、惩罚函数法等。这类方法对于只有不等式约束的优化问题是有效的。这类方法对于解决具有不等式约束和等式约束条件的优化问题都有效。直接解法：间接解法：2.5.1复合形法复合形法：是适用于求解具有不等式约束优化问题的一种直接算法。在n维优化设计空间的可行域D内，构造具有k个顶点的多边形(或多面体)称作复合形。复合形的每个顶点都代表一个设计方案。然后计算复合形各顶点的目标函数值并逐一进行比较，取函数值最大者为最坏点，最小者为最好点。再以去掉最坏点的其余各点的中心点为映射轴心，在最坏点和其余各点的中心点的连线上，寻找一个既满足约束条件，又使目标函数值有所改善的坏点映射点，并以该映射点替换坏点而构成新的复合形。按照上述步骤重复多次，不断地去掉最坏点，这样不断调整复合形的顶点，使复合形不断向最优点靠拢，最后搜索到约束优化问题的最优解。(12)nkn该法的基本思路：对于二维问题，复合形法的搜索原理，如图2-33所示。图2-33复合形法原理因此，复合形法的迭代过程实际就是通过对复合形各顶点的函数值计算与比较，反复进行点的映射与复合形的收缩，使之逐步逼近约束问题最优解的。min(),..()0,(12,)nufXXRstgXum，，（2-60）根据上述复合形法的基本思想，对于求解的优化问题时，采用复合形法来求解，需分两步进行：●第一步：是在设计空