公司设计网站,点开文字进入网站是怎么做的,wordpress logo链接,中国设计品牌网本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等#xff0c;本系列文章篇数较多#xff0c;不定期更新#xff0c;上半部分介绍无约束优化#xff0c;… 本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等本系列文章篇数较多不定期更新上半部分介绍无约束优化下半部分介绍带约束的优化中间会穿插一些路径规划方面的应用实例 八、线搜索最速下降法 1、最速梯度下降法简介 梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数即无约束优化问题时梯度下降Gradient Descent是最常采用的方法之一另一种常用的方法是最小二乘法。在求解损失函数的最小值时可以通过梯度下降法来一步步的迭代求解得到最小化的损失函数和模型参数值。反过来如果我们需要求解损失函数的最大值这时就需要用梯度上升法来迭代了。在机器学习中基于基本的梯度下降法发展了两种梯度下降方法分别为随机梯度下降法和批量梯度下降法。 最速梯度下降法利用函数的一阶信息局部的去找一个让函数下降最快的方向然后沿着这个方向不断的逼近局部极小值 对于有梯度的函数而言最速下降的方向一定是其梯度的反方向如下图中的蓝色箭头所示 如果梯度存在沿着梯度的反方向去更新一个x一定会更接近于局部极小值迭代格式如下式所示其中τ是步长 ∇ f ( x k ) \nabla\text{}f\left(x^k\right)\quad\text{} ∇f(xk)是梯度或最小范数次梯度(次梯度集合里面模长最小的那个向量取反方向) x k 1 x k − τ ∇ f ( x k ) x^{k1}x^{k}-τ\nabla\text{}f\left(x^k\right)\quad\text{} xk1xk−τ∇f(xk) 2、最速梯度下降法流程 3、步长τ的选取 ① 策略1τ取固定常量如1、0.1、0.01等 ② 策略2τ取递减量随着搜索的次数增加而减小 ③ 策略3精确线搜索理想的方式每次搜索的步长都沿着搜索方向让多元函数的截面到达最低点称为最佳步长沿着搜索方向下降最多的步长。然而找最佳步长本身就是一个优化的问题。 ④ 策略4非精确线搜索将策略3的条件进行弱化使得搜索步长不需要解决子优化问题也可以快速的搜索 内容补充一阶方向导数表示函数在该点处沿着方向d的函数值的变化率可表示成如下的形式 ∂ f ( x ) ∂ d 1 ∥ d ∥ ∇ f ( x ) T d ; \frac{\partial f\left(x\right)}{\partial d}\frac{1}{\left\|d\right\|}\nabla f(x)^{T}d; ∂d∂f(x)∥d∥1∇f(x)Td; 1策略① τ取固定常量时若步长太大可能振荡发散步长太小可能收敛过慢当步长恰当时快速收敛。因此固定步长策略需要依靠经验设定合适的步长如下图所示 2 策略②的稳定性较强但收敛速度较慢一般用于对函数的条件很差的时候并且对于求解速率和时间没什么要求的时候。 3 策略④我们可以沿着搜索方向d把周围的函数 f x k fx^{k} fxk解出一个一维的函数这个函数的意思就是当步长取α时对应函数的高度就是图中曲线φ(0)值是 f f f在 f x k fx^{k} fxk处的初始值 如果仅是让函数下降的话跟初始值φ(0)齐平以下的所有区域都可以选如下图所示的0~α2区域但是为了更快的下降需要更严苛的条件这个条件是跟梯度有关的比如若局部极小值为1而当前解为1.001无论如何不能让函数的下降大于0.001因此我们要根据函数当前的梯度或者斜域来定充分下降的斜对数它的斜率就是φ(0)的斜率即搜索方向d与 x k x^{k} xk处梯度的点积 d T ∇ f ( x k ) d^{\mathrm{T}}\nabla f(x^{k}) dT∇f(xk),再乘以一个0~1的系数c对其进行放松得到一个更小的区间0 ~ α1一般来说我们需要找一个不接近于0的步长在这个Armijo condition 区域内搜索一个较靠右的步长即我们想要的步长。 对于非凸函数的可接受区域如下图所示 4、最速下降法流程及策略③和④的比较 给定一个x0首先求他的梯度取负梯度为它的搜索方向然后利用二分法不断的二分α区间去找一个满足Armijo condition的步长α然后接受他去更新下一个x的位置不断的循环当f在xk处的梯度的模长足够小时结束循环。当不可微时梯度改为次微分检验即含零向量时即可结束循环 策略③只有找到上图中的最低点时才进行更新而策略④只要找到的步长位于Armijo condition 区域内即可进行更新。这样会节省一些时间而且更简单一些在工程中策略④更常用 从下图中可以看出若采用精确线搜索策略③只需要寥寥几步更新就可以收敛较理想的状态若采用充分下降线搜索策略④可能需要迭代多次更新但是精确线搜索每次迭代花费算力较多时间较长而充分下降搜索耗时较少所以总的花费时间≈单次耗时x迭代次数。两种策略的总耗时是近似的。 在下图所示的这样一个100维的凸函数的例子中当精度要求比较高时如0.0001两种策略的迭代次数近似而策略③的每次迭代耗时多于策略④ 5、最速下降法的收敛速度 u在G度量意义下的范数 ∥ u ∥ G 2 \|u\|_G^2 ∥u∥G2定义为其中G为Hesse矩阵 ∥ u ∥ G 2 u T G u . \|u\|_G^2{u}^\mathrm{T}Gu. ∥u∥G2uTGu. 对正定二次函数,最速下降方法的收敛速度为 ∥ x k 1 − x ∗ ∥ G 2 ∥ x k − x ∗ ∥ G ⩽ ( λ max − λ min λ max λ min ) 2 . \frac{\|x_{k1}-x^*\|_G^2}{\|x_k-x^*\|_G}\leqslant\left(\frac{\lambda_{\text{max}}-\lambda_{\text{min}}}{\lambda_{\text{max}}\lambda_{\text{min}}}\right)^2. ∥xk−x∗∥G∥xk1−x∗∥G2⩽(λmaxλminλmax−λmin)2. 上式中有 (其中 cond ( G ) ∥ G ∥ ∥ G − 1 ∥ \operatorname{cond}(G)\|G\|\|G^{-1}\| cond(G)∥G∥∥G−1∥称为矩阵G的条件数 λ max − λ min λ max λ min c o n d ( G ) − 1 c o n d ( G ) 1 ≜ μ \frac{\lambda_{\max}-\lambda_{\min}}{\lambda_{\max}\lambda_{\min}}\frac{\mathrm{cond}(G)-1}{\mathrm{cond}(G)1}\triangleq\mu λmaxλminλmax−λmincond(G)1cond(G)−1≜μ. 由上式可以看出最速下降方法的收敛速度依赖于G的条件数.当G的条件数接近于1时, u接近于零,最速下降方法的收敛速度接近于超线性收敛速度;而G的条件数越大,u越接近于1,该方法的收敛速度越慢. Hesse矩阵G的条件数的差异造成了最速下降方法对如下图所示的两个问题收敛速度的差异.在下图可以看出最速下降方法相邻两步的迭代方向互相垂直,Hesse矩阵的条件数越大,二次函数一族椭圆的等高线越扁.可以想象,当目标函数的等高线为一族很扁的椭圆时,迭代在两个相互垂直的方向上交替进行.如果这两个方向没有一个指向极小点,迭代会相当缓慢,甚至收敛不到极小点. 6、最速下降法的优缺点 1缺点 当一个凸函数的条件数等于2时等高线是一系列的椭圆他的梯度是垂直于椭圆的边界的如果条件数很大椭圆就很扁用最速下降法来迭代就会产生一些震荡。 当条件数更大如100时椭圆会更扁由于梯度方向与等高线垂直导致梯度方向近似于平行需要震荡很久才能收敛到局部极小值。所以当函数的曲率很大或者条件数很大的时候采用梯度下降法可能需要很多的迭代次数。 下图是一个二维的二次函数的例子从图中可以看出随着条件数的增大收敛所需的迭代次数也随之增加 2优点 最速下降方法的优点是:算法每次迭代的计算量少,存储量亦少; 即使从一个不太好的初始点出发,算法产生的迭代点也可能接近极小点. 参考资料 1、机器人中的数值优化 2、梯度下降 3、数值最优化方法高立 编著
