| 最优化建模算法理论之Armjio准则（数学原理及MATLAB实现） | 您所在的位置：网站首页 › 线性搜索算法的优缺点 › 最优化建模算法理论之Armjio准则（数学原理及MATLAB实现） |
最优化建模算法理论之Armjio准则（数学原理及MATLAB实现）
|
文章目录
一、前言二、Armjio准则1. 定义2. 几何含义
三、代码实现三、输出示例四、附
一、前言
为了防止迭代过程中函数值 f ( x k ) f(x^k) f(xk) 的下降量不够充分，以至于算法无法收敛到极小值点，必须引入一些更合理的线搜索准则来确保迭代的收敛性。 Armijo 准则是一个常用的线搜索准则，引入 Armijo 准则的目的是保证每一步迭代充分下降。 二、Armjio准则 1. 定义设 d k d^k dk 是点 x k x^k xk 处的下降方向，若 f ( x k + α d k ) ≤ f ( x k ) + c α ∇ f ( x k ) T d k (1) f(x^k + \alpha d^k) \le f(x^k) + c\alpha \nabla f(x^k)^Td^k \tag{1} f(xk+αdk)≤f(xk)+cα∇f(xk)Tdk(1) 则称步长 α \alpha α 满足 Armjio 准则，其中 c ∈ ( 0 , 1 ) c \in (0, 1) c∈(0,1) 是一个常数。 2. 几何含义Armjio 准则有非常直观的几何含义，它指的是点 ( α , ϕ ( α ) ) (\alpha, \phi(\alpha)) (α,ϕ(α)) 必须在直线 l 1 ( α ) = ϕ ( 0 ) + c α ∇ f ( x k ) T d k l_1(\alpha) = \phi(0) + c\alpha \nabla f(x^k)^Td^k l1(α)=ϕ(0)+cα∇f(xk)Tdk 的下方。如下图所示：
区间 [ 0 , α 1 ] [0, \alpha_1] [0,α1] 中的点均满足 Armijo 准则。我们注意到 d k d_k dk 为下降方向，这说明 l ( α ) l (α) l(α) 的斜率为负，选取符合条件 （1） 的 α \alpha α 确实会使得函数值下降。 三、代码实现以下编译环境为 MATLAB R2019b 下编译运行，不同版本可能略有出入。 function [alpha, xk, f, k] = Armjio(fun, grid, x0, dk) % % Function [alpha, xk, fx, k] = Armjio(fun, grid, x0, dk) % 求出函数fun在x0处以dk为下降方向时的步长alpha，同时返回相对应的下 % 一个下降点xk以及xk处的函数值fx，k为迭代次数 % ----------------------------------------------------------- % 输入: % fun 函数名称(字符变量） % grid 梯度函数名称(字符变量) % x0 迭代点(列向量) % dk 函数在迭代点处的下降方向(列向量) % % 输出: % alpha 函数在x0处以dk为下降方向时的下降步长 % xk 函数在x0处以dk为下降方向，以alpha为步长 % 求得的下降点 % fx 函数在下降点xk处的函数值 % k 求步长算法迭代次数 % ----------------------------------------------------------- % by Zhi Qiangfeng % beta = 0.333; % 步长 alpha 的迭代系数，小于 1 c = 1e-3; % 泰勒展开式补足系数，0 > x0 = [-1; 1]; >> dk = -grid(x0); >> [alpha, xk, fx, k] = Armjio("Rosenbrock", "grid", x0, dk) alpha = 0.0014 xk = -0.9945 1.0000 fx = 3.9900 k = 6输出：Rosebrock 函数在 [-1; 1] 点处以负梯度方向为下降方向的迭代步长为 0.0014，下一个迭代点为 [-0.9945; 1]，且下一步函数值为 3.99。 四、附最优化相关算法设计数学原理：最优化/Optimization文章合集 有帮助可以点赞哦，谢谢大家的支持~ |
【本文地址】