自适应可行BB类算法
本文的算法来自于论文： Bo Jiang & Yu-Hong Dai (2013) Feasible Barzilai–Borwein-like methods for extreme symmetric eigenvalue problems, Optimization Methods and Software, 28:4, 756-784, DOI: 10.1080/10556788.2012.656115
该文章研究了极值对称特征值问题的可行BB类算法并给出了收敛性分析。本文仅整理其主要算法部分，并略去了详细证明。
___________________________________________________________________________
问题引入：
研究的主要问题是：
$$\mathop{min}\limits_{x \in \mathbb{R}^n}h(x)=\frac{1}{2}x^TAx$$
$$s.t. x \in \Omega:=\{x:x^Tx=1,x \in \mathbb{R}^n\}$$
其中$A$为对称矩阵，该问题相当于$$\mathop{min}\limits_{x \in \mathbb{R}^n/\{\mathbf{0}\}}\frac{x^TAx}{x^Tx}$$
本文的常见记号如下：
$f(x)=x^TAx=2h(x),g(x)=Ax,g^L(x)=g(x)-f(x)x$，通常也简记为$f,g,g^L.$
在第$k$次迭代中，记$f_k=f(x_k),g_k=g(x_k),g^L_k=g^L(x_k).$
$\Vert x \vert=\sqrt{x^Tx},\lambda_{min}=\mathop{min}\limits_{x \in \mathbb{R}^n/\{\mathbf{0}\}}\frac{x^TAx}{x^Tx},\lambda_{max}=\mathop{max}\limits_{x \in \mathbb{R}^n/\{\mathbf{0}\}}\frac{x^TAx}{x^Tx}$,其中$\lambda_{min},\lambda_{max}$分别为$A$的最小和最大特征值。
___________________________________________________________________________
本算法的迭代更新形式：
取$\forall x \in \Omega,记N_x=\{d:x^Td=0\}$为$x$的零空间.
本算法更新的基本想法是先沿着上一个迭代点$x$的方向延长或缩短然后在沿着某个$N_x$（即与$x$垂直的）中向量的方向走一段距离，即$$Y(\tau,x)=\alpha(\tau)x-\beta(\tau)d$$其中$\tau>0,\alpha(0)=1,\beta(0)=0$
此时令$\alpha(\tau)=\nu(\tau)-1$，而下一个迭代点还需要在可行域$\Omega$内，即：$Y(\tau,x)^TY(\tau,x)=1$，得:$$(\nu(\tau)-1)^2+\beta(\tau)d^Td=1$$相当于$$\frac{2}{\nu(\tau)}=1+(\frac{\beta{\tau}}{\nu(\tau)})^2d^Td$$
记$\phi(\tau)=\frac{\beta(\tau)}{\nu(\tau)}$，其满足$\Phi(0)=0$，且
$$\alpha(\tau)=\frac{1-\Phi(\tau)^2d^Td}{1+\Phi(\tau)^2d^Td}$$
$$\beta(\tau)=\frac{2\Phi(\tau)}{1+\Phi(\tau)^2d^Td}$$
有了这个迭代形式，我们发现在某次迭代时，只需要选择合适的迭代方向与步长即可，下面两个部分就来讨论迭代方向以及步长的选择
___________________________________________________________________________
迭代方向的选择：
根据上述形式，类似于最速下降法，我们需要找到一个最速下降方向$d^* \in N_x$，这相当于求解$$\mathop{min}\limits_{d \in N_x} -\frac{d^Tg}{\Vert d \Vert\Vert g \Vert}$$而取这个问题的一个最优解为$d^*=g-(x^Tg)x=g^L$，作为我们的迭代方向。
于是论文中设$\phi(\tau)=a\tau(a\in (0,1)为常数)$，给出了一种更新方案即：
$$Y(\tau,x)=\alpha(\tau,x)x-\beta(\tau,x)g^L$$
$$\alpha(\tau,x)=\frac{1-a^2\tau^2\Vert g^L \Vert^2}{1+a^2\tau^2\Vert g^L \Vert^2}$$
$$\beta(\tau,x)=\frac{2a\tau}{1+a^2\tau^2\Vert g^L \Vert^2}$$
论文取$a=1/2$.
___________________________________________________________________________
步长选择:
考虑迭代点的更新方式如下：$$x_{k+1}=x_k-\tau_k\nabla q(x_k)$$其中$q(x)为某个目标函数，$记:$s_{k-1}=x_k-x_{k-1},y_{k-1}=\nabla q(x_k)-\nabla q(x_{k-1}).$
Barzilar和Borwein考虑的步长选择为:$$\tau_k=\mathop{argmin}\limits_{\tau \in \mathbb{R}}\Vert \tau^{-1}s_{k-1}-y_{k-1} \Vert或\tau_k=\mathop{argmin}\limits_{\tau \in \mathbb{R}}\Vert s_{k-1}-\tau y_{k-1} \Vert$$
即：$$\tau_k=\frac{\Vert s_{k-1} \Vert_2^2}{s_{k-1}^Ty_{k-1}}或\tau_k=\frac{s_{k-1}^Ty_{k-1}}{\Vert y_{k-1} \Vert_2^2}$$
而在本文的算法中，我们仿照BB法：$s_{k-1}=x_k-x_{k-1},y_{k-1}=g_k^L-g_{k-1}^L.$$(y_{k-1}之所以这样取是为了仿照BB法中y_{k-1}等于迭代方向的差)$,仿照BB方法步长的取值主要有以下四种：
$$\tau_k^{LBB}=\frac{\Vert s_{k-1} \Vert_2^2}{s_{k-1}^Ty_{k-1}}$$
$$\tau_k^{SBB}=\frac{s_{k-1}^Ty_{k-1}}{\Vert y_{k-1} \Vert_2^2}$$
$$ \tau_k^{ABB}=\left\{
\begin{array}{rcl}
\tau_k^{LBB} & , & if \quad k为偶数\\
\tau_k^{SBB} & , & if \quad k为奇数
\end{array} \right. $$
$$ \tau_k^{ADBB}=\left\{
\begin{array}{rcl}
\tau_k^{LBB} & , & if \frac{tau_k^{SBB}}{tau_k^{LBB}}< \gamma \in (0,1)\\
\tau_k^{SBB} & , & otherwise
\end{array} \right. $$
___________________________________________________________________________
算法流程：
该论文经过收敛性分析，将自适应非单调线性搜索法则与上文的迭代更新方法结合，得到自适应可行BB类算法：
Step1（设置参数）：
$(i)$给定$x_0,k:=1,\mathop{\tau_0}\limits^{\_},\epsilon>0,0<\sigma<1,0<\delta<1;$
$(ii)$给定正整数$P>M>L$和常数$\gamma_1=M/L,\gamma_2=P/M,0<\sigma_1<\sigma_2<1;$
$(iii)$设$l:=0,p:=0,f_min=f_r=f_c:=f(x_0).$
Step2（停机条件）：如果$\Vert g_k^L \Vert \leq \epsilon$，则停止算法.
Step3：如果$k=0$，则找到满足下式的最小非负整数$i_0$:
$$f(Y(\delta^{i_0}\mathop{\tau_0}\limits^{\_},x_0)) \leq f(x_0)-\delta\sigma^{i_0}\mathop{\tau_0}\limits^{\_}\Vert g_k^L \Vert^2$$
并设$\tau=\sigma^{i_0}\mathop{\tau_0}\limits^{\_}$；否则，设$\tau_k^{(0)}$为某一BB类步长且
$$\tau_k^{(1)}=max\{\tau_{min},min\{\tau_k^{(0)},\tau_{max}\}\}$$
Step4：如果$k\geq 1$，根据参考论文[1]中的算法2.1计算$\tau_k$并更新$f_r,f_{min}.$
Step5：根据本文上述的更新公式计算$x_{k+1}=Y(\tau_k,x_k)$，并设$k:=k+1$，转到Step2.
注意上述Step4中参考论文[1]中的算法2.1，也可以看我的随笔：自适应的两点步长梯度法 - 来者可追2019 - 博客园 (cnblogs.com)中的第四段：改进的非单调搜索方法
___________________________________________________________________________
参考论文：
[1] Y.H. Dai and H.C. Zhang, Adaptive two-point stepsize gradient algorithm, Numer. Algorithms 27 (2001), pp. 377–385.
[2] Bo Jiang & Yu-Hong Dai (2013) Feasible Barzilai–Borwein-like methods for extreme symmetric eigenvalue problems, Optimization Methods and Software, 28:4, 756-784, DOI: 10.1080/10556788.2012.656115