牛顿法和拟牛顿法

$/quad$牛顿法（Newton method）和拟牛顿法（quasi Newton method）是求解无约束最优化问题的常用方法，有收敛速度快的优点。

1. 牛顿法

考虑无约束最优化问题 minx∈Rnf(x) $$min_{x/in R^n} f(x)$$ 其中x∗$x^*$为目标函数极小点。 假设f(x)$f(x)$有二阶连续偏导数，若第k次迭代值为x(k)$x^{(k)}$,则可将f(x)$f(x)$在x(k)$x^{(k)}$附近进行二阶泰勒展开： f(x)=f(x(k))+gTk(x−x(k))+12(x−x(k))TH(x(k))(x−x(k)) $$f(x)=f(x^{(k)})+g_k^T(x-x^{(k)})+/frac{1}{2}(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)})$$ 这里，gk=g(x(k))=▽f(x(k))$g_k=g(x^{(k)})=/bigtriangledown f(x^{(k)})$是f(x)$f(x)$的梯度向量在点x(k)$x^{(k)}$的值，H(x(k))$H(x^{(k)})$是f(x)$f(x)$的海塞矩阵 H(x)=[∂2f∂xi∂xj]n×n $$H(x)=[/frac{/partial^2f}{/partial x_i/partial x_j}]_{n/times n}$$ 在点x(k)的值。$x^{(k)}的值。$当H(x(k))$H(x^{(k)})$是正定矩阵是，函数f(x)$f(x)$的极值为极小值。 假设x(k)$x^{(k)}$满足： ▽f(x(k+1))=0 $$/bigtriangledown f(x^{(k+1)})=0$$ 对f(x)$f(x)$求导，得 ▽f(x)=gk+Hk(x−x(k)) $$/bigtriangledown f(x) = g_k+H_k(x-x^{(k)})$$ 其中Hk=H(x(k))$H_k=H(x^{(k)})$,则 gk+Hk(x(k+1)−x(k))=0 $$g_k+H_k(x^{(k+1)}-x^{(k)})=0$$ 因此，x(k+1)=x(k)−H−1kgk$x^{(k+1)}=x^{(k)}-H_k^{-1}g_k$ (**), 或者x(k+1)=x(k)+pk$x^{(k+1)}=x^{(k)}+p_k$,其中，Hkpk=−gk$H_kp_k=-g_k$ 式（**）作为迭代公式的算法就是牛顿法。 牛顿法： 输入：目标函数f(x),梯度g(x)=▽f(x),海塞矩阵H(x),精读要求ϵ;$f(x),梯度g(x)=/bigtriangledown f(x), 海塞矩阵H(x),精读要求/epsilon;$ 输出：f(x)的极小点x∗.$f(x)的极小点x^*.$ （1）取初始点x(0)$x^{(0)}$,置k=0，$k=0，$ （2）计算gk=g(x(k))$g_k=g(x^{(k)})$, （3）若||gk||<ϵ$||g_k||/lt /epsilon$,则停止计算，得近似解x∗=x(k)$x^*=x^{(k)}$, （4）计算Hk=H(x(k)),并求pk$H_k=H(x^{(k)}),并求p_k$ Hkpk=−gk $$H_kp_k=-g_k$$ （5）置x(k+1)=x(k)+pk$x^(k+1)=x^{(k)}+p_k$， （6）置k=k+1$k=k+1$,转至（2）。 步骤（4）要求H−1k$H_k^{-1}$，计算复杂，所以有其他改进的方法，比如拟牛顿法等。

待续……