恩施网站建设xiduyun,优质的专业网站建设,昵图网 图库 素材,小程序制作联系方式怎么添加本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等#xff0c;本系列文章篇数较多#xff0c;不定期更新#xff0c;上半部分介绍无约束优化#xff0c;… 本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等本系列文章篇数较多不定期更新上半部分介绍无约束优化下半部分介绍带约束的优化中间会穿插一些路径规划方面的应用实例 七、信赖域方法 1、信赖域方法简介 信赖域方法Trust Region Methods是一种用于非线性优化的数值优化方法旨在寻找目标函数的最小值。信赖域算法是一种迭代算法即从给定的初始解出发通过逐步迭代不断改进直到获得满意的近似最优解为止。其基本思想是把最优化问题转化为一系列简单的局部寻优问题。 它的核心思想是在当前点的局部模型和真实模型之间建立一个可信区域Trust Region并在可信区域内寻找更优的解。 该方法在解决非线性优化问题时常使用局部二次模型来近似目标函数并在每个迭代步骤中解决这个二次模型的最小化问题。信赖域方法是求解非线性最优化问题的有效方法之一广泛应用于计算机视觉、机器学习、优化控制等领域。 2、信赖域方法基本思想 信赖域方法的基本思想是将问题分解为多个步骤。首先用一个二次模型来近似目标函数这个模型只在一个局部域内是准确的。其次在这个局部域内求解二次模型的最小值。最后使用这个最小值来更新优化变量然后检查更新后的函数值是否小于当前的函数值。如果是则扩大局部域的半径否则缩小局部域的半径以此控制每个步骤的更新大小。 那么为什么要构建局部模型而不使用真实模型呢 假设在点 x k x_k xk处我们欲求下降方向 d x d_x dx若直接求解极小值问题 m i n f ( x k d ) min f(x_k d) minf(xkd)去得到 d k d_k dk那么这个问题与原问题复杂程度相同而关于方向d的问题应该是相对简单、易求的。所以解决这个问题简单可行的方法是:利用Taylor展式,在点 x k x_k xk的邻域中,使用 f ( x k d ) f(x_k d) f(xkd)的一阶近似函数或二阶近似函数作为局部模型代替 f ( x k d ) f(x_k d) f(xkd)去求 d k d_k dk 。常使用二阶近似函数,我们记这个局部模型函数为 q k ( d ) q_k(d) qk(d)求取局部模型 q k ( d ) q_k(d) qk(d)的极小点并将其作为迭代方向 d k d_k dk ,即求 min d q k ( d ) \operatorname*{min}_{d}q_{k}(d) dminqk(d) q k ( d ) q_k(d) qk(d)近似 f ( x k d ) f(x_k d) f(xkd)的好坏,是受到 x k x_k xk处邻域大小的影响的.合适的邻域和合适的近似函数的选取,可以保证 q k ( d ) q_k(d) qk(d)是 f ( x k d ) f(x_k d) f(xkd)的一个好的近似函数如取 q k ( d ) f k ∇ f k T d 1 2 d T ∇ 2 f k d q_k(d)f_k \nabla f_k^T d \frac{1}{2} d^T \nabla^2 f_k d qk(d)fk∇fkTd21dT∇2fkd 当||d||较小时 q k ( d ) q_k(d) qk(d)近似 f ( x k d ) f(x_k d) f(xkd)的误差亦小 如果 x k x_k xk处的邻域太大,就无法保证 q k ( d ) q_k(d) qk(d)是 f ( x k d ) f(x_k d) f(xkd)的好的近似函数此时可能会出现 q k ( d ) q_k(d) qk(d)的极小点与目标函数 f ( x k d ) f(x_k d) f(xkd)的极小点相差甚远的情况. 而邻域的大小决定了步长的长短太短的步长会增加算法的迭代次数影响算法的收敛速度所以领域也不能取得过小。 因此,每步迭代在 x k x_k xk处选择一个合适的邻域在这个邻域中求解 min d q k ( d ) \operatorname*{min}_{d}q_{k}(d) mindqk(d)这就是信赖域方法的思想.这个邻域,我们称之为信赖域,即在此信赖域中,我们相信 q k ( d ) q_k(d) qk(d)是 f ( x k d ) f(x_k d) f(xkd)的好的近似函数. 假定在第k步迭代已得 x k x_k xk以及信赖域的半径 Δ k \Delta_k Δk则信赖域的子问题即为求解如下表达式得到 d k d_k dk min q k ( d ) , s.t. ∥ d ∥ ⩽ Δ k , Δ k 0 \begin{array}{l}\min q_k(d),\\ \textrm{s.t.}\|d\|\leqslant\Delta_k,\Delta_k0\end{array} minqk(d),s.t.∥d∥⩽Δk,Δk0 在得到新的迭代点 x k 1 x k d k x_{k1}x_kd_k xk1xkdk之后,我们可以判断 Δ k \Delta_k Δk是否是下一步迭代的合适的信赖域半径,若不合适,可以修正 Δ k \Delta_k Δk得下一步迭代的 Δ k 1 \Delta_{k1} Δk1上式中的范数可依方法而定。 那么如何衡量 Δ k \Delta_k Δk是否是下一步迭代的合适的信赖域半径呢 应该根据 x k x_k xk处 q k ( d ) q_k(d) qk(d)近似 f ( x k d ) f(x_k d) f(xkd)的好坏来确定具体来说可以根据从 x k x_k xk到 x k d k x_kd_k xkdk f ( x ) f(x) f(x)的实际减少量 Δ f k \Delta f_k Δfk与近似函数 q k ( d ) q_k(d) qk(d)的减少量 Δ q k \Delta q_k Δqk之比 γ k \gamma_k γk来衡量其中 q k ( 0 ) f ( x k ) q_k(0)f(x_k) qk(0)f(xk) Δ f k f ( x k ) − f ( x k d k ) Δ q k q k ( 0 ) − q k ( d k ) γ k Δ f k Δ q k \begin{array}{l}\Delta f_kf(x_k)-f(x_kd_k)\\ \\ \Delta q_kq_k(0)-q_k(d_k)\\ \\ \gamma_k\dfrac{\Delta f_k}{\Delta q_k}\end{array} Δfkf(xk)−f(xkdk)Δqkqk(0)−qk(dk)γkΔqkΔfk γ k \gamma_k γk接近1时,表明 q k ( d ) q_k(d) qk(d)近似 f ( x k d ) f(x_k d) f(xkd)的程度好下一步迭代应增大 Δ k \Delta_k Δk;当 γ k \gamma_k γk为接近于零的正数时,表明 q k ( d ) q_k(d) qk(d)近似 f ( x k d ) f(x_k d) f(xkd)的程度不好,下一步迭代应减小 Δ k \Delta_k Δk;当 γ k \gamma_k γk为零或负数时说明 f ( x k d k ) ≥ f ( x k ) f(x_k d_k)≥ f(x_k) f(xkdk)≥f(xk) x k d k x_k d_k xkdk不应被接受为下一步的迭代点这时只应缩小信赖域的半径 γ k \gamma_k γk:,并重新求解。 3、信赖域方法的具体步骤 1初始化选择一个初始点 x 0 x_0 x0设定信赖域的初始大小 Δ 0 \Delta_0 Δ0初始化迭代次数k0。 2开始迭代判断是否满足终止条件例如目标函数的值达到了一定的精度若满足则输出 x k x_k xk迭代停止 3构建局部模型在当前点 x k x_k xk处构建一个局部二次模型 q k ( d ) f k ∇ f k T d 1 2 d T ∇ 2 f k d q_k(d)f_k \nabla f_k^T d \frac{1}{2} d^T \nabla^2 f_k d qk(d)fk∇fkTd21dT∇2fkd 其中 f k f_k fk是目标函数在 x k x_k xk处的函数值 ∇ f k \nabla f_k ∇fk是目标函数在 x k x_k xk处的梯度 ∇ 2 f k \nabla^2 f_k ∇2fk是目标函数在 x k x_k xk处的Hessian矩阵的近似值。 4寻找下降方向求解 q k ( d ) q_k(d) qk(d)的最小值 d k d_k dk满足 ∣ d k ∣ ≤ Δ k |d_k| \leq \Delta_k ∣dk∣≤Δk其中 Δ k \Delta_k Δk是当前信赖域的半径。 5计算实际下降量和预测下降量计算从 x k x_k xk到 x k d k x_kd_k xkdk f ( x ) f(x) f(x)的实际减少量 Δ f k \Delta f_k Δfk与近似函数 q k ( d ) q_k(d) qk(d)的减少量 Δ q k \Delta q_k Δqk之比 γ k \gamma_k γk 6更新信赖域大小根据比值 γ k \gamma_k γk的大小更新信赖域大小 如果 γ k \gamma_k γk一定程度上接近于1比如说 γ k \gamma_k γk0.75说明局部模型对目标函数有较好的拟合效果可以增加信赖域的大小 Δ k 1 min ( γ 2 Δ k , Δ max ) \Delta_{k1}\min(\gamma_2 \Delta_k, \Delta_{\max}) Δk1min(γ2Δk,Δmax)其中 γ 2 1 \gamma_21 γ21是一个大于1的常数 Δ max \Delta_{\max} Δmax是信赖域大小的上限。 如果 γ k \gamma_k γk一定程度上接近于0比如说 γ k \gamma_k γk0.25说明局部模型对目标函数的拟合效果较差应该减少信赖域的大小 Δ k 1 γ 1 Δ k \Delta_{k1}\gamma_1 \Delta_k Δk1γ1Δk其中 0 γ 1 1 0\gamma_11 0γ11是一个小于1的常数。 如果 γ k \gamma_k γk位于0~1之间既不靠近0也不靠近1比如说0.25 γ k \gamma_k γk0.75说明局部模型对目标函数的拟合效果既不好也不坏可以保持信赖域不变 Δ k 1 Δ k \Delta_{k1}\Delta_k Δk1Δk。 7判断是否接受新的点 x k 1 x k d k x_{k1}x_kd_k xk1xkdk。 如果 γ k \gamma_k γk0说明 f ( x k d k ) ≥ f ( x k ) f(x_k d_k)≥ f(x_k) f(xkdk)≥f(xk) x k d k x_k d_k xkdk不应被接受为下一步的迭代点取 x k 1 x k x_{k1}x_k xk1xk转到第2步继续迭代重新求取第k次迭代的解。 如果 γ k \gamma_k γk0说明 f ( x k d k ) f ( x k ) f(x_k d_k) f(x_k) f(xkdk)f(xk) x k d k x_k d_k xkdk可以被接受为下一步的迭代点取 x k 1 x k d k x_{k1}x_kd_k xk1xkdk并将迭代数加1即kk1转到第2步继续迭代。 4、总结 与线搜索方法先在 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。 信赖域方法相对于其他优化算法的优点在于它可以保证每次迭代都可以得到一个可行解并且可以保证在可信区域内寻找更优的解从而增加算法的稳定性和可靠性。此外信赖域方法也可以灵活地处理约束条件和不等式约束问题。 然而信赖域方法也存在一些缺点。例如它可能会陷入局部最优解并且每次迭代需要计算Hessian矩阵或其近似计算成本较高。同时信赖域大小的选取也需要一定的经验和调试。 总的来说信赖域方法是一种有效的非线性优化算法可以用于解决一类较为复杂的优化问题。 参考资料 1、机器人中的数值优化 2、信赖域算法 3、数值最优化方法高立 编著
