网站服务器 试用,项目之家app,微信crm软件,网站建设A系列套餐报价Hessian矩阵逆矩阵的近似
一、拟牛顿法的基本思路 令H0,H1,H2,…表示Hessian矩阵逆矩阵F(x(k))−1的一系列近似矩阵。我们要讨论的是这些近似矩阵应该满足的条件#xff0c;这是拟牛顿法的基础。首先#xff0c;假定目标函数f的Hessian矩阵F(x)是常数矩阵#xff0c;与x无关…Hessian矩阵逆矩阵的近似
一、拟牛顿法的基本思路 令H0,H1,H2,…\boldsymbol{H_0,H_1, H_2}, \dots表示Hessian矩阵逆矩阵F(x(k))−1\boldsymbol{F}(\boldsymbol{x}^{(k)})^{-1}的一系列近似矩阵。我们要讨论的是这些近似矩阵应该满足的条件这是拟牛顿法的基础。首先假定目标函数ff的Hessian矩阵F(x)\boldsymbol{F(x)}是常数矩阵与x\boldsymbol{x}无关即目标函数是二次型函数F(x)QQQT\boldsymbol{F(x) = Q， Q=Q}^T则
g(k1)−g(k)Q(x(k1)−x(k))\boldsymbol{g}^{(k+1)} - \boldsymbol{g}^{(k)} = \boldsymbol{Q}(\boldsymbol{x}^{(k+1)}- \boldsymbol{x}^{(k)})令 Δg(k)g(k1)−g(k)Δx(k)x(k1)−x(k)\Delta\boldsymbol{g}^{(k)} = \boldsymbol{g}^{(k+1)} - \boldsymbol{g}^{(k)} \\
\Delta\boldsymbol{x}^{(k)} = \boldsymbol{x}^{(k+1)}- \boldsymbol{x}^{(k)}可得 Δg(k)QΔx(k)\Delta\boldsymbol{g}^{(k)} = \boldsymbol{Q}\Delta\boldsymbol{x}^{(k)}记对称正定实矩阵H0\boldsymbol{H_0}作为近似矩阵的初始矩阵在给定的kk下，矩阵Q−1\boldsymbol{Q}^{-1}应该满足 Q−1Δg(i)Δx(i),0≤i≤k\boldsymbol{Q}^{-1}\Delta\boldsymbol{g}^{(i)} = \Delta\boldsymbol{x}^{(i)} , \quad 0 \le i \le k 因此近似矩阵Hk1\boldsymbol{H_{k+1}}应该满足 Hk1Δg(i)Δx(i),0≤i≤k\boldsymbol{H}_{k+1}\Delta\boldsymbol{g}^{(i)} = \Delta\boldsymbol{x}^{(i)} , \quad 0 \le i \le k 如果共展开nn次迭代，则共产生nn个迭代方向Δx(0),Δx(1),…,Δx(n−1)\Delta\boldsymbol{x}^{(0)}, \Delta\boldsymbol{x}^{(1)}, \dots, \Delta\boldsymbol{x}^{(n-1)}。由此可得Hn\boldsymbol{H}_{n}应该满足条件 HnΔg(0)Δx(0)HnΔg(1)Δx(1)⋮HnΔg(n−1)Δx(n−1)\boldsymbol{H}_{n} \Delta\boldsymbol{g}^{(0)} = \Delta\boldsymbol{x}^{(0)} \\
\boldsymbol{H}_{n} \Delta\boldsymbol{g}^{(1)} = \Delta\boldsymbol{x}^{(1)} \\
\vdots \\
\boldsymbol{H}_{n} \Delta\boldsymbol{g}^{(n-1)} = \Delta\boldsymbol{x}^{(n-1)} \\将其改写为 Hn[Δg(0),Δg(1),…,Δg(n−1)][Δx(0),Δx(1),…,Δx(n−1)]\boldsymbol{H}_{n} [\Delta\boldsymbol{g}^{(0)}, \Delta\boldsymbol{g}^{(1)}, \dots, \Delta\boldsymbol{g}^{(n-1)}]= [\Delta\boldsymbol{x}^{(0)}, \Delta\boldsymbol{x}^{(1)}, \dots, \Delta\boldsymbol{x}^{(n-1)}]矩阵Q\boldsymbol{Q}能够满足 Q[Δx(0),Δx(1),…,Δx(n−1)][Δg(0),Δg(1),…,Δg(n−1)]\boldsymbol{Q} [\Delta\boldsymbol{x}^{(0)}, \Delta\boldsymbol{x}^{(1)}, \dots, \Delta\boldsymbol{x}^{(n-1)}]= [\Delta\boldsymbol{g}^{(0)}, \Delta\boldsymbol{g}^{(1)}, \dots, \Delta\boldsymbol{g}^{(n-1)}]和 Q−1[Δg(0),Δg(1),…,Δg(n−1)][Δx(0),Δx(1),…,Δx(n−1)]\boldsymbol{Q}^{-1} [\Delta\boldsymbol{g}^{(0)}, \Delta\boldsymbol{g}^{(1)}, \dots, \Delta\boldsymbol{g}^{(n-1)}]= [\Delta\boldsymbol{x}^{(0)}, \Delta\boldsymbol{x}^{(1)}, \dots, \Delta\boldsymbol{x}^{(n-1)}]这说明 如果[Δg(0),Δg(1),…,Δg(n−1)][\Delta\boldsymbol{g}^{(0)}, \Delta\boldsymbol{g}^{(1)}, \dots, \Delta\boldsymbol{g}^{(n-1)}]非奇异那么矩阵Q−1\boldsymbol{Q}^{-1} 能够在nn次迭代之后唯一确定， 即
Q−1=Hn=[Δx(0),Δx(1),…,Δx(n−1)][Δg(0),Δg(1),…,Δg(n−1)]−1
\boldsymbol{Q}^{-1} = \boldsymbol{H}_{n} = [\Delta\boldsymbol{x}^{(0)}, \Delta\boldsymbol{x}^{(1)}, \dots, \Delta\boldsymbol{x}^{(n-1)}][\Delta\boldsymbol{g}^{(0)}, \Delta\boldsymbol{g}^{(1)}, \dots, \Delta\boldsymbol{g}^{(n-1)}]^{-1}由此可得如果Hn \boldsymbol{H}_{n}能够使得方程HnΔg(i)Δx(i),0≤i≤n−1 \boldsymbol{H}_{n}\Delta\boldsymbol{g}^{(i)} = \Delta\boldsymbol{x}^{(i)} , \quad 0 \le i \le n-1 成立 那么利用迭代公式x(k1)x(k)−αkHkgk,αkargmina≥0f(x(k)−αHkgk)\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)} - \alpha_k \boldsymbol{H}_{k} \boldsymbol{g}_{k}, \alpha_k = \arg \min_{a \ge 0}f(\boldsymbol{x}^{(k)} - \alpha \boldsymbol{H}_{k} \boldsymbol{g}_{k})求解nn维二次优化问题，可得x(n+1)=x(n)−αnHngn\boldsymbol{x}^{(n+1)}=\boldsymbol{x}^{(n)} - \alpha_n \boldsymbol{H}_{n} \boldsymbol{g}_{n},这与牛顿法的迭代公式是一致的 说明能够在n1n+1次迭代内完成求解。二、 拟牛顿法的的迭代公式 拟牛顿法的的迭代公式为
d(k)−Hkg(k)αkargmina≥0f(x(k)αd(k))x(k1)x(k)αkd(k)\boldsymbol{d}^{(k)} = - \boldsymbol{H}_{k}\boldsymbol{g}^{(k)} \\
\alpha_k = \arg \min_{a \ge 0}f(\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)}) \\
\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)} + \alpha_k\boldsymbol{d}^{(k)}其中H0,H1,H2,…\boldsymbol{H_0,H_1, H_2}, \dots是对称矩阵。 目标函数为二次型函数时它们必须满足 Hk1Δg(i)Δx(i),0≤i≤k\boldsymbol{H}_{k+1}\Delta\boldsymbol{g}^{(i)} = \Delta\boldsymbol{x}^{(i)} , \quad 0 \le i \le k 其中 Δx(i)x(i1)−x(i)αid(k),Δg(i)g(i1)−g(i)QΔx(i)\Delta\boldsymbol{x}^{(i)} = \boldsymbol{x}^{(i+1)}- \boldsymbol{x}^{(i)} = \alpha_i \boldsymbol{d}^{(k)}, \Delta\boldsymbol{g}^{(i)} = \boldsymbol{g}^{(i+1)}- \boldsymbol{g}^{(i)} =\boldsymbol{Q}\Delta\boldsymbol{x}^{(i)} 实际上拟牛顿法也是一种共轭方法。三、定理 将拟牛顿法应用到二次型问题中 Hessian矩阵为QQT\boldsymbol{Q} = \boldsymbol{Q}^T 对于0≤k≤n−10 \le k \le n-1 , 有
Hk1Δg(i)Δx(i),0≤i≤k\boldsymbol{H}_{k+1}\Delta\boldsymbol{g}^{(i)} = \Delta\boldsymbol{x}^{(i)} , \quad 0 \le i \le k 其中Hk1HTk1\boldsymbol{H}_{k+1} = \boldsymbol{H}_{k+1}^T。如果αi≠0,0≤i≤k\alpha_i \ne 0, 0 \le i \le k , 那么d(0)d(1)⋯d(k1)\boldsymbol{d}^{(0)}，\boldsymbol{d}^{(1)}，\dots，\boldsymbol{d}^{(k+1)}是Q\boldsymbol{Q}共轭的。由以上定理可知对于nn维二次型问题，拟牛顿法最多经过nn部迭代即可求出最优解。注意矩阵Hk\boldsymbol{H}_{k}并不能唯一确定这就给计算矩阵Hk\boldsymbol{H}_{k}的自由发挥空间。
