05无约束优化-最小二乘法

Lingfeng2024-11-09

05无约束优化-最小二乘法

1. 定义

Definition (最小二乘法)

\min f(x)=\frac{1}{2}\sum_{i = 1}^{m} r_{i}^{2}(x)=\frac{1}{2}r(x)^{T}r(x)

Definition (Jacobin矩阵)

J(x)= \frac{ \partial r(x) }{ \partial x^{T} } =\begin{pmatrix} \nabla r_1(x)^{T} \\ \nabla r_2(x)^{T} \\ \vdots \\ \nabla r_n(x)^{T} \end{pmatrix}

Theorem (剩余函数梯度)

一阶梯度

g(x)= J(x)^{T}r(x)

Hesse矩阵为

\begin{align*} G(x) & =J(x)^{T}J(x)+r(x)^{T} \nabla^{2} r(x) \\ & = J(x)^{T}J(x)+S(x)\end{align*}

其中

S(x)=\sum_{i = 1}^{m}r_{i}(x)\nabla^{2}r_{i}(x)

。

证明
使用链式法则

\begin{align*} \frac{ \partial f(x) }{ \partial x } & = \frac{1}{2}\frac{ \partial r(x)^{T}r(x) }{ \partial x } \\ & = \frac{ \partial r(x)^{T} }{ \partial x } r(x) \\ & = J(x)^{T}r(x) \end{align*}

同时考虑

\begin{align*} \frac{ \partial^{2} f(x) }{ \partial x^{T}\partial x } & = \frac{ \partial J(x)^{T}r(x) }{ \partial x^{T}} \\ & = J(x)^{T}\frac{ \partial r(x) }{ \partial x^{T} }+ \left( \frac{ \partial J(x) }{ \partial x } \right)^{T} r(x) \\ & = J(x)^{T}J(x)+S(x) \end{align*}

2. Gauss-Newton方法

Definition (Gauss-Newton方法)

J_{k}^{T}J_{k}d=-J_{k}^{T}r_{k}

Theorem (基本Gauss-Newton的收敛性)

\left\lVert h_{k+1} \right\rVert \leq \left\lVert (J^{*T}J^{*})^{-1} \right\rVert \left\lVert S^{*}\right\rVert \left\lVert h_{k} \right\rVert +O(\left\lVert h_{k} \right\rVert ^{2})

Definition (阻尼Gauss-Newton方法)

基本Guass-Newton确定 $d_{k}$ 后，使用线搜索确定步长。

3. LMF方法

Definition (LM方法)

(J_{k}^{T}J_{k}+\nu_{k}I)d=-J_{k}^{T}r_{k}

Theorem (LM方法与信赖域方法的关系)

$d_{k}$ 是信赖域子问题

\begin{align*} \min \frac{1}{2}\left\lVert J_{k}d+r_{k} \right\rVert ^{2 } \\ s.t.\left\lVert d \right\rVert ^{2 }\leq\Delta_{k} \end{align*}

的全局极小解的充分必要条件为，存在

\nu_{k}\geq 0

使得

\begin{align*} (J_{k}^{T}J_{k}+\nu_{k}I)d & =-J_{k}^{T}r_{k} \\ \nu_{k}(\Delta_{k}^{2}-\left\lVert d_{k} \right\rVert ^{2}) & =0\end{align*}

Definition (LMF方法)

计算

\gamma_{k}=\frac{\Delta f_{k}}{\Delta q_{k}}

根据

\gamma_{k}

调整

\nu_{k}

。

4. 大剩余量问题

注意到

\begin{align*} S(x)\Delta x & =r^{T}(x) \frac{ \partial J(x) }{ \partial x } \Delta x \\ & = r^{T}(x)\Delta J(x) \\ & = \Delta J(x)^{T}r(x) \end{align*}

定义

\hat{y}=\Delta J(x)^{T}r(x)

，则

S(x)

的近似矩阵

\hat{B}_{k}

满足

\hat{B}_{k+1}s_{k}=\hat{y}_{k}

仿照BFGS方法和DFP方法即可解出

\hat{B}_{k+1}=\hat{B}_{k}+\frac{(\hat{y}_{k}-\hat{B}_{k}s_{k})y_{k}^{T}+y_{k}(\hat{y}_{k}-\hat{B}_{k}s_{k})^{T}}{y_{k}^{T}s_{k}}-\frac{(\hat{y}_{k}-\hat{B}_{k}s_{k})^{T}s_{k}}{(y_{k}^{T}s_{k})^{2}}y_{k}y_{k}^{T}

ON THIS PAGE