最优化算法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矩阵,节省了计算二阶导数的计算量;同时保证了其正定性;

上一篇:图像处理技术运用(1)-空域图像增强之图像基本运算和灰度变换、直方图技术


下一篇:聊一聊粗糙集(六)