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

牛顿法存在的问题

1. 计算量大，每次都需要计算HESSE矩阵，对于自变量维数较高的优化函数，计算量是相当大的；
2. HESSE矩阵可能存在不正定的问题，此时求得的迭代方向可能不是下降方向；

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

算法分析

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

上式求导等于0，得：

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

近似矩阵需要满足上述条件；
为了使得迭代计算简单，可以设计，使用秩1矩阵更新\(B\)

取\(E_k=\alpha \mu_k\mu_k^T\)
经过计算可以得出HESSE矩阵逆矩阵近似矩阵迭代公式：

算法

输入：梯度计算公式\(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矩阵，节省了计算二阶导数的计算量；同时保证了其正定性；

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

原文：https://www.cnblogs.com/liudianfengmang/p/13537311.html