无约束优化---牛顿法
无约束最优化问题:
\[\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~ ~ ~x ∈ X ? R^n \end{aligned}
\]
1牛顿法
在\(x = \bar{x}\)时，f(x)可近似为:
\[f(x) \approx h(x) = f(\bar{x}) + ?f(\bar{x})^T (x ? \bar{x}) + \frac{1}{2}(x ? \bar{x})^TH(\bar{x})(x ? \bar{x})
\]
要\(\min ~ ~ ~ f(x)\),则\(?h(x)=0\)，有
\[?f(\bar{x}) +H(\bar{x})(x ? \bar{x}) = 0,
\]
则
\[x ? \bar{x}= -H(\bar{x})^{-1} ?f(\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 $,
- 计算牛顿方向\(d^k=-H(\bar{x}^k)^{-1} ?f(\bar{x}^k)\) 。
- 停止条件：如果 \(d^k=0,或者(d^k)^2/2<\epsilon\)则退出。
- 直线搜索：用精确性搜索或者非精确性搜索选择步长 \(α_k\)
- 迭代： \(x^{k+1} = x^k + α_kd^k, k = k + 1\). 转到步骤1。
请注意以下几点:
- 牛顿法不能满足\(H(\bar{x}^k)\)在每次迭代中都是非奇异,正定矩阵。
- 不能保证每一步\(f(x^{k+1}) <f(x^k)\)
牛顿法的优缺点；https://zhuanlan.zhihu.com/p/33544363
2收敛速度
序列\({s_i}\)是线性收敛时，满足的条件：
\[\lim_{i→∞}s_i = \bar{s}，~ ~ ~\lim_{i→∞} \frac{||s_{i+1}-\bar{s}||}{||s_i-\bar{s}||}= δ < 1.
\]
如果取\(δ = 0\)，则该序列表现出超线性收敛。
序列\({s_i}\)是二次收敛时，满足的条件：
\[\lim_{i→∞}s_i = \bar{s}，~ ~ ~\lim_{i→∞} \frac{||s_{i+1}-\bar{s}||}{||s_i-\bar{s}||^2}= δ < ∞.
\]
3牛顿法的二次收敛性
优化02
原文：https://www.cnblogs.com/liangjiangjun/p/14022648.html
