DFP变尺度法例题终结版

格式：ppt
大小：393.00 KB
文档页数：1

下载文档原格式

/ 1

点云对齐——精选推荐

点云对齐杨成林∗2009年5月31日进行数据采集时，由于受到测量设备和坏境的限制，物体表面完整测量数据的获得往往需要通过多次测量完成。

由于每次测量得到的点云数据往往只覆盖物体部分表面，并且可能出现平移错位和旋转错位，因此为了得到物体完整表面的点云数据，需要对这些局部点云数据进行对齐。

点云的对齐所用的方法可分为两种，一种是依靠测量设备进行对齐，另一种则是根据测量后的数据处理对齐。

第一种方法通过特定的设备测量待测工件或测量传感器在多次测量中的位姿。

通过测得的位姿来对齐多次测量数据。

这一方法快速方便，不需后续处理，不过需要额外的设备，而且不能完全满足测量视角的要求。

第二种方法利用测量得到的数据进行对齐，不受设备的约束，测量视角的选择可以更加自由，不过有时计算量很大，而且会因为局部最优等问题得不到正确的对齐。

本文主要讨论后一种对齐方式。

1ICP方法对于两个点集:作为对齐基准的点集P={p1,p2,...,p n}和待对齐的点集X={x1,x2,...,x m}，两个点云的对齐是使以下目标函数的值最小f(R,t)=mi=1||Rx i+t−y i||22(1)其中R和t分别是旋转矩阵和平移向量，而y i是点x i经过变换后的对应点。

此公式中，对应点可以有多种定义方法，比如规定y i为点x i在P中的最近点。

点云对齐问题的难点在于：y i是R和t的函数，事先无法确定，而∗*****************1且对应点的求取通常是计算量很大的工作。

在对应点是最近点的情况，原始的方法计算复杂度为O(mn)，常用的改进方法kd-tree方法计算复杂度在最好的情况下为O(m log n)。

在点集中点数很多的情况下，计算上的消耗是很大的，所以目标函数求值是计算量很大的工作。

虽然对于一般的最优化问题，减少目标函数的计算次数也是一个重要的目标，但在点云对齐问题中，减少目标函数的计算显得尤为重要。

为了解决这一问题，对齐问题的处理通常分为初始对齐和精确对齐两步。

(05)第四章-无约束优化方法(梯度法-牛顿法和变尺度法)

第四章
第四章
无约束优化问题标准形式：
无约束优化问题标准形式：
§
§
§
§
§
§
图最速下降法的收敛过程
αα
2
2
例4－1 求目标函数
取初始点
[2,2]
=
x
例4－2 求目标函数解取初始点[2,2]
=x
算出一维搜索最佳步长
§
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
梯度法的特点
x
给定0,ε
一般迭代式：
§4.3
§4.3
§4.3
§4.3
α0
d 0
x
x 1
x*
1
α1d 1
1()
f −∇x d 1
4-4 共轭方向法
假设目标函数f (x ) 在极值点附近的二次近似函数为
沿某个下降方向
如果能够选定这样的搜索方向，那么对于二
α
0d0
x0x1x*
1
α
1
d1
1
()
f
−∇x d
1。

2014第2章优化设计-2

X ( k 1) X ( k ) ( k ) [ H ( X ( k ) )]1f ( X ( k ) )
式中，步长因子 ( k ) 又称阻尼因子。
（2-46）
阻尼（修正）牛顿法特点：
（1）阻尼牛顿法保持了牛顿法收敛快的特点，且对
初始点无特别要求。虽然计算量多了一些，但实用性更好
4.4.2 牛顿法
S
(k )
[ H ( X
(k )
)] f ( X
1
(k )
)
(2-45)
4.4.2 牛顿法
X ( k 1) X ( k ) [ H ( X ( k ) )]1 f ( X ( k ) )
S ( k ) [ H ( X ( k ) )]1 f ( X ( k ) )
迭代开始（k＝0）规定： A( 0) I 。利用上式求得的校正矩代入式(2-54)，可得到变尺度矩阵的DFP递推公式：
A( k 1)
(k) X A g g A A( k ) (k ) T (k ) (k ) T (k) (k ) X g g A g
4.4.2 牛顿法
上式就是原始牛顿法的迭代公式。
由上式 (2-44)(可知，牛顿法的搜索方向 ( k 1) k) ( k ) 1 (k ) 为
X
X
[H ( X
)] f ( X
(k ) 1
)
S
(k )
[ H ( X
)] f ( X
(k )
)
(2-45)
牛顿法的迭代步长恒取1
4.4.2 牛顿法
X ( k 1) X ( k ) ( k ) [ H ( X ( k ) )]1f ( X ( k ) )

第七节变尺度法

5）检查迭代次数，若k=n(完成一轮迭代仍未能满足精度要求)，则令 = 进行下一轮迭代计算；若k n,则进行下一步；
6）构造新的迭代方向
五、DFP法的特点
1）DFP法具有牛顿法的二阶收敛速度，因变尺度矩阵最终逼近。
2）对任意给定的初始点，都具有最速下降方向 =-▽f( )。这是由于初始变尺度矩阵 =I(单位阵)，所以搜索方向 =- ▽f( )=-▽f( )。
3）每次搜产生的方向都是共轭的。
4）计算公式具有递推性，便于迭代。只要给出，，即可往下计算。
5）计算方便，无需计算二阶导数矩阵及其逆矩阵。
六、BFGS法
本章学习要点
1）首先要抓住并理解各种优化方法的基本思想、具体的迭代步骤，读懂计算程序框图；其次是较复杂的数学推导。对于工程技术人员来说，主要是应用。因此，对每种优化方法书中都有较简单的数学模型的例题，用手算的迭代过程，读者将例题与计算程序框图结合起来，认真地阅读理解。有条件最好再上机运算，在实践中进一步理解每种优化方法的迭代逻辑。
一、基本思想
二、构造变尺度矩阵的基本要求
三、校正矩阵 de推导
四、变尺度法的迭代步骤
1）给定初始点、收敛精度ε和维数n;
2）置k=0, = =I（n×n阶单位阵），计算梯度 =▽f( ),搜索方向 =- ▽f( )=- ；
3）进行一维搜索求最优步长因子，迭代点：
minf( + = +
4）收敛精度判断
第七节
变尺度法是在克服了梯度法收敛速度慢和牛顿法计算量、存储量大的特点基础上而发展起来的，被公认为是求解无约束优化问题最有效的算法之一，现已在工程优化设计中得到了广泛的应用。变尺度法的种类较多，这里只介绍其中最常用的两种方法：DFP法和BFGS法。DFP变尺度法先由戴维顿（Davidon）于1959年提出，后经费莱彻（Fletcher）和鲍威尔（Powell）于1963年改进而来，故又称DFP法。

第四节无约束--DFP变尺度法6

2.6、DFP变尺度法：变尺度法是Davidon 由于1959年提出后又经Fletcher和Powell加以发展和完善了后的一种变尺度法，故称DFP变尺度法
1、基本思想：变尺度法是克服了梯度法收敛慢和牛顿法计算量大的缺点而发展起来的，是求解无约束问题最有效的算法，在工程优化设计中得到了广泛的应用。利用牛顿法的迭代公式，然后并不是直接计算 [ H ( x )] 而是用一个对称正定矩阵 G( x )近似 (k ) 地代替 [ H ( x )] , G( x ) 在迭代过程中不断改进。
⑥检查迭代次数若若 k n 则转(7)
( k 1)
k n
置
( k 1)
x
x
则转(2)
(k )
⑦计算
f ( x
( k 1)
)g
(k )
( k 1)
g
g
(k )
g
(k )
(k )
x
x
x
E
(k )
G
(k )
E
(k )
G
( k 1)
然后置 k 1 k转(3) G
说明: 已有文献证明：对于二次函数 f ( x)DFP 变尺度法所构成的搜索方向 S S S S 为一组关于海色矩阵共轭的矢量。所以DFP变尺度法属于共轭方向法，具有二次收敛性,在任意情况下，这样方法对于二次目标函数都将在几步内搜索到目标函数的最优点，而是最后的构造矩阵必等于海色矩阵.
0 1
计算 x
点的导数值
S
( 0)
( 0)
g
( 0)
f ( x
( 0)
8(8 5) 24 ) 2(9 6) 6

DPF变尺度法理论证明

( j)
H k +1 Ap
( j)
( j)
= H k Ap
(k )
( j)
+
p p p p( j )
(k )
( k )T
Ap
(k )
( j)
( k )T
q
−
Hkq q q
( k ) ( k )T ( k )T
H k q( k )
=p
−
Hkq
( Ap
(k ) T (k )
)
q
( k )T
Hkq
= p( j )
(k ) ( k )T (k )
∆x ∆x H k ∆g ∆g H k H k +1 = H k + ( k ) T ( k ) − ( k )T (k ) ∆x ∆g ∆g H k ∆g
(k ) ( k )T (k ) ( k )T
p p H k q q H k (k ) H k +1q = H k + ( k )T ( k ) − ( k )T q (k ) p q q Hkq ( k ) ( k )T ( k ) ( k ) ( k )T (k ) p p q Hkq q Hkq (k ) =H k q + − =p ( k ) ( k )T ( k ) ( k )T (k ) p q q Hkq
( i )T
p
( k )T
Ap
( j)
= λk d
( k )T
Ap
( j)
= −λk ( H k g k ) Ap
T
( j)
T T T = −λk g k H k Ap ( j ) = −λk g k p ( j ) = −λk λ j g k d ( j ) = 0.

梯度法

A1=A0+△A0 推广到一般的k+1次构造矩阵
Ak+1=Ak+△Ak
矩阵序列的基本迭代式
△Ak称为校正矩阵
拟牛顿条件
设F（x）为一般形式n阶的目标函数，并具有连续的一、二阶偏导。在点处的二次泰勒近似展开
该近似二次函数的梯度是
沿g(k)方向一维搜索，
求最优步长(k)。
x(k+1)= x(k)- (k) g(k)
出口
例 8-4 用最速下降法求解下列问题
min f (x) 2x12 x22 ，
给定初始点 x(1) (1, 1)T , 1 ．
10
解目标函数 f (x) 的梯度及 x(1) 处的最速下降方向为
f(xk+1)
>
阻尼牛顿法
对原始牛顿法的改进
为解决原始牛顿法的不足，加入搜索步长(k)
因此，迭代公式变为：
x (k+1) = x (k) - (k) Hk-1gk 这就是阻尼牛顿法的迭代公式，最优步长(k)也称
为阻尼因子，是沿牛顿方向一维搜索得到的最优步长。
牛顿法算法步骤
⑴任选初始点，给定精度ε，置k←0 ⑵计算点的梯度矢量及其模
(x)=
x (k)
gk+
Hkx=0
得 x (k+1) = x (k) - Hk-1gk
即牛顿法迭代公式，方向- Hk-1gk称为牛顿方向
三、原始牛顿法的特点
若用原始牛顿法求某二次目标函数的最优解，则构造的逼近函数与原目标函数是完全相同的二次式，其等值线完全重合，故从任一点出发，一定可以一次达到目标函数的极小点。
二、确k定的方确法定自学，不作要求。记住

(完整版)机械优化设计习题参考答案孙靖民第四版机械优化设计

1.Fibonacci法—理想方法，不常用。
2.黄金分割法（0.618法）
原理：提高搜索效率：1）每次只插一个值，利用一个前次的插值；2）每次的缩短率λ相同。左右对称。
程序：p52
（四）插值方法
1.抛物线法
原理：任意插3点：
算得：；；
要求：
设函数用经过3点的抛物线代替，有
解线代数方程
解得：
程序框图p57
网格法，缩小区间，继续搜索。
Monte Carlo方法，，随机数。
比较各次得到的得解
遗传算法(专题)
（二）区间消去法（凸函数）
1.搜索区间的确定：高—低--高（）则区间内有极值。
2.区间消去法原理：在区间[a, b]内插两个点a1, b1保留有极值点区间，消去多余区间。
缩短率：
（三）0.618法
可行方向—约束允许的、函数减小的方向。（图）约束边界的切线与函数等高线的切线方向形成的区域。
数学模型
用内点法或混合法，取，
直接方法
（一）随机方向法
1.在可行域产生一个初始点，因（约束），则
--（0，1）的随机数。
2.找k个随机方向，每个方向有n个方向余弦，要产生kn个随机数，，，随机方向的单位向量为
3.取一试验步长，计算每个方向的最优点
4.找出可行域中的最好点得搜索方向。以为起点，为搜索方向得。最优点必须在可行域内或边界上，为此要逐步增加步长。
得
穷举下去得递推公式
3.算例
p73
4.框图p72
5.特点
作业：1. 2.
（六）变尺度法
1.引言
坐标变换
二次函数
令为尺度变换矩阵

最优化计算方法(工程优化)第4章

f (x*) 0, 2 f x 正定，则 x 为 f (x) 的严格局部极小
点。
如果 2 f x 负定，则 x 为 f (x) 的严格局部极大点。
无约束优化的最优性条件----凸优化的一阶条件
定理(一阶充要条件)
设 f : Rn R 是凸函数且在 x 处连续可微，则 x 为 f (x)的全局极小点的充要条件是 f (x*) 0.
f (x p) f (x)+f (x)T p o( )
P是什么方向时，函数值 f (x p) 下降最快？也就是
p是什么方向时，f (x)T p 取得最小值？
f (x)T p f (x) p cos(f (x), p)
当 cos(f (x), p) 1 时，f (x)T p 最小，最小值为
令 f x 0, 即：
利用一阶条件求驻点
利用二阶条件判断驻点是否是极小点
x12 1 0
x22
2x2
0
得到驻点： 1 1 1 1
x1
0 ,
x2
2 ,
x3
0
,
x4
2
.
无约束优化的最优性条件
函数 f x 的Hesse阵：
2
f
x
2x1
0
0
2
x2
2
利用二阶条件判断驻点是否是极小点
2 0
0 2
的行列式小于0；
x1, x4是鞍点；
2
f
x2
2 0
0
2
是正定矩阵；
x2 是极小点；
2
f
x3
2 0
0 2
是负定矩阵；
x3 是极大点。
• 对某些较简单的函数，这样做有时是可行的；