当前位置：文档之家 › 07.第7讲 牛顿法 DFP变尺度法

07.第7讲 牛顿法 DFP变尺度法

  • 格式：ppt
  • 大小：272.50 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

约束变尺度法

约束变尺度法

约束变尺度法Newton 法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的。

因此，建议凡是Hesse 矩阵比较容易求出的问题，尽可能使用Newton 法求解。

但是，Newton 法也有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton 法的优点。

为此，人们开始寻找一种算法既可以保持Newton 法收敛速度快的优点，又可以摆脱关于Hesse 矩阵的计算，这就是变尺度算法。

变尺度法是一种非常好的方法，其中DFP 算法和BFGS 算法。

可以说，直到目前为止，在不用Hesse 矩阵的方法中是最好的算法。

一、拟Newton 法为了吸收Newton 法收敛速度快的优点，同时避免Newton 法每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，人们提出了具有超线性收敛的拟Newton 法。

（一）拟Newton 法的基本原理在Newton 法中的基本迭代公式kk k k P t X X +=+1，其中1=k t ，)()]([12kkk Xf Xf P ∇∇-=-令)()(2kkkkXf gXf G∇=∇=，于是有，，，，21011=-=-+k g G X X k k k k其中X0是初始点, gk 和 Gk 分别是目标函数f (X )在点 Xk 的梯度和Hesse 矩阵.为了消除这个迭代公式中的Hesse 逆矩阵G-1k ,可用某种近似矩阵Hk=Hk(Xk)来替换它,即构造一矩阵序列{Hk}去逼近Hesse 逆矩阵序列{G-1k}，此时kk k k g H X X -=+1事实上,式中 Pk= -Hk gk 无非是确定了第k 次迭代的搜索方向.为了取得更大的灵活性,考虑更一般的迭代公式kk k k k g H t X X -=+1其中步长tk 通过从Xk 出发沿Pk= -Hk gk 作直线搜索来确定.此式代表很广的一类迭代公式.例如,当Hk=I (单位矩阵)时,它变为最速下降法的迭代公式。

牛顿法

牛顿法

牛顿法牛顿法（英语：Newton's method）又称为牛顿-拉弗森方法（英语：Newton-Raphson method），它是一种在实数域和复数域上近似求解方程的方法。

方法使用函数的泰勒级数的前面几项来寻找方程的根。

起源：牛顿法最初由艾萨克·牛顿在《流数法》（Method of Fluxions，1671年完成，在牛顿去世后的1736年公开发表）中提出。

约瑟夫·鲍易也曾于1690年在Analysis Aequationum中提出此方法。

原理：二阶逼近牛顿法对局部凸函数找到极小值，对局部凹函数找到极大值，对局部不凸不凹函数可能找到鞍点牛顿法要求估计二阶导数。

牛顿法据称比直接计算要快了4 倍。

其中的两次迭代（第二步迭代被注释掉了）就是用的牛顿法来求解方程，也就是的根。

牛顿法的思想其实很简单，给定一个初始点，使用在该点处的切线来近似函数，然后寻找切线的根作为一次迭代。

比如对于这个例子，令，给定初始点，在该点处的导数是，由此可以得到该处的切线为，求解得到正是代码中的迭代。

当然代码的重点其实不在这里，而在0x5f3759df这个奇怪的magic number，用于得到一个好的初始点。

这个神奇的数字到底是谁发现的，根据wikipedia 上的说法似乎至今还没有定论。

xkcd 还为此画了一条漫画，讽刺说每次我们惊奇地发现工业界里不知道哪个无名人士写出了0x5f3759df之类的神奇数字，背后都有成千上万的其他无名人士我们无从知晓，说不定他们中的某一个人已经解决了P=NP 的问题，但是那人却还在调某个自动打蛋器的代码所以我们至今仍无知晓。

:D回到我们今天的话题，从这段代码中我们可以看到两点：牛顿法收敛非常快，对于精度要求不是特别高的情况，比如上面的图形学相关的计算中，甚至只用了一次计算迭代。

另一方面，初始值的选取非常重要，我们接下去将会看到，初始值选得不好有可能会直接导致算法不收敛。

变尺度法

变尺度法

以上两式相减可得
T ρT H ∆H k = ω ρT − ω ρT = 0 j j j T T T T T ρk H ∆H k = ω ρk − ρk HH k
转置可得 ∆H k Hρ j = 0 ∆H k Hρk = ω ρk − H k Hρk
∆H k Hρ j = 0 ∆H k Hρk = ω ρk − H k Hρk 设目标函数为二次型：
对于二次函数 其一阶导数为：
f ( x ) = a + bT x +
欲用迭代法求f ( x ) 的极小，令 一维搜索
1 T x cx 2 g ( x ) = b + cx
(1) ( 2) ( 3) ( 4 ) 公式推导 ( 5)
T gk ρ j = 0
( ) ( ∂f ( x ( ) ) ∂f ( x ( ) ) ∂x ( ) = = −g
i +1 i +1 i +1
x (i +1) = x ( i ) + ∆x ( i ) = x ( i ) − α i ρi
min f x ( i +1) = min f x ( i ) − α i ρi
( i +1)
)
∂α i
∂x
∂α i
T i +1 i
ρ =0
由( 2 ) 得 将 ( 6 ) 代入 ( 5 )中可得 由( 6 ) 可得
(
)
j = 0,1, 2, …, k
j = 0,1, 2, …, k − 1 ∆H k y j = 0 ( 5.52 ) k ∆H k yk = ω∆x − H k yk 此即∆H k 需满足的条件。找出满足该条件的∆H k，就能求出H k +1， 进而建立起迭代关系。 ∆H k 是否满足拟牛顿条件？即当N 次迭代完成时，在极小点附近， 搜索方向即为牛顿方向。

DFP变尺度法

DFP变尺度法
for(j=0;j<n;j++)
{
h[i][j]=0;
if(j==i) h[i][j]=1;
}
g1=g2; k=-1;
}else{
int j;
double a1=0,a2=0;
for(i=0;i<n;i++){
dg[i]=g2[i]-g1[i];
dx[i]=xk1[i]-xk[i];
}
for(i=0;i<n;i++){
if(ia==1) { aa=a[1]; *ft=f[1]; break; }
d=(pow(a[0],2)-pow(a[2],2))*(a[0]-a[1])-(pow(a[0],2)-pow(a[1],2))*(a[0]-a[2]);
if(fabs(d)==0) break;
c=((f[0]-f[2])*(a[0]-a[1])-(f[0]-f[1])*(a[0]-a[2]))/d;
ib=0;
if(ia==1) { xx=xk; break; }
ib=0;
for(i=0;i<n;i++) s[i]=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s[i]+= -h[i][j]*g1[j];
aa=lagrange(xk,ft,s);
xk1=iterate(xk,aa,s);
a[1]=(a[0]+a[2])/2;
f[1]=func(xk,a[1],s);
}
}else{
if(*ft>f[1]) {a[0]=aa;f[0]=*ft;}

最优化理论方法——牛顿法

最优化理论方法——牛顿法

牛顿法牛顿法作为求解非线性方程的一种经典的迭代方法，它的收敛速度快，有内在函数可以直接使用。

结合着matlab 可以对其进行使用，求解方程。

牛顿迭代法（Newton ’s method ）又称为牛顿-拉夫逊方法（Newton-Raphson method ）,它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法,其基本思想是利用目标函数的二次Taylor 展开，并将其极小化。

牛顿法使用函数()f x 的泰勒级数的前面几项来寻找方程()0f x =的根。

牛顿法是求方程根的重要方法之一，其最大优点是在方程()0f x =的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时非线性收敛，但是可通过一些方法变成线性收敛。

牛顿法的几何解释：方程()0f x =的根*x 可解释为曲线()y f x =与x 轴的焦点的横坐标。

如下图：设k x 是根*x 的某个近似值，过曲线()y f x =上横坐标为k x 的点k P 引切线，并将该切线与x 轴的交点 的横坐标1k x +作为*x 的新的近似值。

鉴于这种几何背景，牛顿法亦称为切线法。

2 牛顿迭代公式：（1）最速下降法：以负梯度方向作为极小化算法的下降方向，也称为梯度法。

设函数()f x 在k x 附近连续可微，且()0k k g f x =∇≠。

由泰勒展开式： ()()()()()T k k k k fx f x x x f xx x ο=+-∇+- （*）可知，若记为k k x x d α-=，则满足0T k k d g <的方向k d 是下降方向。

当α取定后，T k k d g 的值越小，即T k k d g -的值越大，函数下降的越快。

由Cauchy-Schwartz 不等式：Tk k kk d g d g ≤，故当且仅当k k d g =-时，T k k d g 最小，从而称k g -是最速下降方向。

最速下降法的迭代格式为： 1k k k k x x g α+=-。

变尺度法

变尺度法
变尺度法 (拟牛顿法)
一.尺度矩阵的引入
尺度变化可以降低函数的偏心程度（通过放大或者缩小各个坐标）
若f (x) 1 xT Gx bT x c，G是对称正定阵，则G与单位阵E合同，故存在一个 2
可逆矩阵Q, 使得QT GQ=E,即函数偏心程度为0 QT Q=G 1 xTGx 1 xTQTGQx
满足上述方程的解很多，我们可以如下确定一组解：
kukukT yk sk k vk vkT yk H k yk
这样，我们可以取：
uk sk ,
kukukT yk sk ,
vk H k yk , k vk vkT yk H k yk ;
8
即：
uk sk , vk Hk yk ,
计算H
，令
k
k

k
1，转step
3.
10
四、变尺度法算法框图：
k k1
给定x0 , H 0
, k 0
d k -H kf (xk )
一维搜索得 k xk 1 xk k d k
修正Hk
N
产生H k 1
xk1 xk
Stop y xk1 解
11
4
(1)d k


H
k
gk为下降方向，则d
k
与梯度方向成钝角，即gT k
d
k

0

gT k
H
k
gk

0,
gT k
H
k
gk

0
H k 对称正定
（3）
f
(x)

1 2
xT Gx

bT
x

07.第7讲 牛顿法 DFP变尺度法

k 1
变尺度法的迭代公式：
X
k 1
X
o
k
A f ( X )
k k k
A
k
为变尺度矩阵，在迭代过程中不断修正。
0
在初试点 X 取 A I ，则上式变为：
X
k 1
X f ( X )
k k k
k * X X 而当 时，即
Ak [ H ( X k )]1
k 1 k
X
*
X
k
f ( X k ) H(X k )
若 f ( X ) 是二次函数，则 X * 就是 f ( X ) 的极小点， 否则只是一个近似点，需进一步迭代。
牛顿法的迭代公式：
X k 1
k f ( X ) k X H(X k )
由于牛顿法迭代公式中没有步长因子 ，或者说
k
步长因子
1 f ( X ) ( X ) f ( X ) f ( X )( X X ) ( X X k ) H ( X k )( X X k ) 2 求二次近似函数 ( X ) 的极小点，即令 ( X ) 0
k k k
k f ( X ) X 在目标函数 在 点处取二阶泰勒展开：
k k k A g S 3.计算搜索方向
；
4.进行一维搜索求 ，得迭代新点
k
X S X
k k kຫໍສະໝຸດ k 15.检验是否满足迭代终止条件
f ( X
k 1
)
若满足，停止迭代，输出 X k 1 X * , f ( X k 1 ) f ( X * ) 否则转下一步；
6.检查迭代次数，若k=n，则置 X k 1 X 0 ，

dfp算法原理

dfp算法原理
DFP算法，也称为DFP校正方法，是第一个拟牛顿法，由Davidon最早提出，后经Fletcher和Powell解释和改进，在命名时以三个人名字的首字母命名。

拟牛顿法多数时候均为对二阶导hessian矩阵或其逆矩阵的近似逼近，DFP所逼近的就是hessian逆矩阵。

其算法步骤如下：
假设已知目标函数及梯度，迭代轮数n，终止条件。

取初始点，精度；计算，若则停止，得到权重；否则转3；令，；令；求，令；计算，若则停止，得到权重；否则转7；计算；计算；令，转4。

求得的X即为每个特征的权重。

一般而言，针对公式会补充一个正定的充要条件：。

但是在实际实现中，本人发现很多时候，并不一定大于0，但距离0差距很小，一般在以内，因此可以将该约束进行放松。

以上内容仅供参考，如需更专业全面的信息，建议查阅数学或算法相关的专业书籍或咨询数学领域专家。

变度量法


校正公式
DFP 法
Gk1 Gk Gk , 其中

考虑
,满足
拟Newton条 件
满足拟Newton条 件 满足对称性
？？确定
（DFP校正公式）
算法步骤
Step1:
Step2: Step3: Step4:
Step5:
Step6: Step7:
DFP 法
举例
DFP 法
用DFP算法求解：
min f x x12 2x22 2x1 x2 4x1 ,
变度量法
简介
本质上是是将最速下降法与Newton法的优点结合起来， 也称修正Newton法或拟Newton法或变尺度法.
(1) 变尺度法是1959年由Davidon、Fletcher和Powell提出的.
(2) Broyden、Goldstein、Shanno 等人于1970年进一步改进 .
基本思想
变度量法
牛顿法每次都计算 Gk 2 f ( xk ) 1.
计算量大；
当Gk非正定时, 不能保证所求方向为下降方向. 当Gk奇异时，步长可能变成无界 .
1959年,Davidon提出设想仅用每次迭代中得到的梯 度信息来近似 Gk，基于此导致了一类非常成功的 方法----变度量法.
本节介绍Broyden族拟牛顿法： DFP算法和BFGS算 法．
基本原理
变度量法
最速下降法和阻尼牛顿法的迭代公式可统一为：
思 能否构造近似于 2 f ( 的xk )G1k 使之不需要计算Hesse矩
考 阵及其拟矩阵，并能使相应的算法保持
Newton法的收敛速度快的优点，同时计算较简单?
基本思路
变度量法
构造矩阵列 Gk满 足：

dfp变尺度法

dfp变尺度法
DFP变尺度法（Davidon-Fletcher-Powell变尺度法）是一种拟牛顿优化算法，用于求解无约束极值问题它综合了梯度法和牛顿法的优点，具有较快的收敛速度和较广的应用范围DFP算法在优化领域中被认为是一种高效的方法，尤其在处理高维问题时具有显著优势。

DFP变尺度法的基本思想是在每次迭代中，用一组线性方程组来近似表示目标函数的Hessian矩阵这样，我们可以用较少的计算代价获得牛顿法类似的收敛速度变尺度法的关键在于选择合适的尺度矩阵，以保证算法的收敛性和稳定性。

DFP算法的步骤如下。

1.初始化：选择一个初始点x0.
2.计算目标函数的梯度g（x）。

f(x)=f(x0)+γ(x-x0).
其中，γ为尺度因子
3.计算Hessian矩阵的近似值H
H=I-γ²g²(x).
4.更新搜索方向。

s=-Hg(x).
5.更新x。

x=x0+αs.
其中，α为线搜索参数。

6.重复步骤2-5，直到满足终止条件（如收敛或达到迭代次数限制）。

DFP变尺度法在实际应用中通常与一维搜索技术和黄金分割法相结合，以提高收敛速度和稳定性此外，还可以根据问题特点对算法进行适当调整，如引入局部搜索、调整线搜索策略等，以适应不同问题的需求总之，DFP变尺度法是一种高效、实用的优化算法，在许多领域都得到了广泛应用。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

则为：
X
k 1
X [ H ( X )] f ( X )
k k
DFP变尺度法及其递推公式：
变尺度矩阵递推公式： A
k
k 1
A A
k
k
其中 A 为k次迭代的修正矩阵。
DFP算法的迭代修正矩阵是
X [X ] A g [g ] A A k T k k 检查迭代次数，若k=n，则置 X k 1 X 0 ，
转2；若k<n，则转7； 7.计算 X X
k k 1
X
k
k k 1 k g f ( X ) f ( X ) ，
k k k k 1 A A A A 按DFP法修正矩阵公式计算 ，
然后，置 k 1 k
k
1 ，这对非二次型目标函数，有时候
f ( X k 1 ) f ( X k ) 的情况。这
会出现函数值上升即
表明牛顿法不能保证函数值稳定下降，在严重的情况
下甚至可能造成迭代点的发散而导致计算失败，为克 服上述弊端，提出阻尼牛顿法，其迭代公式为：
X k 1 X k
k f ( X ) k H(X k )
牛顿法
基本思想： 在求目标函数 f ( X )的极小值时，先将 f ( X ) 在 X k 处附件做泰勒展开，取二次近似函数式，然 后求出这个二次函数的极小点，并将该点作为 原目标函数的近似极小点，若此值不能满足精 度要求，则以此近似极小点作为下一轮迭代的 初始点，继续上述过程，直至满足要求为止。
牛顿法的迭代公式：
X
*
X
k
f ( X k ) H(X k )
若 f ( X ) 是二次函数，则 X * 就是 f ( X ) 的极小点， 否则只是一个近似点，需进一步迭代。
牛顿法的迭代公式：
X k 1
k f ( X ) k X H(X k )
由于牛顿法迭代公式中没有步长因子 ，或者说
k
步长因子
，转3.
k 1
变尺度法的迭代公式：
X
k 1
X
o
k
A f ( X )
k k k
A
k
为变尺度矩阵，在迭代过程中不断修正。
0
在初试点 X 取 A I ，则上式变为：
X
k 1
X f ( X )
k k k
k * X X 而当 时，即
Ak [ H ( X k )]1
k 1 k
DFP变尺度法
变尺度法基本思想： 变尺度法是在克服梯度法收敛慢和牛顿法 计算量大的缺点上发展起来的。它利用牛顿法 k 1 [ H ( X )] ，而是 的迭代形式，然而不直接计算 k k 1 [ H ( X )] 。 A 用一个对称正定矩阵 近似地代替 k A 在迭代过程中不断改进，最后逼近 [H ( X )] 这种方法，省去了塞黑矩阵的计算和求逆，计 算量大为减少。
k k k A g S 3.计算搜索方向
；
4.进行一维搜索求 ，得迭代新点
k
X S X
k k k
k 1
5.检验是否满足迭代终止条件
f ( X
k 1
)
若满足，停止迭代，输出 X k 1 X * , f ( X k 1 ) f ( X * ) 否则转下一步；
k k k T k k k T
k
式中 X k X k 1 X k ，即两迭代点信息之差；
g f ( X
k k 1
) f ( X ) ，即目标函数一阶导数差
k
DFP法迭代步骤：
1.给定初始点 X o ，迭代精度
0
，维数n；
f ( X 0 ) g 0
2.置 0 k ，单位矩阵 I A ，计算
1 f ( X ) ( X ) f ( X ) f ( X )( X X ) ( X X k ) H ( X k )( X X k ) 2 求二次近似函数 ( X ) 的极小点，即令 ( X ) 0
k k k
k f ( X ) X 在目标函数 在 点处取二阶泰勒展开：
式中 ，
k 1

k
k
——阻尼因子；
S [ H ( X )] f ( X ) ——牛顿方向。
牛顿法的特点：
牛顿法不仅利用了函数的一阶导数信息， 还利用了二阶导数信息，故其收敛速度比梯 度法快得多。但牛顿法需计算塞黑矩阵及其 逆矩阵，计算量存储量都很大，且都是以维 2 数 比例增加，维数高时这个问题更加突出。 n 此外，若塞黑矩阵是奇异矩阵时，其逆矩阵 不存在，这种方法就不能使用。