牛顿法存在的问题
- 计算量大,每次都需要计算HESSE矩阵,对于自变量维数较高的优化函数,计算量是相当大的;
- 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矩阵,节省了计算二阶导数的计算量;同时保证了其正定性;