最优化建模算法理论之Armjio准则(数学原理及MATLAB实现)
一、前言
为了防止迭代过程中函数值 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 < c < 1/2
alpha = 1; % 初始步长为 1
k = 0; % 统计迭代次数
gk = feval(grid, x0); % x0处的梯度值
fd = feval(fun, x0 + alpha * dk); % 函数在下一个迭代点处的目标函数值
fk = feval(fun, x0) + alpha * c * gk' * dk; % 函数在下一个迭代点处的泰勒展开值
while fd > fk
alpha = beta * alpha;
fd = feval(fun, x0 + alpha * dk);
fk = feval(fun, x0) + alpha * c * gk' * dk;
k = k + 1;
end
xk = x0 + alpha * dk; % 下降点
f = feval(fun, xk); % 下降点处函数值
end
在实际应用中,参数 c 1 c_1 c1 通常选为一个很小的正数,例如 c 1 = 1 0 − 3 c_1 = 10^{−3} c1=10−3,这使得 Armijo 准则非常容易得到满足。
三、输出示例
以 Rosenbrock 函数
为例,这是优化领域中一个著名的检验函数,其函数与其梯度函数如下:
f ( x ) = 100 ( x 2 − x 1 2 ) 2 + ( 1 − x 1 ) 2 , g ( x ) = [ − 400 x 1 x 2 + 400 x 1 3 + 2 x 1 − 2 200 x 2 − 200 x 1 2 ] \begin{aligned} &f(x) = 100(x_2 - x_1^2)^2 + (1 - x_1)^2,\\ &g(x) = \left[\begin{aligned}-400x_1x_2 + 400x_1^3 + 2x_1 - 2\\200x_2 - 200x_1^2\end{aligned}\right] \end{aligned} f(x)=100(x2−x12)2+(1−x1)2,g(x)=[−400x1x2+400x13+2x1−2200x2−200x12]
编写函数文件 Rosenbrock.m
如下:
function f = Rosenbrock(x)
f = 100 * (x(2) - x(1)^2)^2 + (1 - x(1))^2;
end
随后是梯度函数文件 grid.m
如下:
function g = grid(x)
g = [-400 * x(1) * x(2) + 400 * x(1)^3 + 2 * x(1) - 2;
200 * x(2) - 200 * x(1)^2];
end
接着我们求 Rosenbrock 函数在 [-1; 1] 点处以负梯度方向为下降方向的迭代步长,调用我们上面的 Armjio 函数,输出结果如下:
>> 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文章合集
有帮助可以点赞哦,谢谢大家的支持~