自适应的两点步长梯度法

2024-04-10 15:00:07 阅读数 392

自适应的两点步长梯度法
本文是我在博客园中写的一篇随笔：自适应的两点步长梯度法 - 来者可追2019 - 博客园 (cnblogs.com)

该算法来自于戴彧虹研究员的一篇论文，该文章将两点步长梯度法与非单调搜索结合，并且对非单调搜索的法则进行了改进。

问题引入：
考虑无约束优化问题： $\mathop{min}\limits_{x\in \mathbb{R}^n} \quad f(x)$ 两点步长的迭代法则是： $x_{k+1}=x_k-\alpha_kg_k$ 其中 $g_k=\nabla f(x_k),\alpha_k=\frac{s_{k-1}^Ts_{k-1}}{s_{k-1}^Ty_{k-1}},s_{k-1}=x_k-x_{k-1},y_{k-1}=g_k-g_{k-1}$

一般的非单调搜索是寻找满足下面条件的 $\alpha_k$ : $f(x_k+\alpha_kd_k) \leq \mathop{min}\limits_{0 \leq i \leq m(k)}f(x_{k-i})+\delta\alpha_kg_k^Td_k$ 其中 $m(k)=min(k,M-1)$ ，在实际运算中，数值效果很大程度上取决于 $M$ 的选择。

改进思路如下：

令： $f_{min}=\mathop{min}\limits_{0 \leq i \leq k}f(x_i)$ , $l=k-k_{min}$ ,而 $k_{min}$ 是取到目前最小值的第一个下标。

又令： $f_{max}=\mathop{max}\limits_{0 \leq i \leq min\{k,M-1\}}f(x_{k-i}),f_c=\mathop{max}\limits_{k_{min} \leq i \leq k}f(x_{i})$

一种改进方法是设置参考值 $f_r$ 代替一般非单调搜索中 $\mathop{min}\limits_{0 \leq i \leq m(k)}f(x_{k-i})$ 的位置，具体地：当 $l=L(某个正整数)$ 时，取 $f_r=f_{max}$ 。但是有时会出现 $f_{max}$ 太大的情况，这时戴老师的处理方法是取 $f_r=f_c$ ,即：
$f_r=\left\{ \begin{array}{rcl} f_c & , & if \quad \frac{f_{max}-f_{min}}{f_c-f_{min}} > \gamma_1 \\ f_{max} & , & otherwise \end{array} \right.$
其中 $\gamma_1$ 为一个大于1的常数。这个修改我们称为(1).

另外一种情况是，非单调搜索算法在之前很多的迭代次数内都直接接受初始步长 $\alpha_k^{(1)}$ 作为迭代步长，令 $p$ 为之前连续接收的次数，即 $\alpha_{k-1}^{(1)},\alpha_{k-2}^{(1)},\dots,\alpha_{k-p}^{(1)}$ 都被接受，而 $\alpha_{k-p-1}^{(1)}$ 不被接受。如果 $p$ 太大了，这很可能是因为 $f_r$ 一直不改变所引起的。此时，戴老师的改进方法是：当 $p >P$ （正整数、常数），令：
$f_r=\left\{ \begin{array}{rcl} f_{max} & , & if \quad f_{max} > f(x_k) \quad and \quad \frac{f_{max}-f_{min}}{f_c-f_{min}} \geq \gamma_2 \\ f_r & , & otherwise \end{array} \right.$

其中 $\gamma_2$ 为一个大于1的常数。这个修改我们称为(2).

综上，改进的非单调搜索方法如下：

Step1(修改参考值)：
如果 $l=L$ ,按(1)的方式更新 $f_r$ ,同时令 $l=0$ ；
如果 $p \geq P$ ,按(2)的方式更新 $f_r$ ,同时令 $l=0$ ;

Step2(测试原始步长)：
如果 $f(x_k+\alpha_k^{(1)}d_k) \leq f_r+\delta\alpha_k^{(1)}g_k^Td_k$ 则令 $\alpha_k=\alpha_k^{(1)}$ 和 $p=p+1$ ，并转到Step4;否则，令 $p=0$ ;

Step3(调整步长满足条件)：
$(i)$ 令 $\alpha_{old}=\alpha_k^{(1)}$ ;
$(ii)$ 取 $\alpha_{new} \in [\sigma_1 \alpha_{old},\sigma_2 \alpha_{old}].$ 如果 $f(x_k+\alpha_{new}d_k) \leq \mathop{min}(f_r,f_{max})+\delta\alpha_{new}g_k^Td_k$ 则令 $\alpha_k=\alpha_{new}$ ，并转向Step4；否则，令 $\alpha_{old}=\alpha_{new}$ ，并重复 $(ii)$ ;

Step4(更新一些数值)：
$(i)$ 令 $f_{k+1}=f(x_k+\alpha_kd_k)$ ；
$(ii)$ 如果 $f_{k+1} < f_{min}$ ，设 $f_c=f_{min}=f_{k+1}$ 且 $l=0$ ;否则，令 $l=l+1$ ；
$(iii)$ 如果 $f_{k+1} > f_c$ ，令 $f_c=f_{k+1}$ ；
$(iv)$ 计算 $f_{max}$ ，并令 $k=k+1$ .

结合两点步长梯度法与上述自适应非单调线性搜索法则，就得到了一个新的无约束算法的梯度算法，即自适应两点步长梯度法.

Step0（参数初始化）：
$(i)$ 给定 $0<\alpha_{min}<\alpha_{max}$ , $0<\sigma_1<\sigma_2<1$ , $\epsilon \geq 0$ ,令 $k:=1$ ;
$(ii)$ 给定正整数 $P > M > L$ 和常数 $\gamma_1\geq1$ ， $\gamma_2\geq1$
$(iii)$ 取 $x_1 \in \mathbb{R}^n,\alpha_1^{(1)}\in[\alpha_{min},\alpha_{max}],d_1=-g_1;$
$(iv)$ 令 $l:=0,p:=0,f_{min}=f_c=f_r:=f(x_1)$ .

Step1（是否满足停机条件）：如果 $\Vert g_k \Vert_{\infty} \leq \epsilon\$ ,则停止.

Step2：按照自适应非单调搜索的方式计算 $\alpha_k$ 并更新 $f_r$ 和 $f_{min}$ .

Step3： $x_{k+1}=x_k+\alpha_kd_k,d_{k+1}=-g_{k+1};$

Step4：
$(i)$$s_k=x_{k+1}-x_k,y_k=g_{k+1}-g_k;$
$(ii)$ 如果 $s_k^Ty_k \leq 0,\alpha_{k+1}^{(1)}=\alpha_{max};$ 否则 $\alpha_{k+1}^{(1)}=max\{\alpha_{min},min\{\frac{s_k^Ts_k}{s_k^Ty_k},\alpha_{max}\}\}$ .

Step5： $k:=k+1,$ 返回Step1.

在这里，文章给出的参数设置建议是：
$L \leq 5,P \geq 4M \geq 8L,\gamma_1=M/L,\gamma_2=P/M$

参考论文：Y.H. Dai and H.C. Zhang, Adaptive two-point stepsize gradient algorithm, Numer. Algorithms 27 (2001), pp. 377–385.