最优化算法3【拟牛顿法1】

牛顿法存在的问题

1. 计算量大，每次都需要计算HESSE矩阵，对于自变量维数较高的优化函数，计算量是相当大的；


2. HESSE矩阵可能存在不正定的问题，此时求得的迭代方向可能不是下降方向；

为了解决上述问题，需要求HESSE矩阵近似矩阵\(B\)

算法分析

将函数在\(x_{k+1}\)处二阶展开：

\[f(x)=f(x_{k+1})+g_{k+1}^T(x-x_{k+1})+\frac{1}{2}(x-x_{k+1})^TG_{k+1}(x-x_{k+1})
\]

上式求导等于0，得：

\[g_k=g_{k+1}+G_{k+1}(x-x_{k+1})
\]

令\(s_k=x_{k+1}-x_k\),\(y_k=g_{k+1}-g_k\),则：

\[G_{k+1}s_k\approx y_k
\]

近似矩阵需要满足上述条件；

为了使得迭代计算简单，可以设计，使用秩1矩阵更新\(B\)

\[B_{k+1}=B_k+E_k
\]

取\(E_k=\alpha \mu_k\mu_k^T\)

经过计算可以得出HESSE矩阵逆矩阵近似矩阵迭代公式：

\[H_{k+1}=H_k+\frac{(s_k-H_ky_k)(s_k-H_ky_k)^T}{(s_k-H_ky_k)^Ty_k}
\]

算法

输入：梯度计算公式\(gfun\),容许误差：\(\epsilon\),初始值\(x_0\),初始化HESSE阵逆矩阵

\(step0:求梯度g_k,if\, abs(g_k)<\epsilon,break; \quad else \, to\, step 1;\)

\(step1:d_k=-H_kg_k;\quad x_{k+1}=x_k+\alpha d_k; \quad to\, step2;\)

\(step2:求g_{k+1} \quad 求H_{k+1} \quad to\, step3;\)

\(step3:k=k+1 \quad to\, step0;\)

reflect

主要思路：设计使用秩1矩阵更新HESSE矩阵，节省了计算二阶导数的计算量；同时保证了其正定性；