【理解】无约束非线性优化之下降方法，线搜索

矫情吗；* 2023-07-16 03:37 1阅读 0赞

### 文章目录 ###

*  无约束非线性优化
 *   *  通用下降方法
     *  下降方向
     *  步长
     *  例子

# 无约束非线性优化 #

> Unconstrained Nonlinear Programming

一个典型的UNP问题可以写为：  
 minimize  f ( x ) \\text\{minimize\} \\ f(x) minimize f(x)

## 通用下降方法 ##

> General Descent Method

是一种用迭代的方式求目标函数最小值的方法，每次迭代都会计算搜索方向和步长  
 x k + 1 = x k + t k p k x\_\{k+1\} = x\_k + t\_k p\_k xk\+1=xk\+tkpk

其中， p p p 是搜索方向，  t t t 是步长

之所叫下降方法，是因为满足  f ( x k + 1 ) < f ( x k ) f\\left(x\_\{k+1\}\\right)<f\\left(x\_\{k\}\\right) f(xk\+1)<f(xk)

## 下降方向 ##

> Descent Direction

引入梯度（Gradient）的概念，用  ∇ \\nabla ∇ 来表示，梯度默认指正梯度，这里下降使用的是负梯度，即  − ∇ f ( x ) -\\nabla f(x) −∇f(x) 。只要搜索方向和负梯度方向的夹角小于90°，且步长合适的情况下，都是下降方向，表示为： ∇ f ( x k ) T p k < 0 \\nabla f\\left(x\_\{k\}\\right)^\{T\} p\_\{k\}<0 ∇f(xk)Tpk<0 。

搜索方向有个一般式：  p k = − B k − 1 ∇ f ( x k ) p\_k=−B\_k^\{−1\}\\nabla f(x\_k) pk=−Bk−1∇f(xk)

其中  B k B\_k Bk 是一个对称非奇异矩阵，有以下几种常见的下降方法

1.  梯度下降法（也叫最陡下降法）（Steepest Descent）
    
     B k B\_k Bk 是单位阵，即直接选负梯度为搜索方向，表示为： p k = − ∇ f ( x k ) p\_\{k\}=-\\nabla f\\left(x\_\{k\}\\right) pk=−∇f(xk)
2.  牛顿方法（Newton）
    
     B k = ∇ 2 f ( x k ) B\_k = ∇^2f(x\_k) Bk=∇2f(xk) 是海森（Hessian）矩阵
3.  拟牛顿法
4.  共轭梯度法

补充一点，我们将一般式两边同乘，得到  ∇ f ( x k ) T p k = − ∇ f ( x k ) T B k − 1 ∇ f ( x k ) \\nabla f\\left(x\_\{k\}\\right)^\{T\} p\_k=−\\nabla f\\left(x\_\{k\}\\right)^\{T\} B\_k^\{−1\}\\nabla f(x\_k) ∇f(xk)Tpk=−∇f(xk)TBk−1∇f(xk)，当  B k B\_k Bk 是正定矩阵时， B k − 1 B\_k^\{-1\} Bk−1 也是正定的，因此根据正定的性质，这个式子是满足  ∇ f ( x k ) T p k < 0 \\nabla f\\left(x\_\{k\}\\right)^\{T\} p\_k < 0 ∇f(xk)Tpk<0 的，印证了下降方向。

## 步长 ##

> Stepsize

很多时候我们用的步长是一个固定值，但在这里，我们使用线搜索（Line Search）的方法，每一次迭代都会重新计算步长，有两种方式：

1.  精确线搜索（Exact Line Search）
    
    求解下面这个优化问题，其实很容易理解。步长如果太小，则下降不够快；步长如果太大，则可能不降反升，因此我们想找到步长的一个上界。  
     t k = arg ⁡ min ⁡ α ≥ 0 f ( x k + α p k ) t\_k = \\underset\{\\alpha \\geq 0\}\{\\arg\\min\} f(x\_k + \\alpha p\_k) tk=α≥0argminf(xk\+αpk)
2.  回溯线搜索（Backtracking Line Search）
    
    上面精确计算有时候会很复杂，其实只要近似估计就可以了，设想是先初始化一个较大的步长，然后逐渐缩小，以使得新的函数值与旧的函数值的减少程度大于预设的期望值。可以考虑步长从单位1开始。
    
    如果  f ( x k + t k p k ) > f ( x k ) + α t k ∇ f ( x k ) T p k f(x\_k+t\_k p\_k)>f(x\_k)+\\alpha t\_k \\nabla f(x\_k)^\{T\} p\_k f(xk\+tkpk)>f(xk)\+αtk∇f(xk)Tpk ，则令  t k + 1 = β t k t\_\{k+1\} = \\beta t\_k tk\+1=βtk
    
    其中  α ∈ ( 0 , 0.5 ) \\alpha \\in(0,0.5) α∈(0,0.5)  β ∈ ( 0 , 1 ) \\beta \\in(0,1) β∈(0,1)  t 0 = 1 t\_0 = 1 t0=1
    
     f ( x k + t k p k ) ≤ f ( x k ) + α t k ∇ f ( x k ) T p k f(x\_k+t\_k p\_k) \\leq f(x\_k)+\\alpha t\_k \\nabla f(x\_k)^\{T\} p\_k f(xk\+tkpk)≤f(xk)\+αtk∇f(xk)Tpk 被称为Armijo准则，和  ∇ f ( x k + t k p k ) T p k ≥ α 2 ∇ f ( x k ) T p k \\nabla f\\left(x\_\{k\}+t\_\{k\} p\_\{k\}\\right)^\{T\} p\_\{k\} \\geq \\alpha\_\{2\} \\nabla f(x\_k)^\{T\} p\_\{k\} ∇f(xk\+tkpk)Tpk≥α2∇f(xk)Tpk 一起构成了Wolfe条件

补充：之所以叫线搜索是因为选定的步长  t t t 将决定从直线 \{  x + t p x+tp x\+tp\} 上哪一点开始下一步迭代，其实更准确的应该被叫做射线搜索（Ray Search）

需要知道Armijo准则是一定能满足的，因为只要步长足够小，就一定有  
 f ( x + t Δ x ) ≈ f ( x ) + t ∇ f ( x ) T Δ x < f ( x ) + α t ∇ f ( x ) T Δ x f(x+t \\Delta x) \\approx f(x)+t \\nabla f(x)^\{T\} \\Delta x<f(x)+\\alpha t \\nabla f(x)^\{T\} \\Delta x f(x\+tΔx)≈f(x)\+t∇f(x)TΔx<f(x)\+αt∇f(x)TΔx

## 例子 ##

用梯度下降和精确先搜索方法求解如下问题：  
  minimize  f ( x ) = 1 2 ( x 1 2 + γ x 2 2 ) \\text \{ minimize \} f(x)=\\frac\{1\}\{2\}\\left(x\_\{1\}^\{2\}+\\gamma x\_\{2\}^\{2\}\\right)  minimize f(x)=21(x12\+γx22)

1.  确定搜索方向，这里直接用负梯度：  
     p k = ( − x 1 ( k ) , − γ x 2 ( k ) ) T p\_k = (-x\_\{1(k)\}, -\\gamma x\_\{2(k)\})^T pk=(−x1(k),−γx2(k))T
2.  确定步长：  
     t k = arg ⁡ min ⁡ α ≥ 0 1 2 \[ ( 1 − α ) 2 x 1 ( k ) 2 + γ ( 1 − α γ ) 2 x 2 ( k ) 2 \] t\_k = \\underset\{\\alpha \\geq 0\}\{\\arg\\min\} \\frac\{1\}\{2\}\\left\[(1-\\alpha)^\{2\} x\_\{1(k)\}^\{2\}+\\gamma(1-\\alpha \\gamma)^\{2\} x\_\{2(k)\}^\{2\}\\right\] tk=α≥0argmin21\[(1−α)2x1(k)2\+γ(1−αγ)2x2(k)2\]  
    可以直接用配方法得到：  
     t k = x 1 ( k ) 2 + γ 2 x 2 ( k ) 2 x 1 ( k ) 2 + γ 3 x 2 ( k ) 2 t\_k = \\frac\{x\_\{1(k)\}^2 + \\gamma^2 x\_\{2(k)\}^2\}\{x\_\{1(k)\}^2 + \\gamma^3 x\_\{2(k)\}^2\} tk=x1(k)2\+γ3x2(k)2x1(k)2\+γ2x2(k)2
3.  应用线搜索方法：  
     x k + 1 = x k + x 1 ( k ) 2 + γ 2 x 2 ( k ) 2 x 1 ( k ) 2 + γ 3 x 2 ( k ) 2 ( − x 1 ( k ) , − γ x 2 ( k ) ) T x\_\{k+1\} = x\_k + \\frac\{x\_\{1(k)\}^2 + \\gamma^2 x\_\{2(k)\}^2\}\{x\_\{1(k)\}^2 + \\gamma^3 x\_\{2(k)\}^2\} (-x\_\{1(k)\}, -\\gamma x\_\{2(k)\})^T xk\+1=xk\+x1(k)2\+γ3x2(k)2x1(k)2\+γ2x2(k)2(−x1(k),−γx2(k))T  
    将  x 1 , x 2 x\_1, x\_2 x1,x2 分成两项即：  
     x 1 ( k + 1 ) = x 1 ( k ) − x 1 ( k ) 2 + γ 2 x 2 ( k ) 2 x 1 ( k ) 2 + γ 3 x 2 ( k ) 2 x 1 ( k ) = ( γ − 1 ) γ 2 x 2 ( k ) 2 x 1 ( k ) 2 + γ 3 x 2 ( k ) 2 x 1 ( k ) x\_\{1(k+1)\} = x\_\{1(k)\} - \\frac\{x\_\{1(k)\}^2 + \\gamma^2 x\_\{2(k)\}^2\}\{x\_\{1(k)\}^2 + \\gamma^3 x\_\{2(k)\}^2\} x\_\{1(k)\} = \\frac\{(\\gamma - 1)\\gamma^2 x\_\{2(k)\}^2\}\{x\_\{1(k)\}^2 + \\gamma^3 x\_\{2(k)\}^2\} x\_\{1(k)\} x1(k\+1)=x1(k)−x1(k)2\+γ3x2(k)2x1(k)2\+γ2x2(k)2x1(k)=x1(k)2\+γ3x2(k)2(γ−1)γ2x2(k)2x1(k)
    
     x 2 ( k + 1 ) = x 2 ( k ) − x 1 ( k ) 2 + γ 2 x 2 ( k ) 2 x 1 ( k ) 2 + γ 3 x 2 ( k ) 2 γ x 2 ( k ) = ( 1 − γ ) x 1 ( k ) 2 x 1 ( k ) 2 + γ 3 x 2 ( k ) 2 x 2 ( k ) x\_\{2(k+1)\} = x\_\{2(k)\} - \\frac\{x\_\{1(k)\}^2 + \\gamma^2 x\_\{2(k)\}^2\}\{x\_\{1(k)\}^2 + \\gamma^3 x\_\{2(k)\}^2\} \\gamma x\_\{2(k)\} = \\frac\{(1 - \\gamma) x\_\{1(k)\}^2\}\{x\_\{1(k)\}^2 + \\gamma^3 x\_\{2(k)\}^2\} x\_\{2(k)\} x2(k\+1)=x2(k)−x1(k)2\+γ3x2(k)2x1(k)2\+γ2x2(k)2γx2(k)=x1(k)2\+γ3x2(k)2(1−γ)x1(k)2x2(k)
4.  选择一个初始点开始迭代，这里选一个较特殊的点  x 1 ( 0 ) = γ x\_\{1(0)\} = \\gamma x1(0)=γ， x 2 ( 0 ) = 1 x\_\{2(0)\} = 1 x2(0)=1
    
    当  k = 0 k =0 k=0 时，有：  
     x 1 ( 1 ) = γ ( γ − 1 γ + 1 ) x\_\{1(1)\} = \\gamma\\left(\\frac\{\\gamma-1\}\{\\gamma+1\}\\right) x1(1)=γ(γ\+1γ−1)
    
     x 2 ( 1 ) = − ( γ − 1 γ + 1 ) x\_\{2(1)\} = -\\left(\\frac\{\\gamma-1\}\{\\gamma+1\}\\right) x2(1)=−(γ\+1γ−1)
    
    当  k = 1 k =1 k=1 时，有：  
     x 1 ( 2 ) = γ ( γ − 1 γ + 1 ) 2 x\_\{1(2)\} = \\gamma\\left(\\frac\{\\gamma-1\}\{\\gamma+1\}\\right)^2 x1(2)=γ(γ\+1γ−1)2
    
     x 2 ( 2 ) = − ( γ − 1 γ + 1 ) 2 x\_\{2(2)\} = -\\left(\\frac\{\\gamma-1\}\{\\gamma+1\}\\right)^2 x2(2)=−(γ\+1γ−1)2
    
    通过数学归纳法，我们可以得到一个通式：
    
     x 1 ( k ) = γ ( γ − 1 γ + 1 ) k x\_\{1(k)\} = \\gamma\\left(\\frac\{\\gamma-1\}\{\\gamma+1\}\\right)^k x1(k)=γ(γ\+1γ−1)k
    
     x 2 ( k ) = − ( γ − 1 γ + 1 ) k x\_\{2(k)\} = -\\left(\\frac\{\\gamma-1\}\{\\gamma+1\}\\right)^k x2(k)=−(γ\+1γ−1)k