非线性优化

方法	思路	缺点
最速下降	沿着目标函数的负梯度方向进行搜索	目标函数需连续可导
牛顿法	使用目标函数的二阶导数信息逼近最优解	H矩阵可逆&求逆
拟牛顿法	近似目标的H矩阵避免了求解逆矩阵的复杂
高斯牛顿法	改用
L-M法	拟牛顿法的扩展,适用于参数拟合问题

方程建立

\underset{x}{m i n} F (x) = \frac{1}{2} {| | f (x) | |}^{2}

牛顿法

推导

F (x_{k} + Δ x_{k}) = F (x + k) + J (x_{k})^{T} Δ x_{k} + \frac{1}{2} Δ x_{k}^{T} H (x_{k}) Δ x_{k}

其中 $J$ 为雅克比矩阵(一阶导数), $H$ 为海森矩阵(二阶导数),有

{\begin{matrix} 最 速 下 降 法 : Δ x^{*} = - J (x_{k}) \\ 牛 顿 法 : Δ x^{*} = a r g \underset{Δ x}{m i n} (F (x) + J {(x)}^{T} Δ x + \frac{1}{2} Δ x^{T} H Δ x) \end{matrix}

对右侧求导并令其等于0,有$$J+H\Delta x=0\Rightarrow H\Delta x=-J$$

例题

y = f (x) - a x - b

Δ x_{k} = \frac{f (x_{k}) - a x_{k} - b - y_{k}}{f^{'} (x_{k}) - a}

高斯牛顿法

推导

f (x + Δ x) = f (x) + J (x)^{T} Δ x

有线形最小二乘问题:

Δ x^{*} = a r g \underset{Δ x}{m i n} \frac{1}{2} {| | f (x) + J (x)^{T} Δ x | |}^{2}

右侧展开后求导可以得到

\frac{δ . . .}{δ Δ x} = J (x) f (x) + J (x) J^{T} (x) Δ x = 0

J (x) J^{T} (x) Δ x = - J (x) f (x) \Rightarrow H (x) Δ x = g (x)

例题

有曲线 $y = e x p (a x^{2} + b x + c) + w$ 和一组拟合点 $[[x_{1}, y_{1}], . . ., [x_{n}, y_{n} ∥ x_{1}, y_{1}], . . ., [x_{n}, y_{n}]]$
有$$\underset{a,b,c}{min}\frac12\sum^N_{i=1}\left|\left|y_i-exp(ax_i^2+bx_i+c)\right|\right|^2=\underset{a,b,c}{min}\frac12\sum^N_{i=1}\left|\left|e_i\right|\right|^2$$
对a,b,c求偏导数可以得到$$J_i=[\frac{\delta e_i}{\delta a},\frac{\delta e_i}{\delta b},\frac{\delta e_i}{\delta c}]=[-x_i^2exp(ax_i^2+bx_i+c),-x_iexp(ax_i^2+bx_i+c),-exp(ax_i^2+bx_i+c)]$$

优化算法-高斯牛顿法