现代设计方法14章-优化设计-多维无约束优化2

第14讲最优化设计多维无约束优化2,14.3梯度法,梯度法是求解多维无约束优化问题的解析法之一。,基于梯度是函数变化率最大的方向，而负梯度则是函数下降最快的方向。沿该方向搜索，使函数值在该点附近下降最快。则梯度法就是取迭代点处的函数负梯度方向作为搜索方向，该法又称最速下降法。,梯度法的迭代格式：,梯度法的基本思想:,按上式求得负梯度方向的一个极小点，作为原问题的一个近似最优解；若此解尚不满足精度要求，则再以作为迭代起始点，以处的负梯度方向作为搜索方向，求得该方向的极小点，如此进行下去，直到求得的解满足收敛条件为止。,式中为最优步长。关于的梯度法迭代计算步骤见教材。,解：由梯度的定义，该目标函数的梯度为：,例14-A已知一目标函数为,，,试求在点的梯度。,则该函数在点的梯度为,梯度法的终止条件：,梯度法的特点：(1)算法简单；(2)前后两次迭代方向正交，所以搜索路线是呈直角锯齿形；(3)开始搜索时，收敛速度较快，但当靠近极小点附近，收敛速度越来越慢，这是梯度法的较大缺点。,14.4牛顿法,原始牛顿法和阻尼牛顿法两种。,其迭代过程是在求目标函数的极小值时，先将它在点附近作泰勒展开，并取二次近似函数式；然后求出这个二次函数的极小点，并以该极小点作为原目标函数的极小点X*的一次近似解；,该算法的基本思路：,它是以二次函数来逼近原目标函数。,牛顿法也是一种解析法，它是梯度法的进一步发展。,该法的搜索方向的构造：,是根据目标函数的负梯度和二阶偏导数矩阵来构造的。,牛顿法分为：,若此解不满足精度要求，则可以此近似解作为下一次迭代的初始点，仿照上面的做法，求出二次近似解；照此迭代下去，直至所求出的近似极小点满足精度要求。,现用二维问题来加以说明，将目标函数在给定点作泰勒展开，并取二次近似式：,为求得二次近似式的极小点，对上式求梯度，并令,解之可求得：,式中:为海森（Hessian）矩阵的逆矩阵。,在一般情况下，不一定是二次函数，则所求得的极小点也不一定是原目标函数的真正极小点。但由于在点附近，函数和是近似的，因而可作为的近似极小点。为求得满足精度要求的近似极小点，可将作为下一次迭代的起始点，即得,由上式可知，牛顿法的搜索方向为,上式就是原始牛顿法的迭代公式。,上式中的搜索方向称为牛顿方向，可见原始牛顿法的步长因子恒取：，因此，原始牛顿法是一种定步长的迭代过程。,牛顿算法对于二次函数是非常有效的，迭代一步就可达到极值点，而这一步根本不需要进行一维搜索。对于高次函数，只有当迭代靠近极值点附近，目标函数近似二次函数时，才会保证很快收敛，否则也可能导致算法失败。,为了克服这一缺点，便将迭代公式修改为：,上式为修正牛顿法的迭代公式。式中，步长因子又称阻尼因子。,修正牛顿法的迭代步骤详见教材。,14.5变尺度法,是在克服了梯度法收敛慢和牛顿法计算量大的缺点基础上而发展起来的一种最有效的解析法。现已得到广泛应用。,利用牛顿法的迭代形式，但并不直接计算，而是用一个对称正定矩阵近似地代替。它在迭代过程中不断地改进，最后逼近。,这种算法，省去了海森矩阵的计算和求逆，使之计算量大为减少，并且还保持了牛顿法收敛快的优点。,变尺度法：,在变尺度法中，较为常用的有：,变尺度法特点：,DFP变尺度法BFGS变尺度法。,变尺度法基本思想：,1.DFP变尺度法,DFP变尺度法是最为常用的一种变尺度算法。该算法的迭代公式为：,(14-7),式中:变尺度矩阵，是一nn阶对称正定矩阵，在迭代过程中,它是逐次形成并不断修正，即从一次迭代到另一次迭代是变化的，故称变尺度矩阵。,由式(14-7)，不难看出：当（单位矩阵）时：式(14-7)变为梯度法的迭代公式；当时：式(14-7)就变为牛顿法的迭代公式。,由此可见，梯度法和牛顿法可以看作变尺度法的一种特例。,变尺度矩阵可用下式迭代：,式中，称作校正矩阵，在DFP变尺度法中它可用下式来计算：,式中:,第k次迭代中前后迭代点的向量差；,前后迭代点的梯度向量差。,迭代开始（k0）规定：。,上式称为DFP公式，由该式可以看出，变尺度矩阵的确定取决于在第k次迭代中的下列信息：,不仅不需求海森矩阵及其求逆矩阵的计算，而且保持了牛顿法收敛速度快和梯度法计算简单的优点。,上次的变尺度矩阵，,迭代点的向量差和迭代点的梯度向量差。,利用上式求得的校正矩阵代入式(14-54)，可得到变尺度矩阵的DFP递推公式：,（14-8）,上式常称DFP公式。通过式(14-7)可确定新的搜索方向，进行第k+1次迭代的一维搜索。,因此，DFP变尺度法：,DFP变尺度法的迭代步骤为：,(1)给定初始点和收敛精度，维数n；,(2)计算梯度，取A(0)=I(单位矩阵)，置k=0，,(3)构造搜索方向,(4)沿方向进行一维搜索，求最优步长，使,得到新迭代点,(5)计算，进行收敛判断：,若，则令，停止迭代，输出最优解；否则，转下一步(6)；,DFP变尺度法的计算框图，见图14-32。,并令，转步骤(3)。,(7)计算：,构造新的变尺度矩阵和搜索方向：,(6)检查迭代次数，若k=n，则令，并转入步骤(2)；若kn，则转下步(7)；,图14-32DFP变尺度法的计算框图,2.BFGS变尺度法,计算实践表明：由于DFP变尺度法在计算变尺度矩阵的公式中，其分母含有近似矩阵A(k)，使之计算中容易引起数值不稳定，甚至有可能得到奇异矩阵A(k)。,BFGS变尺度法与DFP变尺度法的迭代步骤相同，不同之点，只是校正矩阵的计算公式不一样。BFGS变尺度法的变尺度矩阵迭代公式仍为,为了克服DFP变尺度法计算稳定性不够理想的缺点，Broydon等人在DFP法的基础上提出了另一种变尺度法称为BFGS变尺度法。,但其中的校正矩阵的计算公式为,(14-9),上式中，所使用的基本变量、与DFP变尺度法相同。由上式可见，BFGS变尺度法的校正矩阵的分母中不再含有近似矩阵。,BFGS法与DFP法具有相同性质，这两种方法都是使每次迭代中目标函数值减少，并保持的对称正定性，则一定逼近海森矩阵的逆矩阵。,在于计