非线性优化

谁践踏了优雅 2021-12-15 00:53 340阅读 0赞

### 文章目录 ###

*   *  最速下降法(梯度下降)
     *  牛顿法－>阻尼牛顿->修正阻尼牛顿
     *  高斯牛顿法
     *  列文伯格-马夸尔特
     *  鲁棒核函数

## 最速下降法(梯度下降) ##

*  定义问题：  
    对于一个非线性函数 f ( x ) f(\\textbf\{x\}) f(x)，目标求： min ⁡ f ( x ) ， &ThickSpace; x ∈ R n \\min f(\\boldsymbol\{x\}) ， \\; \\mathbf\{x\}\\in\\mathbb\{R\}^n minf(x)，x∈Rn
 *  数学理论：

1.  我们需要找到一个下降的方向，使得 f ( x ) f(\\mathbf\{x\}) f(x)随着x的迭代而逐渐减小，直到 x \\mathbf\{x\} x收敛于 x ∗ \\mathbf\{x^\*\} x∗：  
     f ( x k + 1 ) < f ( ( x k ) f(\\mathbf\{x\_\{k+1\}\})<f((\\mathbf\{x\_k\}) f(xk\+1)<f((xk)  
    我们需要选择适当的方向 d \\mathbf\{d\} d和 步长 α \\alpha α ， f ( x k + α d ) < f ( ( x k ) f(\\mathbf\{x\_\{k\}+\\alpha\\mathbf\{d\}\})<f((\\mathbf\{x\_k\}) f(xk\+αd)<f((xk)  
      
    
2.  将 f ( x ) f(x) f(x)在进行一阶泰勒展开： f ( x + α d ) = f ( x ) + α ▽ f ( x ) T d ， ▽ f ( x ) f(\\boldsymbol\{x\}+\\alpha\\mathbf\{d\}) = f(\\mathbf\{x\})+\\alpha\\triangledown f(\\mathbf\{x\})^T\\mathbf\{d\}，\\triangledown f(\\mathbf\{x\}) f(x\+αd)=f(x)\+α▽f(x)Td，▽f(x)是 f ( x ) f(x) f(x)的梯度， ▽ f ( x ) T \\triangledown f(\\mathbf\{x\})^T ▽f(x)T可以用 J J J雅克比代替：  
     f ( x + α d ) = f ( x ) + α J d f(\\boldsymbol\{x\}+\\alpha\\mathbf\{d\}) = f(\\mathbf\{x\})+\\alpha \\mathbf\{J\} \\mathbf\{d\} f(x\+αd)=f(x)\+αJd
3.  因为 α > 0 \\alpha>0 α>0，所以 J d < 0 \\mathbf\{J\} \\mathbf\{d\}<0 Jd<0，有： J d = ∥ J ∥ ∥ d ∥ cos ⁡ θ \\mathbf\{J\} \\mathbf\{d\}= \\parallel \\mathbf\{J\}\\parallel \\parallel \\mathbf\{d\}\\parallel \\cos\\theta Jd=∥J∥∥d∥cosθ  
    当 θ \\theta θ取 − π -\\pi −π也就是**d**取负梯度的方向： − J T -\\mathbf\{J\}^T −JT，到达最小值。
4.  对于 α \\alpha α，我们在最速下降的方向进行－维的搜索，即 α \\alpha α满足 f ( x k + α k d k ) = arg ⁡ min ⁡ α ⩾ 0 f ( x k + α d k ) f(\\boldsymbol\{x\_k\}+\\alpha\_k\\mathbf\{d\_k\}) = \\arg \\min\_\{\\alpha\\geqslant 0\}f(\\boldsymbol\{x\_k\}+\\alpha\\mathbf\{d\_k\}) f(xk\+αkdk)=argα⩾0minf(xk\+αdk)

*  算法：

1.  给定初始点 x 0 \\mathbf\{x\_0\} x0，和允许的误差 ε > 0 \\varepsilon>0 ε>0，置 k = 0 k=0 k=0；
2.  计算搜索方向 d k = − ▽ f ( x k ) \\mathbf\{d\_k\}=- \\triangledown f(\\mathbf\{x\_k\}) dk=−▽f(xk) ；
3.  若 ∥ d k ∥ ⩽ ε \\parallel\\mathbf\{d\_k\}\\parallel\\leqslant\\varepsilon ∥dk∥⩽ε，则停止；否则从 x k \\boldsymbol\{x\_k\} xk出发，沿着 d k \\mathbf\{d\_k\} dk进行一维的搜索，求出 α k \\alpha\_k αk使得： f ( x k + α k d k ) = arg ⁡ min ⁡ α ⩾ 0 f ( x k + α d k ) f(\\boldsymbol\{x\_k\}+\\alpha\_k\\mathbf\{d\_k\}) = \\arg \\min\_\{\\alpha\\geqslant 0\}f(\\boldsymbol\{x\_k\}+\\alpha\\mathbf\{d\_k\}) f(xk\+αkdk)=argα⩾0minf(xk\+αdk)
4.  令 x k + 1 = x k + α k d k \\mathbf\{x\_\{k+1\}\}=\\mathbf\{x\_k\}+\\alpha\_k\\mathbf\{d\_k\} xk\+1=xk\+αkdk，置 k = k + 1 k=k+1 k=k\+1，转步骤2；

*  算法评价：

缺点：

1.  因为每次迭代的梯度方向和下一次的梯度方向是正交的，当到了最优值的附近，震动收敛慢。
2.  另外，如果 f ( x ) f(x) f(x)的海森矩阵正定，最大和最小特征值的比 r = A a r=\\frac\{A\}\{a\} r=aA称为条件数，条件数越小，收敛越快，相反则慢。

Trick：

1.  一般最大特征值和最小特征值和数据维度里面的数据Scale有关，也就是说可能是因为数据的量级差的比较多，这时候可以通过Scale进行数据的缩放，来达到收敛更快的效果。

例题：参考最优化理论和算法p283,例10.1.1

--------------------

## 牛顿法－>阻尼牛顿->修正阻尼牛顿 ##

1.  将 f ( x ) f(\\textbf\{x\}) f(x)进行二阶泰勒展开：  
     (1) f ( x + Δ x ) = f ( x ) + J Δ x + 1 2 Δ x T H Δ x f(\\boldsymbol\{x\}+\\Delta \\mathbf\{x\}) = f(\\mathbf\{x\})+J\\Delta\\mathbf\{x\}+\\frac\{1\}\{2\}\\Delta \\mathbf\{x\}^TH\\Delta \\mathbf\{x\}\\tag\{1\} f(x\+Δx)=f(x)\+JΔx\+21ΔxTHΔx(1)  
    在 x k \\mathbf\{x\_k\} xk处，求 Δ x k ＝ arg ⁡ min ⁡ Δ x f ( x k + Δ x ) \\Delta\\mathbf\{x\_k\}＝\\arg \\min\_\{\\Delta\\mathbf\{x\}\} f(\\mathbf\{x\_k\}+\\Delta\\mathbf\{x\}) Δxk＝argΔxminf(xk\+Δx)
2.  让二次的1式对 Δ x \\Delta\\mathbf\{x\} Δx求导，并令其为０，得到稳定点：  
     (2) J T + H Δ x = 0 J^T+H\\Delta \\mathbf\{x\}=0\\tag\{2\} JT\+HΔx=0(2)  
    得到 Δ x k = − H − 1 J T \\Delta\\mathbf\{x\_k\}=-H^\{-1\}J^T Δxk=−H−1JT

注意，在局部最优解的附近， x + Δ x \\boldsymbol\{x\}+\\Delta \\mathbf\{x\} x\+Δx是最优解，但是当初始点远离极小点的时候，牛顿法可能不收敛，原因之一牛顿方向： Δ x k = − H − 1 J T \\Delta\\mathbf\{x\_k\}=-H^\{-1\}J^T Δxk=−H−1JT不一定是下降的方向，目标值有可能上升。因此对牛顿法提出了修正，提出阻尼牛顿法

1.  **阻尼牛顿法**在原始的牛顿法的基础上添加：沿着牛顿方向进行一维的搜索，迭代公式：  
     x k + λ k d k \\boldsymbol\{x\_k\}+\\lambda\_k\\mathbf\{d\_k\} xk\+λkdk  
    其中 d k = − H k − 1 J k T \\mathbf\{d\_k\}=-H\_k^\{-1\}J\_k^T dk=−Hk−1JkT为牛顿方向， λ k \\lambda\_k λk为搜索步长，满足：  
     f ( x k + λ k d k ) = arg ⁡ min ⁡ λ f ( x k + λ d k ) f(\\boldsymbol\{x\_k\}+\\lambda\_k\\mathbf\{d\_k\}) = \\arg \\min\_\{\\lambda\}f(\\boldsymbol\{x\_k\}+\\lambda\\mathbf\{d\_k\}) f(xk\+λkdk)=argλminf(xk\+λdk)

注意，原始牛顿法和阻尼牛顿法有着共同的缺点，一是可能奇异，而是可能非正定，这样无法确定后继点，进而做进一步修正

1.  **阻尼牛顿法的进一步修正**，阻尼牛顿法用的搜索方向也是牛顿方向，解决海森矩阵非正定的基本思想就是：修正 H k H\_k Hk构造一个对称的正定矩阵 G k G\_k Gk，用 G k G\_k Gk代替2式中的H得到方程：  
     (3) G k d k = − J T G\_k\\mathbf\{d\_k\} = -J^T\\tag\{3\} Gkdk=−JT(3)  
    算出 d k \\mathbf\{d\_k\} dk再以此方向做一维的搜索
2.  构造 G k G\_k Gk的方法之一就是另 G k = H + ε k I G\_k=H+\\varepsilon\_kI Gk=H\+εkI， I I I是单位阵，只要 ε k \\varepsilon\_k εk是一个适当的正数， G k G\_k Gk就是一个对称的正定矩阵。事实上，如果 α k \\alpha\_k αk是 H k H\_k Hk的特征值，那么 α k + ε k \\alpha\_k+\\varepsilon\_k αk\+εk是 G k G\_k Gk的特征值，只要 ε k \\varepsilon\_k εk取的足够大， G k G\_k Gk所有的特征值为正，保证了正定性。
3.  注意的是，当 x k \\mathbf\{x\_k\} xk为鞍点的时候，即梯度为０，海森矩阵不定：  
     − J k T = 0 ； H 不 定 -J^T\_k=0；H不定 −JkT=0；H不定  
    那么根据3式无法求出牛顿方向 d k \\mathbf\{d\_k\} dk，这时候 d k \\mathbf\{d\_k\} dk可以取负曲率方向，即满足： d k T H d k < 0 \\mathbf\{d\_k\} ^TH\\mathbf\{d\_k\} <0 dkTHdk<0再进行一维搜索，必定能使目标函数下降。

*  阻尼牛顿算法：

1.  给定初始点 x 0 \\mathbf\{x\_0\} x0，和允许的误差 ε > 0 \\varepsilon>0 ε>0，置 k = 0 k=0 k=0；
2.  计算 J k T J\_k^T JkT和 H k − 1 H\_k^\{-1\} Hk−1
3.  若 ∥ J ∥ < ε \\parallel J\\parallel<\\varepsilon ∥J∥<ε则停止迭代，否则令： d k = − H k − 1 J k T \\mathbf\{d\_k\}=-H\_k^\{-1\}J\_k^T dk=−Hk−1JkT
4.  从 x k \\mathbf\{x\_k\} xk 出发，沿着 d k \\mathbf\{d\_k\} dk做一维的搜索，满足： f ( x k + λ k d k ) = arg ⁡ min ⁡ λ f ( x k + λ d k ) f(\\boldsymbol\{x\_k\}+\\lambda\_k\\mathbf\{d\_k\}) = \\arg \\min\_\{\\lambda\}f(\\boldsymbol\{x\_k\}+\\lambda\\mathbf\{d\_k\}) f(xk\+λkdk)=argλminf(xk\+λdk)
5.   x k + 1 = x k + λ k d k ； k = k + 1 \\mathbf\{x\_\{k+1\}\}=\\mathbf\{x\_k\}+\\lambda\_k\\mathbf\{d\_k\}；k=k+1 xk\+1=xk\+λkdk；k=k\+1转步骤2

*  算法评价：

1.  牛顿法：

*  优点：对于二次正定函数，经过一次迭代便达到最优点，对于非二次函数，若二次性较强或者迭代点已经进入极点附近收敛很快
 *  缺点：H矩阵计算困难，奇异，非正定等情况

1.  阻尼牛顿法：

*  优点：能保证每次迭代基本会下降，绝不会上升
 *  缺点：H矩阵计算困难，奇异，非正定等情况

1.  阻尼牛顿法的修正：

*  优点：保证了每次迭代能够下降，且解决了海森矩阵非正定，奇异的问题
 *  缺点：G矩阵计算困难，多了 ε \\varepsilon ε的选取策略，算法变得复杂

--------------------

## 高斯牛顿法 ##

高斯牛顿法主要解决非线性最小二乘问题。

*  定义问题：  
    对于一个  残差函数 f ( x ) f(\\textbf\{x\}) f(x)，目标求： min ⁡ F ( x ) = min ⁡ ∑ i = 1 m 1 2 ∥ f i ( x ) ∥ 2 2 \\min F(\\mathbf\{x\}) =\\min \\sum\_\{i=1\}^\{m\}\\frac\{1\}\{2\}\\left \\| f\_i(\\mathbf\{x\}) \\right \\|\_2^2 minF(x)=mini=1∑m21∥fi(x)∥22
 *  数学理论：

1.  定义为 f ( x ) = \[ f 1 ( x ) ⋯ f m ( x ) \] ； &ThinSpace;&ThinSpace;&ThinSpace; f ( x ) T f ( x ) = ∑ i = 1 m ∥ f i ( x ) ∥ 2 2 ； &ThinSpace;&ThinSpace;&ThinSpace; J = \[ J 1 ( x ) ⋯ J m ( x ) \] \\mathbf\{f\}(\\mathbf\{x\})=\\begin\{bmatrix\} f\_1(x) \\\\ \\cdots \\\\ f\_m(x) \\\\ \\end\{bmatrix\}；\\, \\, \\, \\mathbf\{f\}(\\mathbf\{x\})^T\\mathbf\{f\}(\\mathbf\{x\})=\\sum\_\{i=1\}^\{m\}\\left \\| f\_i(\\mathbf\{x\}) \\right \\|\_2^2；\\, \\, \\,\\mathbf\{J\}=\\begin\{bmatrix\} J\_1(\\mathbf\{x\})\\\\ \\cdots \\\\ J\_m(\\mathbf\{x\}) \\end\{bmatrix\} f(x)=⎣⎡f1(x)⋯fm(x)⎦⎤；f(x)Tf(x)=i=1∑m∥fi(x)∥22；J=⎣⎡J1(x)⋯Jm(x)⎦⎤
2.  将 f ( x ) \\mathbf\{f\}(\\mathbf\{x\}) f(x)进行一阶泰勒展开：(这里是残差函数，不是目标函数，和最速下降、牛顿法不同)  
     (1) f ( x + Δ x ) = f ( x ) + J Δ x \\mathbf\{f\}(\\boldsymbol\{x\}+\\Delta \\mathbf\{x\}) = \\mathbf\{f\}(\\mathbf\{x\})+\\mathbf\{J\}\\Delta\\mathbf\{x\}\\tag\{1\} f(x\+Δx)=f(x)\+JΔx(1)
3.  将1式带入F(x)：  
     (2) F ( x + Δ x ) ≈ L ( Δ x ) = 1 2 f ( x + Δ x ) T f ( x + Δ x ) = 1 2 f T f + f T J Δ x + 1 2 Δ x T J T J Δ x = F ( x ) + f T J Δ x + 1 2 Δ x T J T J Δ x F(\\mathbf\{x\}+\\Delta \\mathbf\{x\})\\approx L\\left (\\Delta \\mathbf\{x\} \\right )=\\frac\{1\}\{2\}\\mathbf\{f\}(\\boldsymbol\{x\}+\\Delta \\mathbf\{x\})^T\\mathbf\{f\}(\\boldsymbol\{x\}+\\Delta \\mathbf\{x\}) \\\\ =\\frac\{1\}\{2\}\\mathbf\{f\}^T\\mathbf\{f\}+\\mathbf\{f\}^T\\mathbf\{J\}\\Delta \\mathbf\{x\}+\\frac\{1\}\{2\}\\Delta \\mathbf\{x\}^T\\mathbf\{J\}^T\\mathbf\{J\}\\Delta \\mathbf\{x\}\\\\=F(\\mathbf\{x\})+\\mathbf\{f\}^T\\mathbf\{J\}\\Delta \\mathbf\{x\}+\\frac\{1\}\{2\}\\Delta \\mathbf\{x\}^T\\mathbf\{J\}^T\\mathbf\{J\}\\Delta \\mathbf\{x\}\\tag\{2\} F(x\+Δx)≈L(Δx)=21f(x\+Δx)Tf(x\+Δx)=21fTf\+fTJΔx\+21ΔxTJTJΔx=F(x)\+fTJΔx\+21ΔxTJTJΔx(2)
4.  令２式对 Δ x \\Delta x Δx求导＝０：  
     (3) ( J T J ) Δ x = − J T f \\left ( \\mathbf\{J\}^T\\mathbf\{J\} \\right )\\Delta \\mathbf\{x\}=-\\mathbf\{J\}^T\\mathbf\{f\}\\tag\{3\} (JTJ)Δx=−JTf(3)  
    3式也称作normal equation，或者也叫Gauss-Newton 公式。另外由2式得： F ′ ( x ) = f T J , F ′ ′ ( x ) ≈ J T J F^\{&\#x27;\} (\\mathbf\{x\})=\\mathbf\{f\}^T\\mathbf\{J\},F^\{&\#x27;&\#x27;\} (\\mathbf\{x\})\\approx\\mathbf\{J\}^T\\mathbf\{J\} F′(x)=fTJ,F′′(x)≈JTJ

*  高斯牛顿算法：

1.  给定初始点 x 0 \\mathbf\{x\_0\} x0，运行误差 ε > 0 \\varepsilon>0 ε>0
2.  计算函数值和一阶导数： f i ( x k ) = \[ f 1 ( x k ) f 2 ( x k ) ⋯ f m ( x k ) \] ； J = \[ ∂ f 1 ( x k ) ∂ x 1 ⋯ ∂ f 1 ( x k ) ∂ x n ⋮ ⋱ ⋮ ∂ f m ( x k ) ∂ x 1 ⋯ ∂ f m ( x k ) ∂ x n \] f\_i(\\mathbf\{x\_k\})=\\begin\{bmatrix\} f\_1(\\mathbf\{x\_k\})\\\\ f\_2(\\mathbf\{x\_k\})\\\\ \\cdots\\\\ f\_m(\\mathbf\{x\_k\}) \\end\{bmatrix\}；\\mathbf\{J\}=\\begin\{bmatrix\} \\frac\{\\partial f\_1(\\mathbf\{x\_k\})\}\{\\partial x\_1\}& \\cdots & \\frac\{\\partial f\_1(\\mathbf\{x\_k\})\}\{\\partial x\_n\} \\\\ \\vdots & \\ddots & \\vdots & \\\\ \\frac\{\\partial f\_m(\\mathbf\{x\_k\})\}\{\\partial x\_1\}& \\cdots & \\frac\{\\partial f\_m(\\mathbf\{x\_k\})\}\{\\partial x\_n\} & \\end\{bmatrix\} fi(xk)=⎣⎢⎢⎡f1(xk)f2(xk)⋯fm(xk)⎦⎥⎥⎤；J=⎣⎢⎢⎡∂x1∂f1(xk)⋮∂x1∂fm(xk)⋯⋱⋯∂xn∂f1(xk)⋮∂xn∂fm(xk)⎦⎥⎥⎤
3.  根据式３求出高斯-牛顿方向 d k \\mathbf\{d\_k\} dk
4.  从 x k \\mathbf\{x\_k\} xk 出发，沿着 d k \\mathbf\{d\_k\} dk做一维的搜索，满足： F ( x k + λ k d k ) = arg ⁡ min ⁡ λ F ( x k + λ d k ) F(\\boldsymbol\{x\_k\}+\\lambda\_k\\mathbf\{d\_k\}) = \\arg \\min\_\{\\lambda\}F(\\boldsymbol\{x\_k\}+\\lambda\\mathbf\{d\_k\}) F(xk\+λkdk)=argλminF(xk\+λdk)
5.  令  x k + 1 = x k + λ k d k \\mathbf\{x\_\{k+1\}\}=\\mathbf\{x\_k\}+\\lambda\_k\\mathbf\{d\_k\} xk\+1=xk\+λkdk
6.  若 ∥ x k + 1 − x k ∥ ⩽ ε \\left \\| \\mathbf\{x\_\{k+1\}\}-\\mathbf\{x\_k \}\\right \\|\\leqslant \\varepsilon ∥xk\+1−xk∥⩽ε，则停止，否则 k = k + 1 , k=k+1, k=k\+1,返回步骤2

注意：有时候 J T J J^TJ JTJ是奇异或接近奇异的，这时候解３式会有很大困难，下面一种方法对其做了修正

--------------------

## 列文伯格-马夸尔特 ##

Marquardt对高斯牛顿做了修正，主要思想就是在 J T J J^TJ JTJ上加正定的对角矩阵：  
 ( J T J + μ I ) Δ x l m = − J T f \\left ( \\mathbf\{J\}^T\\mathbf\{J\} +\\mu \\mathbf\{I\}\\right )\\Delta \\mathbf\{x\}\_\{lm\}=-\\mathbf\{J\}^T\\mathbf\{f\} (JTJ\+μI)Δxlm=−JTf

假如 J T J \\mathbf\{J\}^T\\mathbf\{J\} JTJ特征值 λ j \\lambda\_j λj对应特征向量 v j \\mathbf\{v\_j\} vj，得到的 Δ x l m = \\Delta \\mathbf\{x\}\_\{lm\}= Δxlm=  
 − ∑ j = 1 n v j ⊤ F ′ ⊤ λ j + μ v j -\\sum\_\{j=1\}^\{n\}\\frac\{\\mathbf\{v\}\_j^\\top \\mathbf\{F\}^\{&\#x27;\\top\}\}\{\\lambda\_j+\\mu \}\\mathbf\{v\}\_j −j=1∑nλj\+μvj⊤F′⊤vj

**阻尼因子 μ \\mu μ的作用**：

*   μ > 0 \\mu>0 μ>0保证 ( J T J + μ I ) \\left ( \\mathbf\{J\}^T\\mathbf\{J\} +\\mu \\mathbf\{I\}\\right ) (JTJ\+μI)正定，朝着迭代的方向进行
 *   μ \\mu μ非常大是时候，则 Δ x l m = − 1 μ J T f = − 1 μ F ′ ( x ) T \\Delta \\mathbf\{x\}\_\{lm\}=-\\frac\{1\}\{\\mu\}\\mathbf\{J\}^T\\mathbf\{f\}=-\\frac\{1\}\{\\mu\}F^\{&\#x27;\} (\\mathbf\{x\})^T Δxlm=−μ1JTf=−μ1F′(x)T接近最速下降法
 *   μ \\mu μ比较小的时候，则 Δ x l m ≈ Δ x g n \\Delta \\mathbf\{x\}\_\{lm\}\\approx\\Delta \\mathbf\{x\}\_\{gn\} Δxlm≈Δxgn接近高斯牛顿法

**阻尼因子的选取与跟新策略**

*  初始值的选取  
     μ 0 = τ ∗ max ⁡ \{ ( J T J ) i i \} ； τ ∈ \[ 1 0 − 8 , 1 \] \\mu\_0=\\tau \*\\max\\left \\\{ \\left ( \\mathbf\{J\}^T\\mathbf\{J\} \\right )\_\{ii\} \\right \\\}；\\tau \\in\[10^\{-8\},1\] μ0=τ∗max\{ (JTJ)ii\}；τ∈\[10−8,1\]
 *  跟新策略

1.  定性分析：  
    如果： Δ x → F ( x ) ↑ \\Delta x\\rightarrow F(x)\\uparrow Δx→F(x)↑，则 μ ↑ → Δ x ↓ \\mu \\uparrow \\rightarrow \\Delta x\\downarrow μ↑→Δx↓，增大阻尼减小步长，拒绝本次迭代  
    如果： Δ x → F ( x ) ↓ \\Delta x\\rightarrow F(x)\\downarrow Δx→F(x)↓，则 μ ↓ → Δ x ↑ \\mu \\downarrow \\rightarrow \\Delta x\\uparrow μ↓→Δx↑，减小阻尼增大步长，加快收敛，较少迭代次数
2.  定量分析  
    阻尼因子 μ \\mu μ的跟新，通过比例因子 ρ \\rho ρ来确定  
     ρ = F ( x ) − F ( x + Δ x l m ) L ( 0 ) − L ( Δ x l m ) \\rho=\\frac\{F(\\mathbf\{x\})-F(\\mathbf\{x\}+\\Delta \\mathbf\{x\_\{lm\}\})\}\{L(\\mathbf\{0\})-L(\\Delta \\mathbf\{x\_\{lm\}\})\} ρ=L(0)−L(Δxlm)F(x)−F(x\+Δxlm)  
    其中 L ( 0 ) − L ( Δ x l m ) = − f T J Δ x l m − 1 2 Δ x l m T J T J Δ x l m L(\\mathbf\{0\})-L(\\Delta \\mathbf\{x\_\{lm\}\})=-\\mathbf\{f\}^T\\mathbf\{J\}\\Delta \\mathbf\{x\_\{lm\}\}-\\frac\{1\}\{2\}\\Delta \\mathbf\{x\_\{lm\}\}^T\\mathbf\{J\}^T\\mathbf\{J\}\\Delta \\mathbf\{x\_\{lm\}\} L(0)−L(Δxlm)=−fTJΔxlm−21ΔxlmTJTJΔxlm

![在这里插入图片描述][20190705085550723.png_pic_center]

(1). **Marquardt策略**

首先比例因子的分母始终　>　0（**L(x)下降的**），如果：

*   ρ < 0 \\rho<0 ρ<0，则 F ( x ) ↑ F(x)\\uparrow F(x)↑，则 μ ↑ → Δ x ↓ \\mu \\uparrow \\rightarrow \\Delta x\\downarrow μ↑→Δx↓，增大阻尼减小步长
 *  如果  ρ > 0 \\rho>0 ρ>0且比较大，减小 μ \\mu μ，让LM接近Gauss-Newton，加快收敛
 *  反之，如果是比较小的正数，增大阻尼 μ \\mu μ，缩小迭代步长。

i f : ρ < 0.25 μ : = u ∗ 2 &ThickSpace; e l s e &ThickSpace; i f : ρ > 0.75 μ : = μ / 3 if :\\rho<0.25\\\\ \\mu:=u\*2\\\\\\;\\\\else\\; if:\\rho>0.75\\\\\\mu:=\\mu/3 if:ρ<0.25μ:=u∗2elseif:ρ>0.75μ:=μ/3

(2). **Nielsen策略(g2o, ceres采用)**

i f : ρ > 0 μ : = μ ∗ max ⁡ \{ 1 3 , 1 − ( 2 ρ − 1 ) 3 \} ; &ThickSpace;&ThickSpace; ν : = 2 &ThickSpace; e l s e μ : = μ ∗ ν ; &ThickSpace;&ThickSpace; ν : = 2 ∗ ν if :\\rho>0\\\\ \\mu:=\\mu\*\\max\\left \\\{ \\frac\{1\}\{3\},1-\\left ( 2\\rho-1 \\right )^3 \\right \\\};\\;\\;\\nu:=2\\\\ \\; \\\\else\\\\ \\\\ \\mu:=\\mu\*\\nu;\\; \\;\\nu:=2\*\\nu if:ρ>0μ:=μ∗max\{ 31,1−(2ρ−1)3\};ν:=2elseμ:=μ∗ν;ν:=2∗ν

--------------------

## 鲁棒核函数 ##

在最小二乘中处理outlier的情况，应用鲁棒核函数使得最小二乘的结果不受其太大的影响，增强鲁棒性。

鲁棒核函数作用于残差函数 f ( x ) f(x) f(x)上，最小二乘变成如下形式： (1) min ⁡ x 1 2 ∑ k = 1 m ρ ( ∥ f k ( x ) ∥ 2 ) \\min\_\{\\mathbf\{x\}\}\\frac\{1\}\{2\}\\sum\_\{k=1\}^\{m\}\\rho\\left ( \\left \\| f\_k(\\mathbf\{x\}) \\right \\|^2 \\right )\\tag\{1\} xmin21k=1∑mρ(∥fk(x)∥2)(1)

*  数学理论：

1.  将误差的平方项记作 s k = ∥ f k ( x ) ∥ 2 s\_k = \\left \\| f\_k(\\mathbf\{x\}) \\right \\|^2 sk=∥fk(x)∥2，则对鲁棒核误差函数进行二阶泰勒展开： (2) 1 2 ρ ( s + Δ s ) = 1 2 ( ρ ( s ) + ρ ′ Δ s + 1 2 ρ ′ ′ Δ 2 s ) \\frac\{1\}\{2\}\\rho(s+\\Delta s)=\\frac\{1\}\{2\}\\left ( \\rho(s)+\\rho^\{&\#x27;\}\\Delta s+\\frac\{1\}\{2\}\\rho^\{&\#x27;&\#x27;\}\\Delta ^2s \\right )\\tag\{2\} 21ρ(s\+Δs)=21(ρ(s)\+ρ′Δs\+21ρ′′Δ2s)(2)
2.  2式中的 Δ s k \\Delta s\_k Δsk： (3) Δ s k = ∥ f k ( x + Δ x ) ∥ 2 − ∥ f k ( x ) ∥ 2 ≈ ∥ f k + J k Δ x ∥ 2 − ∥ f k ( x ) ∥ 2 = 2 f k ⊤ J k Δ x + Δ x ⊤ J k ⊤ J k Δ x \\Delta s\_k=\\left \\| f\_k(\\mathbf\{x\}+\\Delta \\mathbf\{x\}) \\right \\|^2-\\left \\| f\_k(\\mathbf\{x\}) \\right \\|^2\\\\\\approx \\left \\| f\_k+\\mathbf\{J\}\_k\\Delta \\mathbf\{x\} \\right \\|^2-\\left \\| f\_k(\\mathbf\{x\}) \\right \\|^2\\\\=2f\_k^\\top \\mathbf\{J\}\_k\\Delta \\mathbf\{x\} \\mathbf\{+\\Delta x\}^\\top \\mathbf\{J\}\_k^\\top \\mathbf\{J\}\_k\\Delta \\mathbf\{x\}\\tag\{3\} Δsk=∥fk(x\+Δx)∥2−∥fk(x)∥2≈∥fk\+JkΔx∥2−∥fk(x)∥2=2fk⊤JkΔx\+Δx⊤Jk⊤JkΔx(3)
3.  将3式带入2式：  
    ![在这里插入图片描述][20190705105712809.png]const表示和 Δ x \\Delta \\mathbf\{x\} Δx无关的量，比如2式中的 ρ ( s ) \\rho(s) ρ(s)

1.   对上式求和，再对 Δ x \\Delta \\mathbf\{x\} Δx求导，令其为０，得到： (4) ∑ k J k ⊤ ( ρ ′ I + 2 ρ ′ ′ f k f k ⊤ ) J k Δ x = − ∑ k ρ ′ J k ⊤ f k ∑ k J k ⊤ W J k Δ x = − ∑ k ρ ′ J k ⊤ f k \\sum \_\{k\}\\mathbf\{J\}\_k^\\top (\\rho^\{&\#x27;\}I+2\\rho^\{&\#x27;&\#x27;\}f\_kf\_k^\\top )\\mathbf\{J\}\_k\\Delta \\mathbf\{x\}=-\\sum\_\{k\}\\rho^\{&\#x27;\}\\mathbf\{J\}\_k^\\top f\_k\\\\\\sum \_\{k\}\\mathbf\{J\}\_k^\\top W\\mathbf\{J\}\_k\\Delta \\mathbf\{x\}=-\\sum\_\{k\}\\rho^\{&\#x27;\}\\mathbf\{J\}\_k^\\top f\_k\\tag\{4\} k∑Jk⊤(ρ′I\+2ρ′′fkfk⊤)JkΔx=−k∑ρ′Jk⊤fkk∑Jk⊤WJkΔx=−k∑ρ′Jk⊤fk(4)  
    由4式可以看出，W就相当于权重，作用于每个k上，每次的迭代，权重都会变化

*  核函数举例：

1.  **Cauchy** Loss Function： ρ ( s ) = c 2 log ⁡ ( 1 + s c 2 ) \\rho(s)=c^2\\log (1+\\frac\{s\}\{c^2\}) ρ(s)=c2log(1\+c2s)  
     c c c是控制参数，对 s s s的一阶导数和二阶导数： ρ ′ ( s ) = 1 1 + s c 2 ； ρ ′ ′ ( s ) = − 1 c 2 ( ρ ′ ( s ) ) 2 \\rho^\{&\#x27;\}(s)=\\frac\{1\}\{1+\\frac\{s\}\{c^2\}\}；\\rho^\{&\#x27;&\#x27;\}(s)=-\\frac\{1\}\{c^2\}(\\rho^\{&\#x27;\}(s))^2 ρ′(s)=1\+c2s1；ρ′′(s)=−c21(ρ′(s))2  
    控制参数的设定：如果残差s服从正太分布， c : 2.3849 c:2.3849 c:2.3849

1.  **Huber** Loss Function： L δ ( a ) = \{ 1 2 a 2 &MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace;&MediumSpace; ∣ a ∣ ≤ δ δ ∣ a ∣ − 1 2 δ 2 &MediumSpace;&MediumSpace; o t h e r w i s e L\_\\delta (a)=\\left\\\{\\begin\{matrix\} \\frac\{1\}\{2\}a^2\\: \\: \\: \\: \\: \\: \\: \\: \\: \\: \\: \\: \\: \\left | a \\right |\\leq \\delta \\\\ \\delta \\left | a \\right |-\\frac\{1\}\{2\}\\delta^2 \\: \\: otherwise \\end\{matrix\}\\right. Lδ(a)=\{ 21a2∣a∣≤δδ∣a∣−21δ2otherwise  
     a a a相当于残差 f ( x ) f(x) f(x)， δ \\delta δ相当于控制参数  
    控制参数的设定：如果残差a服从正太分布， δ : 1.345 \\delta:1.345 δ:1.345

[20190705085550723.png_pic_center]: /images/20211214/cbf7cc398ab848e8a5e86c180783c946.png
[20190705105712809.png]: /images/20211214/afc2365a56554a5aae54e715e1eec530.png