当初始矩阵H0选为对称正定矩阵时，DFP算法将保证 以后的迭代矩阵Hk都是对称正定的，从而保证算法总 是下降的。这种算法用于高维问题（如20个变量以 上），收敛速度快，效果好。DFP算法是戴维登 (Davidon)于1959年提出的，后来由弗来彻(Fletcher)和 鲍威尔(Powell)于1963年作了改进，故用三人名字的字 头命名。
五章 无约束优化方法
为了使变尺度矩阵Hk确实与Gk-1 近似，并具有容易计算 的特点，必须对Hk附加某些条件。 1)为保证迭代公式具有下降性质，要求{Hk}中的每一个矩 阵都是对称正定的。 2)要求Hk之间的迭代具有简单的形式。 其中Ek为校正矩阵。上式称作校正公式。 3)要求{Hk}必须满足拟牛顿条件。 所谓拟牛顿条件，可由下面的推导给出。当f(x)为具有 正定矩阵G的二次函数时，根据泰勒展开可得
五章 无约束优化方法
无约束优化方法的分类
开始
一类是利用目标函数的一阶 或二阶导数的无约束优化方 法
最速下降法、共轭梯度法、牛 顿法及变尺度法等。
给定 x d 的初始值
计算 a * 使 f (x + ad )最小
另一类是只利用目标函数 值的无约束优化方法
坐标轮换法，单形替换法 及鲍威尔（Powell）法等。
x = [x 1, x 2 , L , x n ]T 使 f (x ) ® min
对于无约束优化问题的求解，可以直接就用第三章讲 述的极值条件来确定极值点位置。这就是把求函数极 值的问题变成求解方程
?f 0
数值求解
x k + 1 = x k + a k d k (k = 0,1, 2, L )
各种无约束优化方法的区别就在于确定其搜索方向的 方法不同。
每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象 保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求 原来的牛顿法就相当于阻尼牛顿法的步长因子取成固定值1的情况
五章 无约束优化方法
阻尼牛顿法的计算步骤
(1)给定初始点x0，收敛精度ε，置k=0 (2)计算∇f(xk), ∇2f(xk), [∇2f(xk)]-1和dk=-[∇2f(xk)]-1 ×∇f(xk) (3)求xk+1＝xk+akdk，其中ak为沿dk进行一维搜索的最佳 步长 (4)检查收敛精度。若‖xk+1－xk‖≤ε，则x*=xk+1，否则， 置k=k+1，返回到2继续进行搜索。
由于最速下降法是以负梯度方向作为搜索方向，所以 最速下降法又称为梯度法 梯度法 问题转化为求最佳步长因子的一维搜索问题
f (x k + 1 ) = f (x k - ak ? f (x k )) min f (x k - a ? f (x k ))
a
min j (a )
a
五章 无约束优化方法
局部收敛最快， 局部收敛最快，整体上并不是最快
如针对最速下降法(梯度法) 提出只用梯度信息，但比最速下降 法收敛速度快的共轭梯度法； 针对牛顿法提出变尺度法等
五章 无约束优化方法
共轭方向和共轭方向法
共轭方向的概念
研究二次函数：
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
共轭梯度法
五章 无约束优化方法
五章 无约束优化方法
是
x ? x
a *d
否 满足收敛条 件？ 给定新的 d
结束
图 10 无约束极小化算法的粗框图
五章 无约束优化方法
最速下降法（一）
目标函数值f(x) →min 从某点x出发，其搜索方向dk取该点的负梯度方向 负梯度方向(最速 负梯度方向 下降方向) ，使函数值在该点附近的范围内下降最快
x k + 1 = x k - ak ? f (x k ) k 0,1, 2, L
五章 无约束优化方法
阻尼牛顿法
将 阻尼牛顿法的迭代公式为
看作是搜索方向，称其为牛顿方向
ak—沿牛顿方向的一维最佳搜索步长，可称为阻尼因子
ak可通过一维搜索的极小化过程求得 f (x k + 1 ) = f (x k + ak dk ) = min f (x k + adk )
a
ak 取为固定值1时，阻尼牛顿法就成为了牛顿法
五章 无约束优化方法
因为具有正定海赛矩阵Gk+l的一般函数，在极小点附近 可用二次函数很好地近似，所以我们就联想到如果迫 使Hk+l满足类似于上式的关系 把上面的关系系式称作拟牛顿条件，记
则拟牛顿条件可写成
五章 无约束优化方法
三、变尺度法的一般步骤
对于校正矩阵Ek，可由具体的公式来计算，不同的公式对应不同的变尺度 法。但不论哪种变尺度法， Ek 必须满足拟牛顿条件
五章 无约束优化方法
阻尼牛顿法的程序框图
给定x0，ε k=0
dk=-[∇2f(xk)]-1∇f(xk)
xk+1=xk+akdk ak=minf(xk+akdk)
k=k+1
‖xk+1-xk‖≤ε x*=xk+1
结束
五章 无约束优化方法
牛顿型方法的特点
牛顿法和阻尼牛顿法统称为牛顿型方法 主要缺点 每次迭代都要计算函数的二阶导数矩阵，并对该矩 阵求逆。这样工作量很大。特别是矩阵求逆，当维 当维 数高时工作量更大 从计算机存储方面考虑，牛顿型方法所需的存储量 也是很大的 最速下降法的收敛速度比牛顿法慢， 最速下降法的收敛速度比牛顿法慢，而牛顿法又存在 上述缺点。针对这些缺点， 上述缺点。针对这些缺点，近年来人们研究了很多改 进的算法
五章 无约束优化方法
二、变尺度矩阵的建立
对于一般函数f(x)，当用牛顿法寻求极小点时，其牛顿 迭代公式为
为了避免在迭代公式中计算海赛矩阵的逆阵Gk-1，可用 在迭代中逐步建立的变尺度矩阵 来替换Gk-1， 即构造一个矩阵序列{Hk}来逼近海赛逆矩阵序列Gk-1 。 每迭代一次，尺度就改变一次，这正是“变尺度”的含 义。则
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
第六节 变尺度法
变量的尺度变换是放大或缩小各个坐标。通过尺度变 换可以把函数的偏心程度降低到最低限度。尺度变换 技巧能显著地改进几乎所有极小化方法的收敛性质。 对于一般二次函数: 如果进行尺度变换: 则在新的坐标系中，函数f(x)的二次项变为:
取初始点为x0=[2,2]T
则初始点处的函数梯度、海赛矩阵及其逆阵分别是
代入牛顿法迭代公式
五章 无约束优化方法
阻尼牛顿法
从牛顿法迭代公式的推演中可以看到，迭代点 的位置是按照极值条件确定的，其中并未含有 沿下降方向搜寻的概念 对于非二次函数，如果采用上述牛顿迭代公式， 有时会使函数值上升，即出现f(xk+1)>f(xk)的现 象 需对上述牛顿法进行改进，引入数学规划法的 搜索概念，提出所谓“阻尼牛顿法”
五章 无约束优化方法
五章 无约束优化方法
四、DFP算法
在变尺度法中，校正矩阵Ek取不同的形式，就形成不同 的变尺度法。DFP算法中的校正矩阵Ek取下列形式： 根据校正矩阵Ek要满足拟牛顿条件
满足上面方程的待定向量uk和vk有多种取法，这里取 取 从而可得DFP算法的校正公式
五章 无约束优化方法
从而完成了最速下降法的第一次迭代。继续下去，
该问题的目标函数f(x)的等值 线为一族椭圆，迭代点从x0走 的是一段锯齿路线。
五章 无约束优化方法
最速下降算法的程序框图
给定x0, ε k=0
dk=-∇f(xk)
xk+1=xk+akdk ak=minf(xk+akdk)
k=k+1
是 x*=xk+1 ‖xk+1－xk‖＜ε
无约束优化方法
概述 最速下降法 牛顿型方法
五章 无约束优化方法
概述
有些实际问题，其数学模型本身就是一 个无约束优化问题可以按无约束问题来 处理 通过熟悉无约束优化问题的解法可以为 研究约束优化问题打下良好的基础 约束优化问题的求解可以通过一系列无 约束优化方法来达到
五章 无约束优化方法
概述
无约束优化问题
五章 无约束优化方法
牛顿型方法
一维搜索的牛顿方法的迭代公式
对于多元函数f(x)，设xk为其极小点x*附近的一个近似点，在xk处 进行泰勒展开，保留到二次项
极值必要条件
二次收敛
这就是多元函数求极值的牛顿法迭代公式。 这就是多元函数求极值
牛顿法例题
用牛顿法求f(x1,x2)=x12+25x22的极小值
例题：用DFP算法求目标函数的极值解。
1)取初始点x0=[1 1]T，为了按DFP法构造第一次搜寻方向 d0，需计算初始点处的梯度
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
五章 无约束优化方法
梯度为零向量，海赛矩阵正定。可见x2点满足极值充 要条件，因此x2 为极小点。此函数的极值解为
五章 无约束优化方法
五章 无约束优化方法
例题
求目标函数f(x)=x12+25x22的极小值
取初始点x0=[2,2]T 初始点处函数值及梯度分别为 f (x 0 ) = 104
沿负梯度方向搜索
五章 无约束优化方法
a0为一维搜索最佳佳步长，应满足极值必要条件
从而算出一维搜索最佳步长及第一次迭代设计点 位置和函数值
五章 无约束优化方法
若矩阵G是正定的, 则总存在矩阵Q使: , 将函数偏心度变为零。 用Q-1右乘等式两边，得 , 再用Q左乘等式两边， 得