无约束优化---牛顿法

无约束最优化问题:

\[\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 $,

1. 计算牛顿方向\(d^k=-H(\bar{x}^k)^{-1} ∇f(\bar{x}^k)\) 。
2. 停止条件：如果 \(d^k=0,或者(d^k)^2/2<\epsilon\)则退出。
3. 直线搜索：用精确性搜索或者非精确性搜索选择步长 \(α_k\)
4. 迭代： \(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牛顿法的二次收敛性