最优化算法

下降算法

1 下降迭代算法

步骤

• 给出初始点$x^{(0)},k\leftarrow0$
• 判断$x^{(k)}$是否为极小点或近似极小点，是则停止，否则下一步
• 按照某种规则确定搜索方向$p^{(k)}$
• 按照某种规则确定搜索步长$\lambda_k$得到$x^{(k+1)}=x^{(k)}+\lambda_kp^{(k)}$使得$f(x^{(k)}+\lambda_kp^{(k)})<f(x^{(k)})$ ，$\to$ ②

线性搜索(一维搜索)

最优步长：使得目标函数值下降最多的$\lambda_k=argminf(x^{(k)}+\lambda p^{(k)})$

求解以$\lambda$为变量的一元函数$f(x^{(k)}+\lambda p^{(k)})$的极小值点$\lambda_k$

性质:在搜索方向上所得最优点处的梯度与搜索方向正交 $\nabla f(x^{(k+1)})^Tp^{(k)})=0$

$\phi(\lambda)=f(x^{(k)}+\lambda p^{(k)})\\\phi(\lambda)’=\nabla f(x^{(k)}+\lambda p^{(k)})^Tp^{(k)}=\nabla f(x^{(k+1)})^Tp^{(k)}=0$

终止条件

• 绝对误差

  $||x^{(k+1)}-x^{(k)}||<\epsilon_1,\quad ||f(x^{(k+1)})-f(x^{(k)})||<\epsilon_2$

• 相对误差

  $\frac{||x^{(k+1)}-x^{(k)}||}{||x^{(k)}||}<\epsilon_3,\quad \frac{||f(x^{(k+1)})-f(x^{(k)})||}{||f(x^{(k)})||}<\epsilon_4$

• 目标函数梯度的模

  $||\nabla f(x^{(k)})||\leq \epsilon_5$

收敛速度

设序列$\{x^{(k)}\}$收敛于 $x^*$ 若存在于迭代次数$k$无关的数 $0<\beta<\infty$ 和 $\alpha \geq1$ 使得 $k$ 从某个 $k_0>0$ 开始都有 $||x^{(k+1)}-x^*$ $||\leq\beta||x^{(k)}-x^*$ $||^{\alpha} $ 成立，则 $\{x^{(k)}\}$ 的收敛阶为 $\alpha$ 或 $\{x^{(k)}\}$ 为 $\alpha$ 阶收敛

• 二阶收敛 $\alpha=2$
• 超线性收敛 $1<\alpha<2$
• 线性收敛 $\alpha=1$且$0<\beta<1$

线性收敛速度较慢，二阶收敛速度较快

2 Fabonacci

单变量最优化问题(一维最优化问题)

$minimize\quad f(x)\\subject\; to \quad x\in R$

步骤

• 确定试点个数$n$：根据相对精度$\delta$确定$F_n$，然后查表得$n$

• 选取前两个试算点的位置，第一次缩短

  $\begin{cases}t_1=a_0+\frac{F_n-2}{F_n}(b_0-a_0)=b_0-\frac{F_n-1}{F_n}(b_0-a_0)\\t_1’=a_0+\frac{F_n-1}{F_n}(b_0-a_0) \end{cases}$

• 计算函数值$f(t_1)$和$f(t_1’)$ 并比较

  • $f(t_1)<f(t_1’)$

    $a_1=a_0,b_1=t_1’,\\t_2=b_1-\frac{F_n-2}{F_n-1}(b_1-a_1),t_2’=t_1$

  • $f(t_1)>f(t_1’)$

    $a_1=t_1,b_1=b_0,\\t_2=t_1’,t_2’=a_1+\frac{F_n-2}{F_n-1}(b_1-a_1)$

• 计算函数值$f(t_2)$和$f(t_2’)$

• 当进行到$k=n-1$时$t_{n-1}=t’_{n-1}=\frac{a_{n-2}+b_{n-2}}{2}$

  此时无法比较函数值的大小以确定最终区间，因此此时取

  $\begin{cases}t_{n-1}=\frac{a_{n-2}+b_{n-2}}{2}\\t_{n-1}’=a_{n-2}+(\frac12+\epsilon)(b_{n-2}-a_{n-2}) \end{cases}$

  在$t_{n-1}$=和$t’_{n-1}$两点中，以函数值较小者为近似极小点，相应函数值为近似极小值，最终区间$[a_{n-2},t’_{n-2}]$或$[t_{n-1},b_{n-2}]$

3 0.168

用不变的区间缩短率0.618代替Fibonacci法中每次不同的缩短率

• 每次的缩短率$\mu=0.618$最后的区间长度$(b_0-a_0)\mu^{n-1}$
• 当已知缩短精度$\delta$时，由$\mu^{n-1}\leq \delta$求解$n$

步骤

• 置初始区间$[a_0,b_0]$及精度要求$L>0$，计算试探点$\lambda_1(t_1)$和$\mu_1(t_1’)$，并计算其函数值

  $\lambda_1=b_0-0.618(b_0-a_0)=a_0+0.382(b_0-a_0)=0.618a_0+0.382b_0$

  $\mu_1=a_0+0.618(b_0-a_0)=0.382a_0+0.618b_0$

• 若$b_k-a_k<L$ end , or:

  • 当$f(\lambda_k)>f(\mu_k)$时

    $a_{k+1}=\lambda_k,\;b_{k+1}=b_k,\;\lambda_{k+1}=\mu_k,\;\mu_{k+1}=a_{k+1}+0.618(b_{k+1}-a_{k+1})$

  • 当$f(\lambda_k)<f(\mu_k)$时

    $a_{k+1}=a_k,\;b_{k+1}=\mu_k,\;\mu_{k+1}=\lambda_k,\;\mu_{k+1}=b_{k+1}-0.618(b_{k+1}-a_{k+1})$

• 迭代计算

Fibonacci斐波那契数列

$1,1,2,3,5,8,13,21,34,55,89,144…$

数列从第三项起任意一项都是前面两项之和，即$F_{n+2}=F_{n+1}+F_n$

• 若数列$\{F_n\}$为斐波那契数列，则$lim_{n\to \infty} \frac{F_{n+1}}{F_n}=\frac{1+\sqrt5}2$ ，$\frac2{1+\sqrt5}$为黄金分割比

• 若数列$\{F_n\}$为斐波那契数列，则数列前$n$项和为$S_n=\frac1{\sqrt5}[(\frac{1+\sqrt5}2)^{n+2}-(\frac{1-\sqrt5}2)^{n+2}]-1$

  $S_n=F_1+F_2+F_3+…+F_n=F_1+(F_3-F_1)+(F_4-F_2)+(F_5-F_3)+…+(F_{n+1})-(F_{n-1})\\=-F_2+F_n+F_{n+1}=F_{n+2}-1$

• 若数列$\{F_n\}$为斐波那契数列，$A,B,C,D$为四个连续的斐波那契数，则有$C^2-B^2=A\times D$

最优化算法

• 下降方向

假设$f:R^n\to R$对于$x\in dom f$，使得对于任意$\overline{\alpha}>0,d\in R^n$有$f(x+\alpha d)<f(x),\alpha \in(0,\overline{\alpha})$，则$d$ 为$f$的一个下降方向

【$\nabla f(x)^Td<0$的$d$为$f$的一个下降方向】

• 可行方向

假设$f:R^n\to R$对于$x\in dom f$，若存在$\alpha>0,d\in R^n$使得$f(x+\alpha d)\in dom f$，则$d$ 为$f$的一个可行方向

• 局部最优解

假设$f:R^n\to R$ 在点 $x^* \in R$ 处可微。若 $x^*$ 是无约束问题的局部最优解，则 $\nabla f(x^*)=0$

$x^*$ 为函数 $f$ 的驻点或平稳点。函数的一个驻点可以是极小点也可以是极大点，也可以不是极小点也不是极大点，此时成为鞍点。

$x^*$是无约束问题的局部最优解的必要条件是 $x^*$ 是其目标函数 $f$ 的驻点

• 严格局部最优解

假设$f:R^n\to R$在点 $x^*\in R$ 的Hessian矩阵 $\nabla^2f(x^*)$ 存在，若 $\nabla f(x^*)=0$ , 并且 $\nabla^2f(x^*)$正定，则 $x^*$ 是无约束问题的严格局部最优解

• 整体最优解

假设$f:R^n\to R$，$x^* \in R$，$f$ 是 $R^n$ 上的可微凸函数，若有 $\nabla f(x^*)=0$ 则 $x^*$ 是无约束问题的整体最优解

一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，它的目标函数的驻点就是它的整体最优解。

无约束最优化问题

$minimize\quad f(x)\\subject\;to\quad x\in R^n$

假设$f(x)$有一阶连续偏导数，具有极小点$x^*$ 以$x^{(k)}$表示下降算法中极小点的第$k$次近似，则第$k+1$次近似点为第$k$点处沿某下降方向$d^{(k)}$取$x^{(k+1)}=x^{(k)}+\alpha d^{(k)}$

• 确定搜索方向

• 确定搜索步长

负梯度方向

$f(x^{(k)}+\alpha d^{(k)})=f(x^{(k)})+\alpha \nabla f(x^{(k)})^Td^{(k)}+o(\alpha)$

选择使得目标值得到尽可能大改善的方向，也就是$\nabla f(x^{(k)})^Td^{(k)}$最小的方向

$\nabla f(x^{(k)})^Td^{(k)}=||\nabla f(x^{(k)})^T||·||d^{(k)}||cos(\nabla f(x^{(k)})^T,d^{(k)})$

当余弦值最小时得最小值，此时夹角为$180^\circ$

$d^{(k)}=-\nabla f(x^{(k)})^T$ 即负梯度方向

对于等值线是圆的问题，不管初始点在哪里，负梯度方向总是指向圆心，因此一次迭代即可得到最小值点

1 近似最佳步长

• 搜索方向：负梯度方向

  $d^{(k)}=-\nabla f(x^{(k)})^T$

• 搜索步长：近似最佳步长

若$f(x)$有二阶连续偏导数，在$x^{(k)}$作$f(x^{(k)}-\lambda \nabla f(x^{(k)})^T)$泰勒展开得

$f(x^{(k)}-\lambda \nabla f(x^{(k)})^T) \approx f(x^{(k)})^T \lambda \nabla f(x^{(k)})+\frac12 \lambda \nabla f(x^{(k)})^TH(x^{(k)})\lambda \nabla f(x^{(k)})$

对$\lambda$求导并令其等$0$ 得近似最佳步长

$\lambda_k=\frac{\nabla f(x^{(k)})^T\nabla f(x^{(k)})}{\nabla f(x^{(k)})^TH(x^{(k)})\nabla f(x^{(k)})}$

【若将搜索方向规格化为$d^{(k)}=\frac{-\nabla f(x^{(k)})^T}{||\nabla f(x^{(k)})^T||}$，此时$\lambda_k=\frac{\nabla f(x^{(k)})^T\nabla f(x^{(k)})||\nabla f(x^{(k)})^T||}{\nabla f(x^{(k)})^TH(x^{(k)})\nabla f(x^{(k)})}$ 】

2 最速下降法（梯度法）

• 搜索方向：负梯度方向

  $d^{(k)}=-\nabla f(x^{(k)})^T$

• 搜索步长：最速下降法

线性搜索（一维搜索） 由此确定的步长为最优步长

使得目标函数值下降最多的$\lambda_k=argmin\;f(x^{(k)}-\lambda \nabla f(x^{(k)})^T)$

求解以$\lambda$为变量的一元函数$\phi(\lambda)=f(x^{(k)}-\lambda \nabla f(x^{(k)})^T)$的极小点$\lambda_k$

步骤

• 初始点$x^{(0)}\in R^n$精度$\epsilon>0,k\leftarrow 0$
• 若$||\nabla f(x^{(k)})||\leq \epsilon$ end. 解为$x^{(k)}$ or $d^{(k)}=-\nabla f(x^{(k)})$
• 线性搜索确定步长$\lambda_k=argmin\;f(x^{(k)}-\lambda \nabla f(x^{(k)})^T)$
• 令 $x^{(k+1)}=x^{(k)}+\lambda_k d^{(k)},k=k+1$ $\to $ 步骤②

性质

• 如果目标函数等值线为同心圆或同心球面，则负梯度方向指向圆心或球心，从任意初始点一步可达极小值点
• $x$处负梯度方向仅为$x$点附近有最速下降性
• 对于二元二次函数，等值线为椭圆，使用最速下降法搜索路径呈直角锯齿状

3 牛顿法

给二次可微函数寻找其一阶微分等于零的驻点

• 搜索方向：牛顿方向
• 搜索步长：最佳步长 $\lambda_k=argminf(x^{(k)}+\lambda d^{(k)})$

若$f(x)$有二阶连续偏导数，$x^{(k)}$为其极小点的某一近似，做$f(x^{(k)})$的二阶泰勒展开

$f(x)\approx f(x^{(k)})+\nabla f(x^{(k)})^T \Delta(x)+\frac12 \Delta(x)^TH(x^{(k)})\Delta(x)$

$\Delta(x)=x-x^{(k)}$

极值点梯度满足$\nabla f(x)\approx \nabla f(x^{(k)})+H(x^{(k)})\Delta(x)=0$

$\therefore x=x^{(k)}-H(x^{(k)})^{-1}\nabla f(x^{(k)})$

当$f(x)$为二次函数，从任一点$x^{(k)}$出发只需一步即可求出极小点

牛顿方向

$d^{(k)}=-H(x^{(k)})^{-1}\nabla f(x^{(k)})$ 为搜索方向，即牛顿方向

步骤

• 初始点$x^{(0)}\in R^n$精度$\epsilon>0,k\leftarrow 0$

• 若$||\nabla f(x^{(k)})||\leq \epsilon$ end. 解为$x^{(k)}$ or 计算

  $\nabla f(x^{(k)})+H(x^{(k)})^{-1}d^{(k)}=0$ 得

  $d^{(k)}=-H(x^{(k)})^{-1}\nabla f(x^{(k)})$

• 线性搜索确定步长$\lambda_k=argmin\;f(x^{(k)}-\lambda H(x^{(k)})^{-1}\nabla f(x^{(k)}))$

• 令 $x^{(k+1)}=x^{(k)}+\lambda_k d^{(k)},k=k+1$ $\to $ 步骤②

3 拟牛顿法

构造一个矩阵$B^{(k)}$, 用它逼近矩阵$H(x^{(k)})$，就可以不计算$H(x^{(k)})$，其逆矩阵$\overline{H}^{(k)}$ 可以y逼近$H(x^{(k)})^{-1}$

近似矩阵$B^{(k)}$满足

• 某种意义上$B^{(k)}\approx H(x^{(k)})$ ，拟牛顿方向是牛顿方向的近似
• 所有$B^{(k)}$对称正定，保证算法产生方向为$x^{(k)}$处下降方向
• 矩阵$B^{(k)}$容易计算

拟牛顿条件

若$f(x)$有二阶连续偏导数，$x^{(k+1)}$为其极小点的某一近似，作$f(x^{(k+1)})$的二阶泰勒展开得

$f(x)\approx f(x^{(k+1)})+\nabla f(x^{(k+1)})^T(x-x^{(k+1)})+\frac12 (x-x^{(k+1)})^TH(x^{(k+1)})(x-x^{(k+1)})$

$\implies \nabla f(x)\approx \nabla f(x^{(k+1)})+H(x^{(k+1)})(x-x^{(k+1)})$

当$x=x^{(k)}$时

$\nabla f(x^{(k)}) \approx f(x^{(k+1)})+H(x^{(k+1)})(x^{(k)}-x^{(k+1)})$

【$B^{(k+1)}$的合理逼近是当用$B^{(k+1)}$替换$H(x^{(k+1)})$时取等号】

$B^{(k+1)}(x^{(k+1)}-x^{(k)})=\nabla f(x^{(k+1)})-\nabla f(x^{(k)})$

拟牛顿方程（割线方程） $B^{(k)}s^{(k)}=y^{(k)}$

其中$s^{(k)}=x^{(k+1)}-x^{(k)},y^{(k)}=\nabla f(x^{(k+1)})-\nabla f(x^{(k)})$

$\implies \overline{H}^{(k+1)}y^{(k)}=s^{(k)}$

$s^{(k)}=x^{(k+1)}-x^{(k)}=\lambda_kd^{(k)}$ 说明$B^{(k+1)}$与$H(x^{(k)})$沿$d^{(k)}$方向近似

即拟牛顿方程规定的拟牛顿方向是牛顿方向的一个近似

1.DFP

逼近逆矩阵

构造一个矩阵逼近Hessian矩阵，其逆矩阵可逼近Hessian矩阵逆矩阵

$B^{(k)} \approx H(x^{(k)})$

对$\overline{H}(x^{(k)})$做轻微的扰动以产生$\overline{H}(x^{(k+1)})$

$\overline{H}^{(k+1)}=\overline{H}^{(k)}+\Delta \overline{H}^{(k)}$

由于$\Delta \overline{H}(x^{(k)})$为对称矩阵，则设

$\Delta \overline{H}^{(k)}=\alpha_kuu^T+\beta_kvv^T$

代入$\overline{H}^{(k+1)}y^{(k)}=s^{(k)}$

$\overline{H}^{(k)}y^{(k)}+\alpha_kuu^Ty^{(k)}+\beta_kvv^Ty^{(k)}=s^{(k)}$

由于$u^Ty^{(k)}$和$v^Ty^{(k)}$均为常数

$\implies \alpha_k(u^Ty^{(k)})u+\beta_k(v^Ty^{(k)})v=s^{(k)}-\overline{H}^{(k)}y^{(k)}$

由于很难求解到唯一解，因此对于求解$u,v$

令$u=s^{(k)},v=\overline{H}^{(k)}y^{(k)}$

得$\alpha_k((s^{(k)})^Ty^{(k)})s^{(k)}+\beta_k((y^{(k)})^T\overline{H}^{(k)}y^{(k)})\overline{H}^{(k)}y^{(k)}=s^{(k)}-\overline{H}^{(k)}y^{(k)}$

解得$\alpha_k=\frac1{(y^{(k)})^Ts^{(k)}},\beta_k=\frac1{(y^{(k)})^T \overline{H}^{(k)}y^{(k)}}$

则迭代方程为 $\overline{H}^{(k+1)}$ $=\overline{H}^{(k)}+\Delta \overline{H}^{(k)}\\=\overline{H}^{(k)}+\frac{s^{(k)}(s^{(k)})^T}{(y^{(k)})^Ts^{(k)}}-\frac{\overline{H}^{(k)}y^{(k)}(y^{(k)})^T\overline{H}^{(k)}}{(y^{(k)})^T\overline{H}^{(k)}y^{(k)}}$

【保证 $\overline{H}^{(0)}$ 对称正定, 则之后迭代构造出的所有矩阵均对称正定】

步骤

• 给定初始点$x^{(0)}\in R^n$,精度$\epsilon >0,k\leftarrow 0$

• 若$||\nabla f(x^{(k)})||\leq \epsilon$ end. 解为$x^{(k)}$ or 计算

  $\overline{H}^{(k)} = \begin{cases} 1& \text{k=0} \ \overline{H}^{(k-1)}+\frac{s^{(k-1)}(s^{(k-1)})^T}{(y^{(k-1)})^Ts^{(k-1)}}-\frac{\overline{H}^{(k-1)}y^{(k-1)}(y^{(k-1)})^T\overline{H}^{(k-1)}}{(y^{(k-1)})^T\overline{H}^{(k-1)}y^{(k-1)}} & \text{k>0} \end{cases}$

  求得$d^{(k)}=-\overline{H}^{(k)}\nabla f(x^{(k)})$

• 线性搜索确定步长$\lambda_k=argmin\;f(x^{(k)}-\lambda \overline{H}(x^{(k)})\nabla f(x^{(k)}))$

• 令 $x^{(k+1)}=x^{(k)}+\lambda_k d^{(k)},k=k+1$ $\to $ 步骤②

2.BFGS

逼近Hessian矩阵

通过产生$B^{(k+1)}$来找对应的逆矩阵

$B^{(k+1)}=B^{(k)}+\Delta B^{(k)}$

由于$\Delta B(x^{(k)})$为对称矩阵，则设

$\Delta B^{(k)}=\alpha_kuu^T+\beta_kvv^T$

代入 $B^{(k)}s^{(k)}=y^{(k)}$ 得

$B^{(k)}s^{(k)}+\alpha_kuu^Ts^{(k)}+\beta_kvv^Ts^{(k)}=y^{(k)}$

由于$u^Ts^{(k)}$和$v^Ts^{(k)}$均为常数

$\implies \alpha_k(u^Ts^{(k)})u+\beta_k(v^Ts^{(k)})v=y^{(k)}-B^{(k)}s^{(k)}$

同样由于很难求解到唯一解，因此对于求解$u,v$

令$u=y^{(k)},v=B^{(k)}s^{(k)}$

得$\alpha_k((y^{(k)})^Ts^{(k)})y^{(k)}+\beta_k((s^{(k)})^TB^{(k)}s^{(k)})B^{(k)}s^{(k)}=y^{(k)}-B^{(k)}s^{(k)}$

解得$\alpha_k=\frac1{(y^{(k)})^Ts^{(k)}},\beta_k=\frac1{(s^{(k)})^T B^{(k)}s^{(k)}}$

则迭代方程为 $B^{(k+1)}$ $=B^{(k)}+\Delta B^{(k)}\\=B^{(k)}+\frac{y^{(k)}(y^{(k)})^T}{(y^{(k)})^Ts^{(k)}}-\frac{B^{(k)}s^{(k)}(s^{(k)})^TB^{(k)}}{(s^{(k)})^TB^{(k)}s^{(k)}}$

步骤

• 给定初始点$x^{(0)}\in R^n$,精度$\epsilon >0,k\leftarrow 0$

• 若$||\nabla f(x^{(k)})||\leq \epsilon$ end. 解为$x^{(k)}$ or 计算

  $B^{(k)} = \begin{cases} 1& \text{k=0} \ B^{(k-1)}+\frac{y^{(k-1)}(y^{(k-1)})^T}{(y^{(k-1)})^Ts^{(k-1)}}-\frac{B^{(k-1)}s^{(k-1)}(s^{(k-1)})^TB^{(k-1)}}{(s^{(k-1)})^TB^{(k-1)}s^{(k-1)}} & \text k \geq 1 \end{cases}$

  求得$d^{(k)}=-(B^{(k)})^{-1} \nabla f(x^{(k)})$

• 线性搜索确定步长$\lambda_k=argmin\;f(x^{(k)}-\lambda (B(x^{(k)})^{-1}\nabla f(x^{(k)}))$

• 令 $x^{(k+1)}=x^{(k)}+\lambda_k d^{(k)},k=k+1$ $\to $ 步骤②

Sherman-Morrison公式

设$A\in R^n$为非奇异方阵，$u,v \in R^n$，若满足$1+v^TA^{-1}u \not= 0$ ，则矩阵$A+uv^T$非奇异，且其逆矩阵为$(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$

由于 $B^{(k+1)}=B^{(k)}+\frac{y^{(k)}(y^{(k)})^T}{(y^{(k)})^Ts^{(k)}}-\frac{B^{(k)}s^{(k)}(s^{(k)})^TB^{(k)}}{(s^{(k)})^TB^{(k)}s^{(k)}}$

连续使用两次$Sherman-Morrison$公式即可求得$B^{(k+1)}$的逆矩阵

$\overline{H}^{(k+1)}$ $=(1-\frac{s^{(k)}(y^{(k)})^T}{(y^{(k)})^Ts^{(k)}})\overline{H}^{(k)}(1-\frac{s^{(k)}(y^{(k)})^T}{(y^{(k)})^Ts^{(k)}})+\frac{s^{(k)}(s^{(k)})^T}{(y^{(k)})^Ts^{(k)}}\\=\overline{H}^{(k)}+\frac{(s^{(k)}-\overline{H}^{(k)}y^{(k)})(s^{(k)})^T+s^{(k)}(s^{(k)}-\overline{H}^{(k)}y^{(k)})^T}{(y^{(k)})^Ts^{(k)}}-\frac{(s^{(k)}-\overline{H}^{(k)}y^{(k)})^Ty^{(k)}}{((y^{(k)})^Ts^{(k)})^2}s^{(k)}(s^{(k)})^T$

其中$\overline{H}^{(k+1)}=(B^{(k+1)})^{-1},\overline{H}^{(k)}=(B^{(k)})^{-1}$

3.Broyden簇

利用$DFP$算法和$BFGS$算法之间存在的对偶关系构造矩阵

$B^{(k+1)}=\alpha_kB^{(k+1)}_{BFGS}+(1-\alpha_k)B^{(k+1)}_{DFP} \ H^{(k+1)}=\alpha_kH^{(k+1)}_{BFGS}+(1-\alpha_k)H^{(k+1)}_{DFP}$