招远住房和规划建设管理局网站网站建设的业务员

当前位置： 首页 > news >正文

招远住房和规划建设管理局网站,网站建设的业务员,浙江中企建设集团有限公司网站,wordpress底部添加菜单本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等#xff0c;本系列文章篇数较多#xff0c;不定期更新#xff0c;上半部分介绍无约束优化#xff0c;…   本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等本系列文章篇数较多不定期更新上半部分介绍无约束优化下半部分介绍带约束的优化中间会穿插一些路径规划方面的应用实例 四、无约束最优化方法基础 1、无约束的最优化问题描述 无约束的最优化问题可以描述成求取使得目标函数值最小的最优解 x ∗ x^{} x∗即    min ⁡ f ( x ) \min f(x) minf(x)    其中 注1最优解 x ∗ x^{} x∗是一个解集可能包含一个解、多个解也有可能不存在 2、函数下降方向d 内容补充设 x k x_k xk​ 是经 k 步迭代后得到的迭代点, d k d_k dk​ 是在 x k x_k xk​ 点使 f ( x ) f(x) f(x) 下降的方向, a k a_k ak​ 0 是沿 d k dk dk​ 的步长,第k1个选代点则可用下式表示,它满足 f ( x k 1 ) f ( x k ) . f\left(x{k1}\right)f\left(x{k}\right). f(xk1​)f(xk​). x k 1 x k α k d k x{k1}x{k}\alpha{k}d_{k} xk1​xk​αk​dk​ 那么我们来思考满足什么条件的方向是在 x k xk xk​ 点使 f ( x ) f(x) f(x) 下降的方向呢 对任意 d ∈ R n d ∈R^n d∈Rn,若存在 α ‾ k \overline{\alpha}{k} αk​使 f ( x k α d ) f ( x k ) , ∀ α ∈ ( 0 , α ˉ k ) f\left(x{k}\alpha d\right)f\left(x{k}\right),\forall\alpha\in\left(0,\bar{\alpha}_{k}\right) f(xk​αd)f(xk​),∀α∈(0,αˉk​),则d为 f ( x ) f(x) f(x) 在点 x k xk xk​ 处下降的方向将 f ( x k α d ) f\left(x{k}\alpha d\right) f(xk​αd)在点 x k xk xk​ 处泰勒展开得到下式 f ( x k α d ) f ( x k ) α ∇ f ( x ) T d O ( ∥ α d ∥ 2 ) f\left(x{k}\alpha d\right)f\left(x{k}\right)\alpha \nabla f\left(x\right)\text{}^{\text{T}}dO\left(\left|\alpha d\right|^{2}\right) f(xk​αd)f(xk​)α∇f(x)TdO(∥αd∥2) 由上式可知当下降方向d满足 g k T d 0 g{k}^{T}d0 gkT​d0时d即为使得 f ( x ) f(x) f(x) 在点 x k xk xk​ 处下降的方向。 3、无约束最优化算法的基本结构及构成要素 第1步给定初始点 x 0 ∈ R n , k : 0 ; x{0}\in{R}^{n},k:0; x0​∈Rn,k:0; 第2步若在 x k x_k xk​点终止准则满足,则输出有关信息,停止迭代; 第3步确定 f ( x ) f(x) f(x)在 x k x_k xk​点的下降方向 d k d_k dk​; 第4步确定步长 a k ak ak​,使 f ( x k α k d k ) f\left(x{k}\alpha{k}d{k}\right) f(xk​αk​dk​)较之 f ( x ) f(x) f(x)有某种意义的下降 第5步令 x k 1 : x k α k d k , k : k 1 x{k1}:x{k}\alpha{k}d{k},k:k1 xk1​:xk​αk​dk​,k:k1转到第2步 构成一个最优化方法的基本要素有二:其一是下降的方向;其二是步长.也就是说不同的方法可得到不同的下降方向和步长。我们称所有具有以上结构的最优化方法为 线搜索型方法 在最优化方法中,下降的方向与步长的选取顺序不同,导致产生不同类型的方法.线搜索方法是在 x k x_k xk​点求得下降方向 d k d_k dk​再沿 d k d_k dk​确定步长 a k a_k ak​;信赖域方法是先限定步长的范围,再同时确定下降方向 d k d_k dk​和步长 a k a_k ak​ 算法的另一个重要问题是迭代的终止准则因为局部极小点 x ∗ x^* x∗是稳定点,我们可用 ∥ ∇ f ( x k ) ∥ ⩽ ε |\nabla\text{}f\left(x_k\right)|\leqslant\varepsilon ∥∇f(xk​)∥⩽ε 作为终止准则.这样对于使用者来说,就存在着一个选择 ε \varepsilon ε的问题. ε \varepsilon ε的大小决定所得迭代点 x k x_k xk​近似 x ∗ x^* x∗的精度.上述准则有一定的局限性.例如,对于在极小点邻域内比较陡峭的函数,即使该邻域中的点已相当接近极小点,但其梯度值可能仍然较大,从而使迭代难以停止。 其他终止准则有 ∥ x k − x k ˉ 1 ∥ ⩽ ε |xk-x{\bar{k}1}|\leqslant\varepsilon ∥xk​−xkˉ1​∥⩽ε 或者 f k − f k 1 ⩽ ε fk-f{k1}\leqslant\varepsilon fk​−fk1​⩽ε等这两个准则满足只能说明算法这时所进行的迭代对迭代点或迭代点处目标函数值的改善已经很小并不能保证 ∥ x k − x ∗ ∥ |x_k-x^*| ∥xk​−x∗∥ 或者 f k − f ⋆ f_k-f^{\star} fk​−f⋆一定足够小。 五、线搜索准则 在当前迭代点 x k x_k xk​ ,假定我们已得到下降方向 d k d_k dk​ ,求步长 a k a_k ak​的问题为一维搜索或线搜索问题,它包括两个内容:满足什么样的准则,步长可以接受?有了合适的准则,满足该准则的步长该如何求? 对如何确定 a k a_k ak​的接受准则这个问题,有两个最简单、直观的方法。即精确线搜索和非精确线搜索 1精确线搜索准则 精确线搜索是优化算法中一种用于确定每一步迭代中最优步长的方法。该方法的目标是在给定的搜索方向上找到能够最小化目标函数的步长从而快速收敛到最优解。它通常应用于梯度下降法和共轭梯度法等优化算法中。 精确线搜索即使 f x fx fx沿着 d k dk dk​寻找一个步长 a a a使得函数在该点处取得极小值如下式所示 min ⁡ α f ( x k α d k ) \min\limits\alpha f(x_k\alpha d_k) αmin​f(xk​αdk​) 设上式的解为 a k ak ak​则 x k 1 x{k1} xk1​ x k x{k} xk​ a k a{k} ak​ d k d{k} dk​且 ∇ f ( x k ) T d k 0 \nabla f\left(x{k}\right)^\mathrm{T}dk0 ∇f(xk​)Tdk​0 这一点对一些无约束最优化方法的有限终止起着关键作用然而,做精确线搜索需要求几乎精确的步长因子,当n 非常大或 f ( x ) f(x) f(x)非常复杂时,精确线搜索的计算量是相当大的,.实际上,当迭代点离最优解尚远时,是没有必要做高精度线搜索的.另外,对一般问题而言,实现精确线搜索是很困难的。 2非精确线搜索准则 正是因为精确线搜索存在的这些问题,我们产生了做非精确线搜索的想法对于步长的选取准则,我们会自然地产生第二个简单的想法,即取 a k a{k} ak​使其满足如下表达式 f ( x k α k d k ) f ( x k ) f(x_k\alpha_k d_k)f(x_k) f(xk​αk​dk​)f(xk​) 在下图所示的例子中满足上式表达式的a取值范围为 0 β 1 、 0β_1、 0β1​、 β 2 β 3 β_2β_3 β2​β3​因此仅通过以上表达式的准则来确定a的取值范围得到的a可能会接近与区间 0 β 1 0β_1 0β1​的左端点0或者区间 β 2 β 3 β_2β_3 β2​β3​的右端点 β 3 β_3 β3​因此我们应该增加一些新的准则来使得获取的a不太接近区间 0 β 1 0β_1 0β1​的左端点或者区间 β 2 β 3 β_2β_3 β2​β3​的右端点。 常用的准则有 Armijo 准则、Goldstein 准则、Wolfe 准则、强Wolfe 准则等些常用的准则.这些准则都是建立在 f ( x k α k d k ) f(x_k\alpha_k dk) f(xk​αk​dk​)在零点处的斜率 ∇ f ( x k ) T d k \nabla f\left(x{k}\right)^\mathrm{T}d_k ∇f(xk​)Tdk​为负值的前提上,否则,说明 d k d_k dk​不是下降方向,不应被采用 ① Armijo 准则 f ( x k α d k ) ⩽ f ( x k ) ρ ∇ f ( x k ) T d k α , ρ ∈ ( 0 , 1 ) . f(x_k\alpha d_k)\leqslant f(xk)\rho \nabla f\left(x{k}\right)^{\mathrm T}d_k\alpha,\quad\rho\in(0,1). f(xk​αdk​)⩽f(xk​)ρ∇f(xk​)Tdk​α,ρ∈(0,1). 一般地,可取 ρ \rho ρ为 1 0 − 3 10^{-3} 10−3或更小的值上式的右边是一个关于a的线性函数,由于 d k dk dk​是下降方向满足 ∇ f ( x k ) T d k \nabla f\left(x{k}\right)^\mathrm{T}d_k ∇f(xk​)Tdk​0该函数是关于a的减函数 只要 a不取得太小这个不等式可以保证新迭代点 x k α d k x_k\alpha d_k xk​αdk​的函数值较之点 a k a_k ak​的函数值有一定量的下降.满足该条件的点下图所示区间 0 β 4 ] 0β_4] 0β4​]和 [ β 5 β 6 ] [β_5β_6] [β5​β6​]中的点。 Armijo 准则可以避免α取得太大而接近于仅使用 f ( x k α k d k ) f ( x k ) f(x_k\alpha_k d_k)f(x_k) f(xk​αk​dk​)f(xk​)准则时图中的右端点的值. 有几种方法可以避免α取得太小而接近于仅使用 f ( x k α k d k ) f ( x k ) f(x_k\alpha_k d_k)f(x_k) f(xk​αk​dk​)f(xk​)准则时图中左端点的值,它们分别与Armijo 准则结合,构成如下准则 ② Goldstein准则 f ( x k α d k ) ⩽ f ( x k ) ρ ∇ f ( x k ) T d k α , f ( x k α d k ) ⩾ f ( x k ) ( 1 − ρ ) ∇ f ( x k ) T d k α , \begin{array}{l}f(x_k\alpha d_k)\leqslant f(xk)\rho \nabla f\left(x{k}\right)^\mathrm{T}d_k\alpha,\ f(x_k\alpha d_k)\geqslant f(xk)(1-\rho)\nabla f\left(x{k}\right)^\mathrm{T}d_k\alpha,\end{array} f(xk​αdk​)⩽f(xk​)ρ∇f(xk​)Tdk​α,f(xk​αdk​)⩾f(xk​)(1−ρ)∇f(xk​)Tdk​α,​ 其中ρ ∈(0,¹⁄₂)满足Goldstein准则的点是下图所示 β 7 β 4 ] β_7β_4] β7​β4​]和 [ β 5 β 6 ] [β_5β_6] [β5​β6​]中的点区间中的点。 Goldstein 准则是 Armijo 准则的改进版增加了一个上限条件限制步长不能太小Goldstein准则可以避免α取得太大而接近于右端点的值又可避免取得太小而接近于左端点的值。 ③ Wolfe准则 f ( x k α d k ) ⩽ f ( x k ) ρ ∇ f ( x k ) T d k α , ∇ f ( x k α d k ) T d k ⩾ σ ∇ f ( x k ) T d k , \begin{array}{l}f(x_k\alpha d_k)\leqslant f(xk)\rho\nabla f\left(x{k}\right)^\mathrm{T}d_k\alpha,\ \nabla f(x_k\alpha d_k)^{\mathrm T}dk\geqslant\sigma \nabla f\left(x{k}\right)^\mathrm{T}d_k,\end{array} f(xk​αdk​)⩽f(xk​)ρ∇f(xk​)Tdk​α,∇f(xk​αdk​)Tdk​⩾σ∇f(xk​)Tdk​,​ 其中的σ和ρ满足1σ ρ0满足Wolfe 准则的点为下图所示区间 β 7 β 4 ] β_7β_4] β7​β4​] [ β 8 β 9 ] [β_8β9] [β8​β9​] [ β 10 β 6 ] [β{10}β_6] [β10​β6​]中的点. Wolfe准则中的第二条是要求 f ( x k α d k ) f(x_k\alpha d_k) f(xk​αdk​)在点a的斜率不能小于 f ( x k α d k ) f(x_k\alpha dk) f(xk​αdk​)在零点斜率 ∇ f ( x k ) T d k \nabla f\left(x{k}\right)^{\mathrm{T}}d_{k} ∇f(xk​)Tdk​的σ倍。假设在零点的斜率为下图中绿色曲线所示的-p1则在点a的斜率应该位于下图中灰色扇形所覆盖的区域内。 我认为可以这样理解这条准则若在a的斜率不在下图中扇形区域内可以认为函数值在a处的下降率较大稍微增大a的值函数值会有较大的下降因此更趋向于取当前位置右侧的值作为a值因为其位置处函数值更小。 在Wolfe准则中的第二条中即使σ取为0,亦无法保证满足准则的点接近精确线搜索的结果。因为其仅仅限制了负斜率较高的情况即函数值在a点处快速下降的区域而没有对正斜率较大的区域进行限制即函数值在a处快速上升的区域 若采用下面的强 Wolfe 准则, σ取得越小,满足准则的α越接近精确线搜索的结果 ④ 强Wolfe准则 f ( x k α d k ) ⩽ f ( x k ) ρ ∇ f ( x k ) T d k α , ∣ ∇ f ( x k α d k ) T d k ∣ ⩽ − σ ∇ f ( x k ) T d k , \begin{array}{l}f(x_k\alpha d_k)\leqslant f(xk)\rho \nabla f\left(x{k}\right)^\mathrm{T}d_k\alpha,\[8pt]| \nabla f(x_k\alpha d_k)^{\mathrm T}dk|\leqslant-\sigma \nabla f\left(x{k}\right)^\mathrm{T}d_k,\end{array} f(xk​αdk​)⩽f(xk​)ρ∇f(xk​)Tdk​α,∣∇f(xk​αdk​)Tdk​∣⩽−σ∇f(xk​)Tdk​,​ 从上图可以看出强 Wolfe 准则对正斜率和负斜率较大的区域都进行了限制且 σ取得越小满足强 Wolfe准则的α越接近精确线搜索的结果 其中的σ和ρ满足1σ ρ0实际应用中控制α不要太小的准则可以不用因为在线搜索时,只要给定 α k α_k αk​一个下界即可. 参考资料 1、机器人中的数值优化 2、梯度下降 3、数值最优化方法高立 编著