重庆网站服务建设,wordpress 会员开卡消费,北京网站建设费用,广州翼讯资讯科技有限公司 网站本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等#xff0c;本系列文章篇数较多#xff0c;不定期更新#xff0c;上半部分介绍无约束优化#xff0c;… 本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等本系列文章篇数较多不定期更新上半部分介绍无约束优化下半部分介绍带约束的优化中间会穿插一些路径规划方面的应用实例 十、拟牛顿方法 1、拟牛顿方法介绍 Newton方法的缺点是在每步迭代时需计算Hesse矩阵 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk)为此要计算n(n 1)/2个二阶偏导数;若该方法产生的迭代点不能充分接近极小点 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk)的正定性不能保证。Newton方法的优点在于它具有二阶收敛的速度.这促使我们去考虑是否可以构造一种方法,它既不需要计算二阶偏导数,又具有较快的收敛速度。 假设我们要构造一个矩阵M去近似Hessian矩阵那么M应该满足什么条件 ①它应该不需要计算所有元素的二阶导 ②可以不用显式的求解线性方程组方程组应该有闭式解以便很快的解出 ③它应该不需要是满秩的所以它的存储应该是紧凑的 ④它必须保持下降方向即它必须是正定的 ⑤它应该包含曲率信息(局部二次近似)即应该逼近Hessian矩阵 – 从下图的推导可以看出当近似矩阵M是正定的矩阵时可以保证搜索方向与负梯度方向成锐角即可保证搜索方向为下降方向。 ☆☆☆注在深蓝学院课程机器人中的数值优化中用H表示Hessian矩阵用M表示Hessian矩阵的近似用B表示M的逆矩阵而在数值最优化方法高立 编著这本书中用B表示Hessian矩阵的近似而用H表示B的逆矩阵在下文的文字描述中采用数值最优化方法高立 编著这本书中的表示方法下文中的图片大部分是基于深蓝学院课程机器人中的数值优化课程中的PPT进行修改补充后而形成的采用该课程的表示方法 假定当前迭代点为 x k 1 x_{k1} xk1若我们用已得到的 x k x_{k} xk x k 1 x_{k1} xk1及其一阶导数信息 ∇ f ( x k ) \nabla f\left(x_{k}\right) ∇f(xk)和 ∇ f ( x k 1 ) \nabla f\left(x_{k1}\right) ∇f(xk1)构造一个正定矩阵 B k 1 B_{k1} Bk1作为 ∇ f 2 ( x k 1 ) \nabla f^2\left(x_{k1}\right) ∇f2(xk1)的近似这样下降方向 d k 1 d_{k1} dk1 由以下方程组给出 B k 1 d − ∇ f ( x k 1 ) {B}_{k1}d-\nabla f\left(x_{k1}\right) Bk1d−∇f(xk1) 然而这样做仍需求解一个线性方程组进一步的改进为用相同的信息构造一个矩阵 H k 1 H_{k1} Hk1作为 ∇ f 2 ( x k 1 ) − 1 \nabla f^2\left(x_{k1}\right)^{-1} ∇f2(xk1)−1的近似,这样下降方向 d k 1 d_{k1} dk1就可以由下式给出 d − H k 1 ∇ f ( x k 1 ) d-H_{k1}\nabla f\left(x_{k1}\right) d−Hk1∇f(xk1) 近似矩阵的构造应该是简单有效的,它应具有如下的条件: ①只需 f ( x ) f(x) f(x)的一阶导数信息; ② B k 1 {B}_{k1} Bk1 ( H k 1 ) (H_{k1}) (Hk1)正定,以保证方向的下降性; ③方法具有较快的收敛速度。 对梯度进行泰勒展开去掉高阶小量可得下式 ∇ f ( x k 1 ) − ∇ f ( x k ) ≈ ∇ 2 f ( x ) ∗ x k 1 − x k \nabla f\left(x_{k1}\right)-\nabla f\left(x_{k}\right) ≈ \nabla^2 f(x)*x_{k1}-x_k ∇f(xk1)−∇f(xk)≈∇2f(x)∗xk1−xk 若进行以下定义 s k x k 1 − x k , y k ∇ f ( x k 1 ) − ∇ f ( x k ) , \begin{array}{c}s_kx_{k1}-x_k,\\ \\ y_k\nabla f\left(x_{k1}\right)-\nabla f\left(x_{k}\right),\end{array} skxk1−xk,yk∇f(xk1)−∇f(xk), 则 B k 1 {B}_{k1} Bk1作为 ∇ f 2 ( x k 1 ) \nabla f^2\left(x_{k1}\right) ∇f2(xk1)的近似应该满足以下方程 B k 1 s k y k B_{k1}s_ky_k Bk1skyk 该方程称为拟Newton方程或拟Newton条件。若记 H k 1 B k 1 − 1 , H_{k1}B_{k1}^{-1}, Hk1Bk1−1,则 H k 1 H_{k1} Hk1应该满足下式 H k 1 y k s k . H_{k1}y_ks_k. Hk1yksk. 拟Newton方法是指由 B k 1 d − ∇ f ( x k 1 ) {B}_{k1}d-\nabla f\left(x_{k1}\right) Bk1d−∇f(xk1)式或者 d − H k 1 ∇ f ( x k 1 ) d-H_{k1}\nabla f\left(x_{k1}\right) d−Hk1∇f(xk1)式确定迭代方向d的最优化方法,其中的 B k 1 {B}_{k1} Bk1需满足拟 Newton条件 B k 1 s k y k B_{k1}s_ky_k Bk1skyk H k 1 {H}_{k1} Hk1需满足拟Newton条件 H k 1 y k s k H_{k1}y_ks_k Hk1yksk 下面我们给出一般拟Newton方法的结构,其算法以矩阵 H k 1 H_{k1} Hk1的迭代为例. 在上述算法中,初始矩阵H通常取为单位矩阵,这样算法的第一步迭代的迭代方向取为负梯度方向. 那么如何修正 H k {H}_{k} Hk得 H k 1 {H}_{k1} Hk1呢即如何确定在下式中的 Δ H k \Delta H_k ΔHk呢 H k 1 H k Δ H k H_{k1}H_k\Delta H_k Hk1HkΔHk Δ H k \Delta H_k ΔHk的取法是多种多样的,但它应具有简单、计算量小、有效的特点下面介绍几种重要的修正 H k H_k Hk与 B k B_k Bk的公式. 1、拟牛顿方法修正公式 1对称秩1公式SR1 对称秩1(Symmetric Rank 1,SR1)公式是由Broyden、Davidon等人独立提出的。 H k 1 S R 1 H k ( s k − H k y k ) ( s k − H k y k ) T ( s k − H k y k ) T y k , H_{k1}^{\mathrm{SR1}}H_k\dfrac{(s_k-H_ky_k)(s_k-H_ky_k)^{\mathrm{T}}}{(s_k-H_ky_k)^{\mathrm{T}}y_k}, Hk1SR1Hk(sk−Hkyk)Tyk(sk−Hkyk)(sk−Hkyk)T, B k 1 S R 1 B k ( y k − B k s k ) ( y k − B k s k ) T ( y k − B k s k ) T s k . B_{k1}^{\mathrm{SR1}}B_k\dfrac{(y_k-B_k s_k)(y_k-B_k s_k)^{\mathrm{T}}}{(y_k-B_k s_k)^{\mathrm{T}}s_k}. Bk1SR1Bk(yk−Bksk)Tsk(yk−Bksk)(yk−Bksk)T. 2DFP公式 DFP公式,或者说DFP方法,首先是由Davidon于1959年提出,后经Fletcher 和 Powell发展得到的。该方法是第一个被提出的拟 Newton方法,它为拟 Newton方法的建立与发展奠定了基础. H k 1 D F P H k s k s k T s k T y k − H k y k y k T H k y k T H k y k . H_{k1}^{\mathrm{DFP}}H_k\frac{s_k s_k^{\mathrm{T}}}{s_k^{\mathrm{T}}y_k}-\frac{H_ky_ky_k^{\mathrm{T}}H_k}{y_k^{\mathrm{T}}H_ky_k}. Hk1DFPHkskTykskskT−ykTHkykHkykykTHk. 我们称采用DFP公式来修正矩阵的拟Newton方法为DFP方法。假定 H k H_k Hk与 H k 1 H_{k1} Hk1都可逆,根据Shermann-Morrison-Woodbury 公式,由上式可以导出 B k 1 B_{k1} Bk1的修正公式 B k 1 D F P B k ( 1 s k T B k s k s k T y k ) y k y k T s k T y k − ( y k s k T B k B k s k y k T s k T y k ) . B_{k1}^{\mathrm{DFP}}B_{k}\left(1\frac{s_{k}^{\mathrm{T}}B_{k}s_{k}}{s_{k}^{\mathrm{T}}y_{k}}\right)\frac{y_{k}y_{k}^{\mathrm{T}}}{s_{k}^{\mathrm{T}}y_{k}}-\left(\frac{y_{k}s_{k}^{\mathrm{T}}B_{k}B_{k}s_{k}y_{k}^{\mathrm{T}}}{s_{k}^{\mathrm{T}}y_{k}}\right). Bk1DFPBk(1skTykskTBksk)skTykykykT−(skTykykskTBkBkskykT). 上式其实也是下面问题的解: min ∥ W − T ( B − B k ) W − 1 ∥ F , s.t. B B T , B s k y k , \begin{array}{l}\min\|W^{-\mathrm T}(B-B_k)W^{-1}\|_{\mathrm F},\\ \text{s.t.}\quad BB^{\mathrm T},B s_ky_k,\end{array} min∥W−T(B−Bk)W−1∥F,s.t.BBT,Bskyk, 其中 W ∈ R n × n W ∈R^{n×n} W∈Rn×n非奇异。 W T W B W^TWB WTWB满足拟Newton条件 B s k y k Bs_ky_k Bskyk、这个问题的目的是在所有对称、满足拟Newton条件的矩阵中,寻找在加权F范数意义下与 B k B_k Bk的差最小的矩阵.如果在这个问题中改变目标函数的矩阵范数,就得到其他的拟Newton修正公式 参考资料 1、数值最优化方法高立 编著 2、机器人中的数值优化
