05 第五章 无约束优化方法.ppt

第1页：第四章 无约束优化方法概述

从第一章列举的机械设计问题可以看出，大多数实际问题是约束优化问题。约束优化问题的求解是转化为一系列的无约束优化问题实现的，因此无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。

第2页：无约束优化方法的分类

解析法在数学模型复杂时不便求解，数值法可以处理复杂函数及没有数学表达式的优化设计问题。搜索方向问题是无约束优化方法的关键，各种方法的区别在于确定搜索方向的方法不同。

第3页：

第4页：最速下降法

第二节 最速下降法：优化设计追求目标函数值最小，若搜索方向取该点的负梯度方向，可使函数值在该点附近的范围内下降最快。按此规律不断走步，形成迭代算法，故称最速下降法或梯度法。搜索方向确定为负梯度方向后，还需确定步长因子，即求一维搜索的最佳步长。

第5页：最速下降法的锯齿现象

由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直；而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直，迭代路径呈锯齿状。

第6页：

第7页：例4-1 求目标函数极小点

例4-1：求目标函数的极小点，演示最速下降法的迭代计算过程。

第8页：

第9页：多元函数的牛顿型方法

第三节 牛顿型方法：对于多元函数作泰勒展开，设其为函数的极小点，根据极值的必要条件即可导出多元函数的牛顿法迭代公式。

第10页：牛顿法迭代公式与阻尼牛顿法

上式即多元函数求极值的牛顿法迭代公式。

例4-2：用牛顿法求函数的极小值。对牛顿法进行改进，提出阻尼牛顿法。

第11页：

第12页：共轭方向的概念

第四节 共轭方向及共轭方向法：为了克服最速下降法的锯齿现象、提高收敛速度，发展了一类共轭方向法，其搜索方向是共轭方向。共轭方向的概念是在研究二次函数时引出的，首先考虑二维情况。

第13页：共轭方向的作用

如果按最速下降法选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，则对于二元二次函数只需进行两次直线搜索就可以求到极小点。

第14页：共轭方向的判定条件

该搜索方向应满足什么条件？对于二次函数在极小点处取得极值的必要条件，等式两边同乘后即得方向之间应满足的条件——两搜索方向对 G 共轭。

第15页：共轭方向法的基本步骤

三、共轭方向法步骤：

1. 选定初始点、下降方向和收敛精度 ε，k=0
2. 沿方向进行一维搜索，得新点
3. 判断是否满足收敛精度，若满足则打印结果，否则转第 4 步
4. 提供新的共轭方向
5. 置 k=k+1，转第 2 步

第16页：

第17页：共轭梯度法

第五节 共轭梯度法：共轭梯度法是共轭方向法的一种，共轭向量由迭代点的负梯度构造出来，所以称共轭梯度法。从点出发，沿 G 的某一共轭方向作一维搜索到达新点，而在两点的梯度之间存在确定关系。

第18页：共轭方向与梯度的关系

由此得出共轭方向与梯度之间的关系：沿方向进行一维搜索，其终点与始点的梯度值差与该共轭方向正交。

第19页：共轭梯度法的几何说明

本页为共轭梯度法的几何说明（图4-9），以二维等高线展示沿共轭方向进行两次一维搜索即达极小点的搜索路线。

第20页：

第21页：变尺度法的基本思想

第六节 变尺度法的基本思想：前面讨论的梯度法和牛顿法，它们的迭代公式可以看作下列公式的特例。变尺度法是对牛顿法的修正，它不是计算二阶导数的矩阵和它的逆矩阵，而是设法构造一个对称正定矩阵 H 来代替 Hesse 矩阵的逆矩阵，并在迭代过程中使其逐渐逼近 H⁻¹。由于 H 在迭代过程中不断修正改变，对梯度起到改变尺度的作用，故称变尺度矩阵。

第22页：尺度矩阵的概念

一、尺度矩阵的概念：变量的尺度变换是放大或缩小各个坐标，通过尺度变换可以把函数的偏心程度降低到最低限度。对于一般二次函数，如果进行尺度变换，则在新的坐标系中函数的二次项随之改变。

第23页：尺度变换与偏心度

选择这样变换的目的是降低二次项的偏心程度。若矩阵 G 是正定的，则总存在矩阵 Q 使函数偏心度变为零；用 Q⁻¹ 右乘等式两边，再用 Q 左乘等式两边，即得相应关系。

第24页：牛顿方向与变尺度法步骤

二次函数矩阵 G 的逆矩阵可以通过尺度变换矩阵 Q 求得，这样牛顿法迭代过程中的牛顿方向可写成相应形式。本页并给出三、变尺度法的一般步骤。

第25页：

第26页：坐标轮换法

第七节 坐标轮换法：坐标轮换法是每次搜索只允许一个变量变化、其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法，又称变量轮换法。它把多变量的优化问题轮流地转化成单变量的优化问题：先将 (n-1) 个变量固定不动，只对第一个变量进行一维搜索得到最优点，再依次对其余变量搜索。

第27页：

第28页：坐标轮换法原理图

本页为坐标轮换法原理图（图4-12，动画演示），展示沿各坐标方向轮流搜索的折线路径。

第29页：坐标轮换法的搜索方向

2. 搜索方向与步长的确定 ——（1）搜索方向的确定：对于第 k 轮第 i 次的计算，该次迭代方向轮流取 n 维坐标的单位向量。

第30页：搜索步长的确定

3. 搜索步长的确定：关于步长通常有以下几种取法：

• （1）加速步长法
• （2）最优步长法：利用一维最优搜索方法完成每一次迭代，此时可以采用 0.618 方法或二次插值方法来计算步长。

第31页：加速步长法的搜索路线

本页为加速步长法的搜索路线图（图4-13），展示按固定步长试探、成功后加大步长的搜索路径。

第32页：最优步长法的搜索路线

本页为最优步长法的搜索路线图（图4-14），展示每轮沿坐标方向作一维最优搜索的收敛路径。

第33页：坐标轮换法存在的问题

4. 坐标轮换法存在的问题（图4-15）：在各种不同情况下的效能差别很大——（a）搜索有效；（b）搜索低效；（c）搜索无效。

第34页：Powell法（方向加速法）

第八节 Powell法（方向加速法）：Powell 法是利用共轭方向可以加速收敛的性质所形成的一种搜索算法。本页介绍一、共轭方向的生成。

第35页：

第36页：Powell法的基本算法

二、基本算法：本页给出 Powell 法（方向加速法）的基本算法步骤。

第37页：Powell法的改进算法

三、改进的算法：在鲍维尔基本算法中，每一轮迭代都用连接始点和终点所产生的搜索方向去替换原来向量组中的第一个向量，而不管它的“好坏”。改进的算法是：首先判断原向量组是否需要替换，如需要替换，再产生新的向量。

第38页：