无约束最优化问题:
在\(x = \bar{x}\)时，f(x)可近似为:
这是\(f (x)\)在\(x = \bar{x}\)处的二次泰勒展开式。其中\(H(\bar{x})= ?^2f(\bar{x})\)
要\(\min ~ ~ ~ f(x)\),则\(?h(x)=0\)，有
设\(H(\bar{x})\)可逆， 则
\(-H(\bar{x})^{-1} ?f(\bar{x})\)称为牛顿方向，或\(x = \bar{x}\)处的牛顿步长。则得牛顿法的迭代公式：
\(\large\color{#70f3ff}{\boxed{\color{brown}{阻尼牛顿法} }}\)
纯牛顿法步长固定为 \(α=1\) ，阻尼牛顿法( damped Newton method or guarded Newton method)的步长\(α\)是不固定的。
[算法] 给定起始点$ x_0\in dom \ f,k=0 $，精度 $\epsilon >0 $,
def newton(f, start):
fun = Function(f)
x = array(start)
g = fun.grad(x)
while fun.norm(x) > epsilon:
G = fun.hesse(x)
d = (-dot(linalg.inv(G), g)).tolist()[0]
alpha = wolfe(f, x, d)
x = x + alpha * array(d)
g = fun.grad(x)
return x
请注意以下几点:
牛顿法的原理是使用函数 \(f(x)\) 的泰勒级数的前面几项来寻找方程 \(f(x)=0\) 的根。
将函数 \(f(x)\) 在 \(x_0\) 处展开成泰勒级数:
取其线性部分，作为 \(f(x)\) 的近似，则可用 \(f(x_0)+f^{‘}(x_0)(x-x_0)=0\) 的解来近似 \(f(x)=0\) 的解，其解为
由于对 \(f(x)\) 的近似只是一阶展开，因此 \(r\) 并非 \(f(x)=0\) 的解，只能说 \(f(x_1)\) 比 \(f(x_0)\) 更接近0。于是，考虑迭代求解：
由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：
牛顿法搜索动态示例图：
序列\({s_i}\)是线性收敛时，满足的条件：
如果取\(δ = 0\)，则该序列表现出超线性收敛。
序列\({s_i}\)是二次收敛时，满足的条件：
\(\Large\color{magenta}{例子}\)
线性收敛:
超线性收敛:
二次收敛:
\(\large\color{magenta}{\boxed{\color{brown}{定理1} }}\)如果\(H(x)\)是对称和正定(SPD)，而\(d =-H({x})^{-1} ?f({x}) \neq 0\)，则\(d\)是一个下降方向，即对于所有\(α\)的足够小的值，有 \(f(x +αd) < f(x)\)。
【证明】因为
要\(\min ~ ~ ~ f(x)\),则\(?h(x)=0\)，有
所以\(d =-H({x})^{-1} ?f({x})\) ，\(x^{k+1} = x^k + αd\) ,如果\(H(x)\)是对称和正定(SPD)，则
则\(d\)是一个下降方向,有 \(f(x +αd) < f(x)\)。
\(\large\color{magenta}{\boxed{\color{brown}{定理2} }}\) （二次收敛定理） 假设 \(f(x)\) 是二次连续可微 ，点 \(x^{*}\) 满足 \(\nabla f\left(x^{*}\right)=0\) 。假设 \(\mathrm{H}(\mathrm{x})\) 满足以下条件:
存在一个标量 \(h>0\) ，有 \(\left\|H\left(x^{*}\right)^{-1}\right\| \leq \frac{1}{h}\) ，存在标量 \(\beta>0\) 和 \(L>0\) 满足 \(\left\|H(x)-H\left(x^{*}\right)\right\| \leq L\left\|x-x^{*}\right\|\) 其中 \(x\) 满足 \(\left\|x-x^{*}\right\| \leq \beta\)
那么：
(i) \(\left\|x_{N}-x^{*}\right\| \leq\left\|x-x^{*}\right\|^{2}\left(\frac{L}{2\left(h-L\left\|x-x^{*}\right\|\right)}\right)\)
(ii) \(\left\|x_{N}-x^{*}\right\| \leq\left\|x-x^{*}\right\|<\gamma\)
(iii) \(\left\|x_{N}-x^{*}\right\| \leq\left\|x-x^{*}\right\|^{2}\left(\frac{3 L}{2 h}\right)\).
牛顿法虽然收敛很快，但其一个致命弱点就是每次迭代都要计算目标函数的Hesse矩阵及其逆矩阵，当问题的维数较大时，计算量迅速增加。于是后来又有了拟牛顿法。
对于步长 \(α_k = 1\) 是否让目标函数充分下降；否，则采用线搜索方法重新确定* \(α_k\)；
若\(?^2f (x^k ) ? 0\), 则选取 \(B_k := ?^2f (x_k )\) ； 否则，采取修正方法(多种):
\(B_k := ?^2f (x^ k ) + λI\) , \(λ\)为适当正数保证 \(B_k\) 正定；
考虑特征值分解 \(?^2f (x ^k ) = Q^T ΛQ\) , 其中 \(Λ = diag (λ _1, · · · , λ _n )\) ; 令 \(B_k = Q^T diag(τ_i)Q\) ,
\(δ\)为一适当的正数
例1:用牛顿法求解
解决方案:
【1】
让 \(\nabla f(x)=0,\) 有
所以, \(\bar{x}=\left(\begin{array}{c}8 \\ -4\end{array}\right)\) 是一个严格的局部优化。
【2】
设 \(x^{1}=\left(\begin{array}{l}1 \\ 1\end{array}\right), \nabla f\left(x^{1}\right)=\left(\begin{array}{c}-2 \\ 3\end{array}\right),\) 有
\(H^{-1}=\left(\begin{array}{cc}2 & -1 \\ -1 & 1\end{array}\right),\)所以
\(x^{2}=x^{1}-H^{-1} \nabla f\left(x^{1}\right)=\left(\begin{array}{c}1 \\ 1\end{array}\right)-\left(\begin{array}{cc}1 & 1 \\ 1 & 2\end{array}\right)^{-1}\left(\begin{array}{c}-2 \\ 3\end{array}\right)=\left(\begin{array}{c}8 \\ -4\end{array}\right)\)
因为 \(\nabla f\left(x^{2}\right)=0,\) 停止迭代. \(x^{2}\) 是一个最优点。
例2:
解决方案:
不难发现\(x^{*}=\frac{1}{7}=0.142857143\)是唯一的全局最小值。在\(x\)的牛顿方向是
因此，Newton的方法将生成迭代\(\left\{x^{k}\right\}\)的序列，满足:
顺便说一下，牛顿的二次收敛的范围。这个函数的方法是
例3:
解决方案:
这是显而易见的 \(x^{*}=\left(\frac{1}{3}, \frac{1}{3}\right)^{T}, f\left(x^{*}\right)=7=3.295836866\).
在牛顿法中，重复步骤3 通过 \(x^{k+1}=x^{k}+\alpha_{k} d_{N}^{k}\) 其中\(\alpha_{k}\) 满足：
例4:
用Damp-Newton法求解
解决方案:
设 \(x^{1}=\left(\begin{array}{l}1 \\ 1\end{array}\right),\) 有
令 \(x=x^{1}+\alpha d^{1},\) 其中
然后我们有
令 \(\varphi^{\prime}(\alpha)=0,\) 我们有 \(\alpha_{1}=1,\) 并且 \(x^{2}=x^{1}+\alpha_{1} d^{1}=(8,-4)^{T}\)
因为 \(\nabla f\left(x^{2}\right)=0,\) 停止迭代. \(x^{2}\) 是一个最优点。
无约束优化算法--牛顿法与拟牛顿法（DFP，BFGS，LBFGS） - ljy2013 - 博客园
MIT凸优化课程
Stephen Boyd的Convex Optimization
《凸优化》，Stephen Boyd等著，王书宁等译
“最优化理论与算法”北京邮电大学数学系
原文：https://www.cnblogs.com/liangjiangjun/p/14188282.html