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

Lingfeng 2024-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)$ 其中 $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})$ 当 $\left\lVert S^{*} \right\rVert=0$ 则有二阶收敛速度，反之当 $\left\lVert (J^{*T}J^{*})^{-1} \right\rVert \left\lVert S^{*}\right\rVert<1$ 为线性收敛速度。

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}$