• 虽然阻尼牛顿法有上述缺点，但在特定条件下它具有 收敛最快的优点，可为其他算法提供思路和理论依据。
•把
•看作一个搜索方向，
•称其为牛顿方向，则阻尼牛顿法的迭代公式为：
•——阻尼因子，即沿牛顿方向进行一维搜索的最佳步长， •可通过如下极小化过程求得：
•（2）阻尼牛顿法的计算步骤
•1）给定初始点 ，收敛精度 ，置 •2）计算
•3）求
•4）检查收敛精度。若
•，则
，停机；
•否则置
•返回到2），继续进行搜索。
• 搜索方向取该点的负梯度方向即 数值在该点附近的范围内下降最快。
，使函
•2、最速下降法的原理
•（1）使
，按此规律不断走步，形成迭代算法：
•（2）其步长因子 取一维搜索的最佳步长，即
• 根据一元函数极值的必要条件和多元复合函数求导 公式，得
•或
• 由此可知，在最速下降 法中，相邻两个迭代点上 的函数梯度相互垂直。而 搜索方向就是负梯度方向 ，因此相邻两个搜索方向 互相垂直。这就是说在迭 代点向函数极小点靠近的 过程，走的是曲折的路线 ，形成“之”字形的锯齿现 象，而且越接近极小点锯 齿越细。
•解法2：引入变化
•，则目标函数
•变为
•
•，
•经过坐标（尺度）变化后，只需要经过一次迭代，就可找 到最优解：
•不同等值线的迭代过程
•讨论
• 可以看出二者的对角形矩阵不同，前者的 等值线为一族椭圆，后者的等值线为一族同 心圆，这说明对角形矩阵是表示度量的矩阵 或者是表示尺度的矩阵，最速下降法的收敛 速度和变量的尺度有很大关系。
机械优化设计_第四章无 约束优化方法
2020年5月31日星期日
• 实际中的工程问题大都是在一定限制条件下追 求某一指标为最小，属于约束优化问题。
• 为什么要研究无约束优化问题？
•1）有些实际问题，其数学模型本身就是一个无约束问题；
•2）通过熟悉它的解法可以为研究约束优化问题打下良好的 基础；
•3）约束优化问题的求解可用通过一系列无约束优化方法来 达到。
•（3）阻尼牛顿法的
•
程序框图
•方法特点：
•1）初始点应选在极小点附近，有一定难度；
•2）尽管每次迭代都不会是函数上升，但不能保证每次 都下降；
•3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不 能构造牛顿法方向；
•4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计 算量和存储量大。此外对于二阶不可微函数也不适用。
•所以无约束优化问题的解法是优化设计方法的基本 组成部分，也是优化方法的基础。
•一、概述
•1、无约束优化问题
•求 维设计变量
使目标函数
•，而对 没有任何限制条件。
•2、求解方法 •（1）利用极值条件来确定极值点的位置。
•（2）数值计算方法——搜索方法 •基本思想：从给定的初始点 出发，沿某一搜索方向
•对于多元函数 •，设 •为 •极小点 •的第一 •个近似点， •泰勒展开，保留到二次项，得:
•设 •为 •的极小点，它作为 •极小点 •的下一个近似点，根据极值必要条件：
•即
•---多元函数求极值 的牛顿法迭代公式。
•——•海赛矩阵
•对于二次函数，海赛矩阵是常矩阵，故从任何点出发，确定最佳步长 •使函数值沿 •下降
•最大。依此方式不断进行，形成迭代的下降算法：
•3、算法框图
•4、无约束优化方法的分 类
•搜索方向的构成问题是无约束优化方法的关键。 •根据确定其搜索方向 方法不同，可分为：
•（1）只利用目标函数值的无约束优化方法（或称直接法， 即不使用导数信息），如：坐标轮换法、单形替换法及鲍威 （Powell）法。 • 直接法不必求函数导数，只计算目标函数值。适用于求 解变量个数较少（小于20）的问题，一般情况下效率较低。
•（4）梯度法的收敛速度与目标函数的性质密切相关 。对于等值线（面）为同心圆（球）的目标函数，一 次搜索即可达到极小点。
•三、牛顿型方法
•基本思想：在 领域内用一个二次函数 来近似
代替原目标函数，并将 的极小值作为目标函数 求优的下一个迭代点 。经多次迭代，使之逼近目标 函数 的极小点。
•1、牛顿法
•最 速 下 降 法 的 程 序 框 图
•例：求目标函数
•解法1：取初始点
•及梯度分别为：
•的极小点
•，则初始点处的函数值
•为一维搜索最佳步长，应满足极值必要条件
•则第一次迭代设计点位置和函数值
•经过10次迭代后，得到最优解： • 该问题的目标函数的等值线为一族椭圆，迭 代点走的是一段锯齿形路线。
•最速下降法的搜索路 径
•函数梯度为局部性质，因此并非“最快”。
•梯度法的迭代历程
•方法特点
•1）初始点可任选，每次迭代计算量小，存储量 少，程序简短。即使从一个不好的初始点出发， 开始的几步迭代，目标函数值下降很快，然后慢 慢逼近局部极小点；
•2）任意相邻两点的搜索方向是正交的，它的迭 代路径为绕道逼近极小点。当迭代点接近极小点 时，步长变得很小，越走越慢。
•3、最速下降法收敛速度的估计式
•—— •的海赛矩阵最大特征值上界 •—— •的海赛矩阵最小特征值下界
•梯度法的特点：
•（1）理论明确，程序简单，对初始点要求不严格；
•（2）对一般函数而言，梯度法的收敛速度并不快， 因为最速下降法仅仅是指某点的一个局部性质；
•（3）梯度法相邻两次搜索方向的正交性决定了迭代 全过程的搜索路径呈锯齿形，在远离极小点时逼近速 度较快，而在接近极小点时逼近速度较慢；
•例:•用牛顿法求
•解：取初始点
•，则
的极小值
•代入牛顿法迭代公式可得:
•从而经过一次迭代即求得极小点和函数极小值。
•2、阻尼牛顿法
• 在牛顿法中，迭代点的位置是按照极值条件确定，并 未含有沿下降方向搜寻的概念，因此采用牛顿迭代公式， 对于非二次函数，有时会使函数值上升。
•（1）阻尼牛顿法的迭代公式
•（2）利用目标函数的一阶或二阶导数的无约束优化方法 （或称间接法）如：最速下降法（梯度法）、共轭梯度法 、牛顿法及变尺度法； • 间接法除了要计算目标函数值外，还要计算目标函数 的梯度，有的还要计算其海赛矩阵；
•二、最速下降法（梯度法）
•1、基本思想
• 函数的负梯度方向是函数值在该点下降最快的方向。 将n维问题转化为一系列沿负梯度方向用一维搜索方法寻 优的问题，即利用负梯度作为搜索方向，故称为最速下降 法或梯度法。