机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上)

这篇具有很好参考价值的文章主要介绍了机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言

本节将介绍无约束优化问题的常用求解方法,包括坐标轴交替下降法、最速下降法

本节是对优化算法(十~十七)最速下降法(梯度下降法)的理论补充,其中可能出现一些定理的证明过程这里不再赘述,并在相应位置附加链接

总体介绍

从本节开始,将介绍四大类无约束优化问题的常用求解方法:

  • 坐标轴交替下降法
  • 最速下降法
  • 牛顿法
  • 拟牛顿法

这些方法的核心区别在于:下降方向选择策略的差异性。通过介绍各算法选择下降方向的方式,并延伸至该算法的特点。

回顾:线搜索下降算法

关于最小化目标函数 min ⁡ f ( x ) \min f(x) minf(x)无约束优化问题线搜索下降算法迭代步骤表示如下:

  • 给定数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk}k=0的迭代初始点 x 0 ( k = 0 ) x_0(k=0) x0(k=0)
    这仅是从数学角度对数值解序列进行描述。如果从算法角度,它不可能是一个长度为无穷大的序列。可以通过终止条件使迭代算法停止。
  • 判断 x k x_k xk是否满足终止条件:是,则终止;
  • 寻找 x k x_k xk位置的下降方向 D k \mathcal D_k Dk
  • 选择合适的步长 α k ≥ 0 \alpha_k \geq 0 αk0,使得:
    f ( x k + α k ⋅ D k ) < f ( x k ) f(x_k + \alpha_k \cdot \mathcal D_k) < f(x_k) f(xk+αkDk)<f(xk)
  • 令: x k + 1 = x k + α k ⋅ D k x_{k+1} = x_k + \alpha_k \cdot \mathcal D_k xk+1=xk+αkDk;并令 k = k + 1 k = k+1 k=k+1,转步骤 2 2 2

其中:

  • 常用终止条件 ∥ ∇ f ( x k ) ∥ ≤ ϵ \|\nabla f(x_k)\| \leq \epsilon ∥∇f(xk)ϵ
    • 其中 ϵ \epsilon ϵ是一个较小的正值。例如 1 0 − 6 10^{-6} 106
    • 如果满足该条件,意味着: x k x_k xk点处的梯度 ∇ f ( x k ) \nabla f(x_k) f(xk)已经充分接近于 0 0 0
  • 步长选择方式:基于区间的直接搜索法;非精确搜索准则(五~七);
    包括 Armijo,Glodstein,Wolfe \text{Armijo,Glodstein,Wolfe} Armijo,Glodstein,Wolfe准则。因为仅仅让 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk)}k=0收敛并不是其达到最优解的充要条件。详见线搜索方法(步长角度;非精确搜索)
  • 下降方向

针对不同的下降方向选择方式,产生不同种类的算法。而我们更关心的是对应算法产生的数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk}k=0是否能够收敛至最优解 x ∗ x^* x,如果能够收敛至最优解 x ∗ x^* x,需要关心它的收敛速度情况

收敛速度的衡量方式

对应文章详见:优化算法(九)收敛速度的简单认识

线性收敛范围

假设数值解序列 { x k } k = 0 ∞ ⇒ x ∗ \{x_k\}_{k=0}^{\infty} \Rightarrow x^* {xk}k=0x,如果存在极限
很明显,关于 β \beta β的取值范围: β ∈ [ 0 , 1 ] \beta \in [0,1] β[0,1]

  • 其中当 β = 1 \beta=1 β=1时,分母与分子之间的差异性可视作完全相同;换句话说,当 k k k充分大时,两者之间的差距确实存在,但小到可以忽略不计。称这种收敛方式为次线性收敛
  • 0 < β < 1 0<\beta<1 0<β<1时,可以明显观察到分母与分子之间存在比值的大小关系;通过该比值 β \beta β可以明显观察到迭代过程中呈线性的收敛效果
  • β = 0 \beta = 0 β=0时,和 β = 1 \beta = 1 β=1相反,当 k k k充分大时,分母与分子之间的差距足够大,甚至分子与分母相比,小到可以忽略不计
    lim ⁡ k ⇒ ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ = β \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} = \beta klimxkxxk+1x=β

根据 β \beta β的不同取值,有:

  • 0 < β < 1 0 < \beta < 1 0<β<1时,称数值解序列 { x k } \{x_k\} {xk}线性收敛
  • β = 0 \beta = 0 β=0时,则称数值解序列 { x k } \{x_k\} {xk}超线性收敛

示例:假设 β = 1 2 \begin{aligned}\beta = \frac{1}{2}\end{aligned} β=21,那么:
{ ∥ x k + 1 − x ∗ ∥ = 1 2 ∥ x k − x ∗ ∥ ∥ x k + 2 − x ∗ ∥ = 1 2 ∥ x k + 1 − x ∗ ∥ = 1 4 ∥ x k − x ∗ ∥ ⋮ \begin{cases} \begin{aligned} \|x_{k+1} -x^*\| & = \frac{1}{2} \|x_k - x^*\| \\ \|x_{k+2} - x^*\| & = \frac{1}{2} \|x_{k+1} - x^*\| = \frac{1}{4}\|x_k - x^*\| \\ \vdots \\ \end{aligned} \end{cases} xk+1xxk+2x=21xkx=21xk+1x=41xkx
可以明显观察到其呈线性的收敛效果。

高阶收敛范围

如果存在 p ≥ 1 p \geq 1 p1,有:
lim ⁡ k ⇒ ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ p = β < + ∞ \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|^p} = \beta < +\infty klimxkxpxk+1x=β<+
则称 { x k } \{x_k\} {xk} p p p阶收敛

  • 牛顿法在适当条件下被证明是二阶收敛
  • 可以想象,当 p > 1 p>1 p>1时,相比于线性收敛范围,高阶收敛必然是更高级别的收敛速度。从而有如下表达
    p > 1 p > 1 p>1时, p p p阶收敛必然为超线性收敛,但反之不一定成立。

验证:当 p > 1 p > 1 p>1时,可以将上式拆解为如下形式:
lim ⁡ k ⇒ ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ p = lim ⁡ k ⇒ ∞ ( ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ ⋅ 1 ∥ x k − x ∗ ∥ p − 1 ) \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|^p} = \mathop{\lim}\limits_{k \Rightarrow \infty} \left(\frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} \cdot \frac{1}{\|x_k - x^*\|^{p-1}}\right) klimxkxpxk+1x=klim(xkxxk+1xxkxp11)

  • 其中第一项描述的是线性收敛范围;观察第二项: lim ⁡ k ⇒ ∞ 1 ∥ x k − x ∗ ∥ p − 1 \begin{aligned}\lim_{k \Rightarrow \infty} \frac{1}{\|x_k - x^*\|^{p-1}}\end{aligned} klimxkxp11 p > 1 p>1 p>1条件下,其结果是 + ∞ +\infty +
  • 如果需要 lim ⁡ k ⇒ ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ ⋅ ∞ = β < ∞ \begin{aligned}\mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} \cdot \infty = \beta < \infty\end{aligned} klimxkxxk+1x=β<,必然需要 lim ⁡ k ⇒ ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ = 0 \begin{aligned}\mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} = 0\end{aligned} klimxkxxk+1x=0,即超线性收敛

二次终止性

关于判断一个算法的优劣性,除去收敛速度这个评价标准外,优化问题本身也可以作为算法优劣性的评价标准。算法针对某类简单问题

  • 可能无法在有限迭代步骤内实现收敛;
  • 可能会在有限迭代步骤内实现收敛,但计算代价过大

这样的算法本身存在问题。相反,如何衡量简单问题的基准 ? ? ?通常将目标函数为凸二次函数作为基准:
矩阵 Q \mathcal Q Q至少是半正定矩阵
f ( x ) = 1 2 x T Q x + C T x Q ≽ 0 f(x) = \frac{1}{2}x^T \mathcal Qx + \mathcal C^T x \quad \mathcal Q \succcurlyeq 0 f(x)=21xTQx+CTxQ0
如果针对上述问题在有限迭代步骤内接近最优解,我们称该算法具有二次终止性

朴素算法:坐标轴交替下降法

基本思想表示为:给定初始点 x 0 ∈ R n x_0 \in \mathbb R^n x0Rn,依次沿坐标轴 e 1 , e 2 , ⋯   , e n e_1,e_2,\cdots,e_n e1,e2,,en进行搜素

  • 关于坐标轴交替下降法,它并不想在迭代步骤中花费代价计算下降方向,而是直接选择坐标轴方向作为下降方向。
  • 这与吉布斯采样方法的思想——坐标上升法如出一辙。

对应算法框架表示如下:

  • 给定初始点 x 0 ; k = 0 ; x_0;k=0; x0;k=0;
  • 依然判断 ∥ ∇ f ( x k ) ∥ ≤ ϵ \|\nabla f(x_k)\| \leq \epsilon ∥∇f(xk)ϵ:如果满足,终止;
  • y 0 = x k y_0 = x_k y0=xk,令:
    { y i = y i − 1 + α i ⋅ e i α i = arg ⁡ min ⁡ f ( y i − 1 + α ⋅ e i ) i = 1 , 2 , ⋯   , n \begin{cases} y_i = y_{i-1} + \alpha_i \cdot e_i \\ \alpha_i = \mathop{\arg\min} f(y_{i-1} + \alpha \cdot e_i) \quad i=1,2,\cdots,n \end{cases} {yi=yi1+αieiαi=argminf(yi1+αei)i=1,2,,n
    解释:实际上该步骤是一个 n n n次循环。这里的 y i ( i = 1 , 2 , ⋯   , n ) y_i(i=1,2,\cdots,n) yi(i=1,2,,n)分别表示特征空间中的具体点。这里以二维特征 x k ∈ R 2 ⇒ ( e 1 , e 2 ) x_k \in \mathbb R^2 \Rightarrow (e_1,e_2) xkR2(e1,e2)为例,使用图像描述该过程:
    • 初始状态下, y 0 = x k : ( x 1 ( k ) , x 2 ( k ) ) y_0 = x_k:(x_1^{(k)},x_2^{(k)}) y0=xk:(x1(k),x2(k))
    • 除去 e 1 e_1 e1外,其他维度固定的条件下,此时固定优化方向 e 1 e_1 e1,在该方向上的最优步长 α 1 \alpha_1 α1可表示为关于步长变量 α \alpha α函数 ϕ ( α ) \phi(\alpha) ϕ(α)的最优解
      α 1 = arg ⁡ min ⁡ α ϕ ( α ) = arg ⁡ min ⁡ α f ( y 0 + α ⋅ e 1 ) \alpha_1 = \mathop{\arg\min}\limits_{\alpha} \phi(\alpha) = \mathop{\arg\min}\limits_{\alpha} f(y_0 + \alpha \cdot e_1) α1=αargminϕ(α)=αargminf(y0+αe1)
    • 找到 α 1 \alpha_1 α1后,通过 y 1 = y 0 + α 1 ⋅ e 1 y_1 = y_0 + \alpha_1 \cdot e_1 y1=y0+α1e1可以得到第一次循环结束后更新的位置
    • 同上,继续循环,寻找除去 e 2 e_2 e2外,其他维度固定的条件下,求出 e 2 e_2 e2方向上的最优步长 α 2 \alpha_2 α2,以此类推。直到 n n n个维度全部被遍历一次为止,得到 y n = x k + 1 y_n= x_{k+1} yn=xk+1。对应图像表示如下:
      当然这里 n = 2 n=2 n=2
      机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上),最优化理论与方法,python,坐标轴交替下降法,梯度下降法,梯度下降法的缺陷,坐标上升法,python实现梯度下降法
  • 在得到 x k + 1 = y n x_{k+1} = y_n xk+1=yn后, k = k + 1 k = k+1 k=k+1,并步骤 2 2 2,直到满足条件为止。

该算法的优势在于:

  • 不需要花费额外代价计算下降方向;
  • 步骤 3 3 3的循环中, e i ∈ R ( i = 1 , 2 , ⋯   , n ) e_i \in \mathbb R(i=1,2,\cdots,n) eiR(i=1,2,,n),因而计算上相对简单。
  • 目标函数 f ( x ) f(x) f(x)中的决策变量 x ∈ R n x \in \mathbb R^n xRn,其各分量 x i ( i = 1 , 2 , ⋯   , n ) x_i(i=1,2,\cdots,n) xi(i=1,2,,n)之间的交叉程度很小时,该算法框架会非常有效
    什么是交叉程度很小——可理解为各分量之间的关联关系较小,甚至是线性无关。例如各分量满足可分离函数各分量各算各的~
    min ⁡ f ( x ) = min ⁡ [ f 1 ( x 1 ) + f 2 ( x 2 ) + ⋯ + f n ( x n ) ] = ∑ i = 1 n min ⁡ f 1 ( x 1 ) \begin{aligned} \min f(x) & = \min [f_1(x_1) + f_2(x_2)+\cdots + f_n(x_n)] \\ & = \sum_{i=1}^n \min f_1(x_1) \end{aligned} minf(x)=min[f1(x1)+f2(x2)++fn(xn)]=i=1nminf1(x1)

相反,该算法的劣势在于:对于一般问题,该算法得到的数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk}k=0不一定收敛
如果决策变量内各分量之间的关联性程度较高,其产生的结果并不容易收敛,吉布斯采样同样存在这种缺陷。

一种改进方法描述:线搜索方法坐标轴交替下降法交替使用从而使数值解序列收敛。具体改进步骤如下:
前面步骤并没有发生变化,在通过坐标轴交替下降法找到 x ˉ k \bar{x}_k xˉk后,能够确定: f ( x ˉ k ) ≤ f ( x k ) f(\bar{x}_k) \leq f(x_k) f(xˉk)f(xk),也就是说: x k ⇒ x ˉ k x_k \Rightarrow \bar{x}_k xkxˉk的方向 D k \mathcal D_k Dk一定是下降方向

  • 给定初始点 x 0 ; k = 0 ; x_0;k=0; x0;k=0;

  • 依然判断 ∥ ∇ f ( x k ) ∥ ≤ ϵ \|\nabla f(x_k)\| \leq \epsilon ∥∇f(xk)ϵ:如果满足,终止;

  • y 0 = x k y_0 = x_k y0=xk,令:
    { y i = y i − 1 + α i ⋅ e i α i = arg ⁡ min ⁡ f ( y i − 1 + α ⋅ e i ) i = 1 , 2 , ⋯   , n \begin{cases} y_i = y_{i-1} + \alpha_i \cdot e_i \\ \alpha_i = \mathop{\arg\min} f(y_{i-1} + \alpha \cdot e_i) \quad i=1,2,\cdots,n \end{cases} {yi=yi1+αieiαi=argminf(yi1+αei)i=1,2,,n
    从而得到 x ˉ k \bar{x}_{k} xˉk

  • x ˉ k \bar{x}_k xˉk起始点 D k : x k ⇒ x ˉ k \mathcal D_k:x_k \Rightarrow \bar{x}_k Dk:xkxˉk下降方向使用线搜索方法选择合适步长,从而得到新的更新结果 x k + 1 x_{k+1} xk+1
    依然是基于 2 2 2维特征,对应示例图像表示如下。
    机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上),最优化理论与方法,python,坐标轴交替下降法,梯度下降法,梯度下降法的缺陷,坐标上升法,python实现梯度下降法

  • 得到 x k + 1 x_{k+1} xk+1后, k = k + 1 k=k+1 k=k+1,并返回步骤 2 2 2

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

基本思想表示为:在迭代过程中,选择 x k x_k xk处的负梯度方向作为搜索方向。即: D k = − ∇ f ( x k ) \mathcal D_k = - \nabla f(x_k) Dk=f(xk)
而负梯度方向也被称作最速下降方向

  • 泰勒展开式的角度观察,根据线搜索方法(方向角度)的下降方向的推导过程可知:若判断 x k x_k xk处的某方向 D \mathcal D D是否为下降方向,只需判断:
    [ ∇ f ( x k ) ] T D < 0 [\nabla f(x_k)]^T \mathcal D < 0 [f(xk)]TD<0
    那么方向 D \mathcal D D就是 x k x_k xk位置的下降方向。当 D = − ∇ f ( x k ) \mathcal D = -\nabla f(x_k) D=f(xk)时,能够使 [ ∇ f ( x k ) ] T D [\nabla f(x_k)]^T \mathcal D [f(xk)]TD达到最小值
    这里仅关注向量 ∇ f ( x k ) , D \nabla f(x_k),\mathcal D f(xk),D的方向信息,因而设 ∥ ∇ f ( x k ) ∥ = ∥ D ∥ = 1 \|\nabla f(x_k)\| = \|\mathcal D\| = 1 ∥∇f(xk)=D=1
    [ ∇ f ( x k ) ] T D = ∥ ∇ f ( x k ) ∥ ⋅ ∥ D ∥ cos ⁡ θ [\nabla f(x_k)]^T \mathcal D = \|\nabla f(x_k)\| \cdot \|\mathcal D\| \cos \theta [f(xk)]TD=∥∇f(xk)Dcosθ
    其中 θ \theta θ表示向量 ∇ f ( x k ) , D \nabla f(x_k),\mathcal D f(xk),D(不分先后)之间的夹角。当 D , ∇ f ( x k ) \mathcal D,\nabla f(x_k) D,f(xk)之间夹角为 π 2 \begin{aligned}\frac{\pi}{2}\end{aligned} 2π时,能够取到 cos ⁡ θ \cos \theta cosθ最小值 − 1 -1 1
  • 如果从方向导数的角度观察: [ ∇ f ( x k ) ] T D [\nabla f(x_k)]^T \mathcal D [f(xk)]TD,它可以看作: x k x_k xk所在位置处关于 D \mathcal D D的方向导数。在凸函数铺垫:梯度与方向导数中介绍过,对应方向导数可表示为:
    这里示例 x k x_k xk是二维特征,坐标为 ( x , y ) (x,y) (x,y)
    ∂ Z ∂ D ∣ ( x , y ) = f x ( x k ) ⋅ cos ⁡ α + f y ( x k ) ⋅ cos ⁡ β = [ f x ( x k ) , f y ( x k ) ] ⏟ [ ∇ f ( x k ) ] T ( cos ⁡ α cos ⁡ β ) = [ ∇ f ( x k ) ] T D \begin{aligned} \frac{\partial \mathcal Z}{\partial \mathcal D}\mid_{(x,y)} & = f_x(x_k) \cdot \cos \alpha + f_y(x_k) \cdot \cos \beta \\ & = \underbrace{[f_x(x_k),f_y(x_k)]}_{[\nabla f(x_k)]^T} \begin{pmatrix} \cos \alpha \\ \cos \beta \end{pmatrix} \\ & = [\nabla f(x_k)]^T \mathcal D \end{aligned} DZ(x,y)=fx(xk)cosα+fy(xk)cosβ=[f(xk)]T [fx(xk),fy(xk)](cosαcosβ)=[f(xk)]TD
    关于方向导数的性质
    这意味着: [ ∇ f ( x k ) ] T D [\nabla f(x_k)]^T \mathcal D [f(xk)]TD达到最小值,意味着函数值下降的越剧烈
    • [ ∇ f ( x k ) ] T D > 0 ⇒ [\nabla f(x_k)]^T \mathcal D > 0 \Rightarrow [f(xk)]TD>0 x k x_k xk位置沿着 D \mathcal D D方向的函数值上升;反之, [ ∇ f ( x k ) ] T D < 0 ⇒ [\nabla f(x_k)]^T \mathcal D < 0 \Rightarrow [f(xk)]TD<0 x k x_k xk位置沿着 D \mathcal D D方向的函数值下降
    • ∣ ∇ f ( x k ) T D ∣ |\nabla f(x_k)^T \mathcal D| ∣∇f(xk)TD越大 ⇒ \Rightarrow 上升/下降的越猛烈;反之, ∣ ∇ f ( x k ) T D ∣ |\nabla f(x_k)^T \mathcal D| ∣∇f(xk)TD越小 ⇒ \Rightarrow 上升/下降的越平缓

梯度下降法的特点

优点
梯度下降法能够收敛,并且其下降方向被指定为负梯度方向 − ∇ f ( x k ) -\nabla f(x_k) f(xk)

缺陷

  • 收敛速度,即便是在凸函数甚至是强凸函数最快也只能达到线性收敛
    相关证明见:梯度下降法在强凸函数上的收敛性证明以及梯度下降法在凸函数上的收敛性。

    归纳:

    • 梯度下降法仅使用负梯度方向作为搜索方向,换句话说:在考虑搜索方向的过程中,仅考虑了一阶梯度 ∇ f ( ⋅ ) \nabla f(\cdot) f()信息;实际上,二阶梯度信息 ( Hessian Matrix ) (\text{Hessian Matrix}) (Hessian Matrix)也可以用来判断搜索方向

    • 其次,假设在最速下降法的过程中,由于方向 D k \mathcal D_k Dk已被确定,那么最优步长 α k \alpha_k αk是关于 ϕ ( α ) = f ( x k + α ⋅ D k ) \phi(\alpha) = f(x_k + \alpha \cdot \mathcal D_k) ϕ(α)=f(xk+αDk)精确最小点
      α k = arg ⁡ min ⁡ α ϕ ( α ) = arg ⁡ min ⁡ α f ( x k + α ⋅ D k ) \alpha_k = \mathop{\arg\min}\limits_{\alpha} \phi(\alpha) =\mathop{\arg\min}\limits_{\alpha} f(x_k + \alpha \cdot \mathcal D_k) αk=αargminϕ(α)=αargminf(xk+αDk)
      ϕ ′ ( α ) ≜ 0 \phi'(\alpha) \triangleq 0 ϕ(α)0,必然有:
      ϕ ′ ( α k ) = [ ∇ f ( x k + α k ⋅ D k ) ] T D k = [ ∇ f ( x k + 1 ) ] T [ − ∇ f ( x k ) ] = 0 \phi'(\alpha_k) = [\nabla f(x_k + \alpha_k \cdot \mathcal D_k)]^T \mathcal D_k = [\nabla f(x_{k+1})]^T[-\nabla f(x_k)] = 0 ϕ(αk)=[f(xk+αkDk)]TDk=[f(xk+1)]T[f(xk)]=0
      这意味着:梯度向量 ∇ f ( x k + 1 ) \nabla f(x_{k+1}) f(xk+1)与梯度向量 ∇ f ( x k ) \nabla f(x_k) f(xk)垂直。
      而这个垂直于 Z \mathcal Z Z字形的缺陷是同一个缺陷:它仅能在迭代步骤中找到局部最优方向,而不是全局最优方向。也就是说:梯度下降法是一个贪心算法

  • ZigZag \text{ZigZag} ZigZag现象:在迭代过程中,其收敛路径呈 Z \mathcal Z Z字形
    见下方代码示例与图像。可以看出:其搜索路径呈线 Z \mathcal Z Z字形,并且每一次迭代的方向均不是全局最优

  • 不具备二次终止性,也就是说:关于凸二次函数的最优化问题,仅仅通过有限次迭代步骤,无法收敛至最优解

针对最速下降法缺陷代码示例

针对梯度下降法上述缺陷问题,以凸二次函数最优化问题 min ⁡ f ( x , y ) = 1 2 x 2 + 2 y 2 \begin{aligned}\min f(x,y) = \frac{1}{2} x^2 + 2 y^2\end{aligned} minf(x,y)=21x2+2y2为例,使用最速下降法近似求解最优解。对应代码表示如下:

import numpy as np
import math
import matplotlib.pyplot as plt


def f(x,y):
    return 0.5 * (x ** 2) + 2 * (y ** 2)

def ConTourFunction(x,Contour):
    return math.sqrt(0.5 * (Contour - (0.5 * (x ** 2))))

def Derfx(x):
    return x

def Derfy(y):
    return 4 * y

def GradientDescent(stepTime=10,epsilon=0.1):
    Start = (2.0,1.0)
    LocList = list()
    LocList.append(Start)

    for _ in range(stepTime):

        DerStart = (Derfx(Start[0]),Derfy(Start[1]))
        for step in list(np.linspace(0.0,1.0,1000)):
            Next = (Start[0] - (DerStart[0] * step),Start[1] - (DerStart[1] * step))
            DerfNext = Derfx(Next[0]) * (-1 * DerStart[0]) + Derfy(Next[1]) * (-1 * DerStart[1])

            if abs(DerfNext) <= epsilon:
                LocList.append(Next)
                Start = Next
                epsilon /= 5.0
                break

    ContourList = [0.1,0.2,0.5,1.0]
    LimitParameter = 0.0001
    plt.figure(figsize=(10,5))
    for Contour in ContourList:
    	# 设置范围时,需要满足x的定义域描述。
        x = np.linspace(-1 * math.sqrt(2 * Contour) + LimitParameter,math.sqrt(2 * Contour) - LimitParameter,200)
        y1 = [ConTourFunction(i,Contour) for i in x]
        y2 = [-1 * j for j in y1]
        plt.plot(x,y1,'--',c="tab:blue")
        plt.plot(x,y2,'--',c="tab:blue")

    plotList = list()
    for (x,y) in LocList:
        plotList.append((x,y))
        plt.scatter(x,y,s=50,facecolor="none",edgecolors="tab:red",marker='o')
        if len(plotList) < 2:
            continue
        else:
            plt.plot([plotList[0][0],plotList[1][0]],[plotList[0][1],plotList[1][1]],c="tab:red")
            plotList.pop(0)
            
    plt.plot([0,2],[0,1],'--',c="tab:green")
    plt.show()

if __name__ == '__main__':
    GradientDescent()

对应图像结果表示如下:
机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上),最优化理论与方法,python,坐标轴交替下降法,梯度下降法,梯度下降法的缺陷,坐标上升法,python实现梯度下降法
观察:其中绿色虚线表示全局最优方向;而红色线均与对应位置点所在等值线的切线相垂直;并且相邻路径间也垂直( Z \mathcal Z Z字形)。相比于全局最有方向,该方法过程中走了不少弯路~
而这里的弯路是指单次迭代步骤的最优方向

该函数是一个凸二次函数,由于函数简单,因而代码中通过采样的方式来找出每次迭代步骤的近似最优解。但如果使用 Wolfe \text{Wolfe} Wolfe准则方式寻找迭代优质解,可能不会找的那么精确。随着迭代步骤的增加,最速下降法后期在最优解附近振动,而不容易收敛至最优解。

Reference \text{Reference} Reference
最优化理论与方法-第六讲-无约束优化问题(二)文章来源地址https://www.toymoban.com/news/detail-695605.html

到了这里,关于机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器学习笔记之最优化理论与方法(二)凸集的简单认识(上)

    本节将介绍关于 凸集 的基本信息,包括 概念 、 基本性质 以及常见凸集。 在 最优化问题 范畴中, 凸优化问题 是一类常见的、并且 性质优秀 的优化问题。一些情况下可以通过 凸优化问题 来解决 非凸优化问题 。 而 凸集合与凸函数 决定了该优化问题是 凸优化问题 。具体

    2024年02月10日
    浏览(38)
  • 无约束最优化方法

    求解无约束最优化的基本思路 给定初始点 x 0 ∈ R n , k = 0 x_0in mathbb{R}^n,k=0 x 0 ​ ∈ R n , k = 0 判断当前解是否满足终止准则,若满足则停止迭代,若不满足则转3. 确定 f ( x ) f(x) f ( x ) 在 x k x_k x k ​ 点的下降方向 确定步长 λ k lambda_k λ k ​ ,使 f ( x k + λ k d k ) f(x_k+lambda_

    2023年04月08日
    浏览(96)
  • 最优化理论笔记及期末复习(《数值最优化》——高立)

    8.3.1实验内容 利用Matlab编程,实现采用简单Armijo非精确线搜索求步长的三种方法:负梯度法、BFGS法及FR共轭梯度法,并求解如下无约束优化问题: m i n f ( x ) = 10 ( x 1 3 − x 2 ) 2 + ( x 1 − 1 ) 2 min f(x) =10(x_1^3-x_2)^2+(x_1-1)^2 m i n f ( x ) = 1 0 ( x 1 3 ​ − x 2 ​ ) 2 + ( x 1 ​ − 1 ) 2 通过

    2024年02月02日
    浏览(41)
  • (最优化理论与方法)第一章最优化简介-第二节:最优化典型实例之稀疏优化和低秩矩阵恢复

    考虑下面线性方程组的求解问题,其中 x ∈ R n , b ∈ R m xin R^{n},bin R^{m} x ∈ R n , b ∈ R m ,矩阵 A ∈ R m × n Ain R^{m×n} A ∈ R m × n ,且向量 b b b 的维数远小于向量 x x x 的维数,也即 m m m n n n A x = b Ax=b A x = b 在相关问题中,当我们建立这样的模型后,常常希望 解出向量

    2024年02月08日
    浏览(44)
  • 25.9 matlab里面的10中优化方法介绍—— 惩罚函数法求约束最优化问题(matlab程序)

    1. 简述          一、算法原理 1、问题引入 之前我们了解过的算法大部分都是无约束优化问题,其算法有:黄金分割法,牛顿法,拟牛顿法,共轭梯度法,单纯性法等。但在实际工程问题中,大多数优化问题都属于有约束优化问题。惩罚函数法就可以将约束优化问题转化为

    2024年02月15日
    浏览(33)
  • 最优化:建模、算法与理论(最优性理论2

    考虑优化问题 min ⁡ x ∈ R n 1 2 ∣ ∣ x − y ∣ ∣ 2 2 , s . t . A x = b min_{x{in}R^n}frac{1}{2}||x-y||_2^2,\\\\ s.t.{quad}Ax=b x ∈ R n min ​ 2 1 ​ ∣∣ x − y ∣ ∣ 2 2 ​ , s . t . A x = b 其中 A ∈ R m × n , b ∈ R m , y ∈ R n A{in}R^{m times n},b{in}R^m,y{in}R^n A ∈ R m × n , b ∈ R m , y ∈ R n 为给定的矩阵

    2024年02月07日
    浏览(43)
  • 【机器学习】最大熵模型【下】最大熵模型学习的最优化算法

    有任何的书写错误、排版错误、概念错误等,希望大家包含指正。 由于字数限制,分成两篇博客。 【机器学习】最大熵模型【上】最大熵模型概述与约束最优化问题 【机器学习】最大熵模型【下】最大熵模型学习的最优化算法 这里的最优化算法就是用于训练最大熵模型参数

    2023年04月15日
    浏览(51)
  • 最优化学习笔记——第三章

    非线性规划比线性规划更困难,没有统一的数学模型,有自己特定的适用范围,目前还没有通用于所有问题的非线性规划问题的算法 满足以上条件的解释可行解,所有解为可行域,如果可行域=R n ,则为无约束问题,否则为有约束问题 如果所有的约束与目标函数都是凸函数,

    2024年02月03日
    浏览(78)
  • 最优化:建模、算法与理论(优化建模)

    目前在学习 最优化:建模、算法与理论这本书,来此记录一下,顺便做一些笔记,在其中我也会加一些自己的理解,尽量写的不会那么的条条框框(当然最基础的还是要有) 本章将从常用的建模技巧开始,接着介绍统计学、信号处理、图像处理以及机器学习中常见的优化模

    2024年02月10日
    浏览(187)
  • 最优化:建模、算法与理论(典型优化问题

    4.1.1 基本形式和应用背景 再次说明一下,其实这本书很多的内容之前肯定大家都学过,但是我觉得这本书和我们之前学的东西的出发角度不一样,他更偏向数学,也多一个角度让我们去理解 线性规划问题的一般形式如下: min ⁡ x ∈ R n c T x s . t . A x = b G x ≤ e (4.1.1) min_{x{

    2024年02月09日
    浏览(246)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包