网站做seo教程,网页设计代码模板代码,菜单栏颜色wordpress,关联词有哪些五年级机器学习笔记之最优化理论与方法——基于无约束优化问题的常用求解方法[上] 引言总体介绍回顾#xff1a;线搜索下降算法收敛速度的衡量方式线性收敛范围高阶收敛范围 二次终止性朴素算法#xff1a;坐标轴交替下降法最速下降法(梯度下降法)梯度下降法的特点 针对最速下降法缺… 机器学习笔记之最优化理论与方法——基于无约束优化问题的常用求解方法[上] 引言总体介绍回顾线搜索下降算法收敛速度的衡量方式线性收敛范围高阶收敛范围 二次终止性朴素算法坐标轴交替下降法最速下降法(梯度下降法)梯度下降法的特点 针对最速下降法缺陷代码示例 引言
本节将介绍无约束优化问题的常用求解方法包括坐标轴交替下降法、最速下降法。 本节是对优化算法(十~十七)最速下降法(梯度下降法)的理论补充其中可能出现一些定理的证明过程这里不再赘述并在相应位置附加链接。 总体介绍
从本节开始将介绍四大类无约束优化问题的常用求解方法
坐标轴交替下降法最速下降法牛顿法拟牛顿法。
这些方法的核心区别在于下降方向选择策略的差异性。通过介绍各算法选择下降方向的方式并延伸至该算法的特点。
回顾线搜索下降算法
关于最小化目标函数 min f ( x ) \min f(x) minf(x)的无约束优化问题线搜索下降算法的迭代步骤表示如下
给定数值解序列 { x k } k 0 ∞ \{x_k\}_{k0}^{\infty} {xk}k0∞的迭代初始点 x 0 ( k 0 ) x_0(k0) x0(k0) 这仅是从数学角度对数值解序列进行描述。如果从算法角度它不可能是一个长度为无穷大的序列。可以通过终止条件使迭代算法停止。判断点 x k x_k xk是否满足终止条件是则终止寻找 x k x_k xk位置的下降方向 D k \mathcal D_k Dk选择合适的步长 α k ≥ 0 \alpha_k \geq 0 αk≥0使得 f ( x k α k ⋅ D k ) f ( x k ) f(x_k \alpha_k \cdot \mathcal D_k) f(x_k) f(xkαk⋅Dk)f(xk)令 x k 1 x k α k ⋅ D k x_{k1} x_k \alpha_k \cdot \mathcal D_k xk1xkαk⋅Dk并令 k k 1 k k1 kk1转步骤 2 2 2。
其中
常用终止条件 ∥ ∇ f ( x k ) ∥ ≤ ϵ \|\nabla f(x_k)\| \leq \epsilon ∥∇f(xk)∥≤ϵ 其中 ϵ \epsilon ϵ是一个较小的正值。例如 1 0 − 6 10^{-6} 10−6。如果满足该条件意味着 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)\}_{k0}^{\infty} {f(xk)}k0∞收敛并不是其达到最优解的充要条件。详见线搜索方法(步长角度非精确搜索)下降方向
针对不同的下降方向选择方式产生不同种类的算法。而我们更关心的是对应算法产生的数值解序列 { x k } k 0 ∞ \{x_k\}_{k0}^{\infty} {xk}k0∞是否能够收敛至最优解 x ∗ x^* x∗如果能够收敛至最优解 x ∗ x^* x∗需要关心它的收敛速度情况。
收敛速度的衡量方式 对应文章详见优化算法(九)收敛速度的简单认识 线性收敛范围
假设数值解序列 { x k } k 0 ∞ ⇒ x ∗ \{x_k\}_{k0}^{\infty} \Rightarrow x^* {xk}k0∞⇒x∗如果存在极限 很明显关于 β \beta β的取值范围 β ∈ [ 0 , 1 ] \beta \in [0,1] β∈[0,1]。
其中当 β 1 \beta1 β1时分母与分子之间的差异性可视作完全相同;换句话说当 k k k充分大时,两者之间的差距确实存在但小到可以忽略不计。称这种收敛方式为次线性收敛。当 0 β 1 0\beta1 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_{k1} - x^*\|}{\|x_k - x^*\|} \beta k⇒∞lim∥xk−x∗∥∥xk1−x∗∥β
根据 β \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_{k1} -x^*\| \frac{1}{2} \|x_k - x^*\| \\ \|x_{k2} - x^*\| \frac{1}{2} \|x_{k1} - x^*\| \frac{1}{4}\|x_k - x^*\| \\ \vdots \\ \end{aligned} \end{cases} ⎩ ⎨ ⎧∥xk1−x∗∥∥xk2−x∗∥⋮21∥xk−x∗∥21∥xk1−x∗∥41∥xk−x∗∥ 可以明显观察到其呈线性的收敛效果。
高阶收敛范围
如果存在 p ≥ 1 p \geq 1 p≥1有 lim k ⇒ ∞ ∥ x k 1 − x ∗ ∥ ∥ x k − x ∗ ∥ p β ∞ \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k1} - x^*\|}{\|x_k - x^*\|^p} \beta \infty k⇒∞lim∥xk−x∗∥p∥xk1−x∗∥β∞ 则称 { x k } \{x_k\} {xk}为 p p p阶收敛。
牛顿法在适当条件下被证明是二阶收敛。可以想象当 p 1 p1 p1时相比于线性收敛范围,高阶收敛必然是更高级别的收敛速度。从而有如下表达 当 p 1 p 1 p1时 p p p阶收敛必然为超线性收敛但反之不一定成立。
验证当 p 1 p 1 p1时可以将上式拆解为如下形式 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_{k1} - x^*\|}{\|x_k - x^*\|^p} \mathop{\lim}\limits_{k \Rightarrow \infty} \left(\frac{\|x_{k1} - x^*\|}{\|x_k - x^*\|} \cdot \frac{1}{\|x_k - x^*\|^{p-1}}\right) k⇒∞lim∥xk−x∗∥p∥xk1−x∗∥k⇒∞lim(∥xk−x∗∥∥xk1−x∗∥⋅∥xk−x∗∥p−11)
其中第一项描述的是线性收敛范围观察第二项 lim k ⇒ ∞ 1 ∥ x k − x ∗ ∥ p − 1 \begin{aligned}\lim_{k \Rightarrow \infty} \frac{1}{\|x_k - x^*\|^{p-1}}\end{aligned} k⇒∞lim∥xk−x∗∥p−11在 p 1 p1 p1条件下其结果是 ∞ \infty ∞。如果需要 lim k ⇒ ∞ ∥ x k 1 − x ∗ ∥ ∥ x k − x ∗ ∥ ⋅ ∞ β ∞ \begin{aligned}\mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k1} - x^*\|}{\|x_k - x^*\|} \cdot \infty \beta \infty\end{aligned} k⇒∞lim∥xk−x∗∥∥xk1−x∗∥⋅∞β∞必然需要 lim k ⇒ ∞ ∥ x k 1 − x ∗ ∥ ∥ x k − x ∗ ∥ 0 \begin{aligned}\mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k1} - x^*\|}{\|x_k - x^*\|} 0\end{aligned} k⇒∞lim∥xk−x∗∥∥xk1−x∗∥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)21xTQxCTxQ≽0 如果针对上述问题在有限迭代步骤内接近最优解我们称该算法具有二次终止性。
朴素算法坐标轴交替下降法
其基本思想表示为给定初始点 x 0 ∈ R n x_0 \in \mathbb R^n x0∈Rn依次沿坐标轴 e 1 , e 2 , ⋯ , e n e_1,e_2,\cdots,e_n e1,e2,⋯,en进行搜素。
关于坐标轴交替下降法,它并不想在迭代步骤中花费代价计算下降方向,而是直接选择坐标轴方向作为下降方向。这与吉布斯采样方法的思想——坐标上升法如出一辙。
对应算法框架表示如下
给定初始点 x 0 ; k 0 ; x_0;k0; x0;k0;依然判断 ∥ ∇ f ( x k ) ∥ ≤ ϵ \|\nabla f(x_k)\| \leq \epsilon ∥∇f(xk)∥≤ϵ如果满足终止记 y 0 x k y_0 x_k y0xk令 { 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 i1,2,\cdots,n \end{cases} {yiyi−1αi⋅eiαiargminf(yi−1α⋅ei)i1,2,⋯,n 解释实际上该步骤是一个 n n n次循环。这里的 y i ( i 1 , 2 , ⋯ , n ) y_i(i1,2,\cdots,n) yi(i1,2,⋯,n)分别表示特征空间中的具体点。这里以二维特征 x k ∈ R 2 ⇒ ( e 1 , e 2 ) x_k \in \mathbb R^2 \Rightarrow (e_1,e_2) xk∈R2⇒(e1,e2)为例使用图像描述该过程 初始状态下 y 0 x k : ( x 1 ( k ) , x 2 ( k ) ) y_0 x_k:(x_1^{(k)},x_2^{(k)}) y0xk:(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 y1y0α1⋅e1可以得到第一次循环结束后更新的位置同上继续循环寻找除去 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_{k1} ynxk1。对应图像表示如下 当然这里 n 2 n2 n2。 在得到 x k 1 y n x_{k1} y_n xk1yn后 k k 1 k k1 kk1并步骤 2 2 2直到满足条件为止。
该算法的优势在于
不需要花费额外代价计算下降方向步骤 3 3 3的循环中 e i ∈ R ( i 1 , 2 , ⋯ , n ) e_i \in \mathbb R(i1,2,\cdots,n) ei∈R(i1,2,⋯,n)因而计算上相对简单。当目标函数 f ( x ) f(x) f(x)中的决策变量 x ∈ R n x \in \mathbb R^n x∈Rn其各分量 x i ( i 1 , 2 , ⋯ , n ) x_i(i1,2,\cdots,n) xi(i1,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_{i1}^n \min f_1(x_1) \end{aligned} minf(x)min[f1(x1)f2(x2)⋯fn(xn)]i1∑nminf1(x1)
相反该算法的劣势在于对于一般问题该算法得到的数值解序列 { x k } k 0 ∞ \{x_k\}_{k0}^{\infty} {xk}k0∞不一定收敛。 如果决策变量内各分量之间的关联性程度较高其产生的结果并不容易收敛吉布斯采样同样存在这种缺陷。
一种改进方法描述将线搜索方法与坐标轴交替下降法交替使用从而使数值解序列收敛。具体改进步骤如下 前面步骤并没有发生变化在通过坐标轴交替下降法找到 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 xk⇒xˉk的方向 D k \mathcal D_k Dk一定是下降方向。 给定初始点 x 0 ; k 0 ; x_0;k0; x0;k0; 依然判断 ∥ ∇ f ( x k ) ∥ ≤ ϵ \|\nabla f(x_k)\| \leq \epsilon ∥∇f(xk)∥≤ϵ如果满足终止 记 y 0 x k y_0 x_k y0xk令 { 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 i1,2,\cdots,n \end{cases} {yiyi−1αi⋅eiαiargminf(yi−1α⋅ei)i1,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:xk⇒xˉk为下降方向使用线搜索方法选择合适步长从而得到新的更新结果 x k 1 x_{k1} xk1 依然是基于 2 2 2维特征对应示例图像表示如下。 得到 x k 1 x_{k1} xk1后 k k 1 kk1 kk1并返回步骤 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)]TD0 那么方向 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)∥⋅∥D∥cosθ 其中 θ \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} ∂D∂Z∣(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)]TD0⇒在 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)]TD0⇒在 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_{k1})]^T[-\nabla f(x_k)] 0 ϕ′(αk)[∇f(xkαk⋅Dk)]TDk[∇f(xk1)]T[−∇f(xk)]0 这意味着梯度向量 ∇ f ( x k 1 ) \nabla f(x_{k1}) ∇f(xk1)与梯度向量 ∇ 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)21x22y2为例使用最速下降法近似求解最优解。对应代码表示如下
import numpy as np
import math
import matplotlib.pyplot as pltdef 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 xdef Derfy(y):return 4 * ydef GradientDescent(stepTime10,epsilon0.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 Nextepsilon / 5.0breakContourList [0.1,0.2,0.5,1.0]LimitParameter 0.0001plt.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,--,ctab:blue)plt.plot(x,y2,--,ctab:blue)plotList list()for (x,y) in LocList:plotList.append((x,y))plt.scatter(x,y,s50,facecolornone,edgecolorstab:red,markero)if len(plotList) 2:continueelse:plt.plot([plotList[0][0],plotList[1][0]],[plotList[0][1],plotList[1][1]],ctab:red)plotList.pop(0)plt.plot([0,2],[0,1],--,ctab:green)plt.show()if __name__ __main__:GradientDescent()对应图像结果表示如下 观察其中绿色虚线表示全局最优方向而红色线均与对应位置点所在等值线的切线相垂直并且相邻路径间也垂直( Z \mathcal Z Z字形)。相比于全局最有方向该方法过程中走了不少弯路~ 而这里的弯路是指单次迭代步骤的最优方向。
该函数是一个凸二次函数由于函数简单因而代码中通过采样的方式来找出每次迭代步骤的近似最优解。但如果使用 Wolfe \text{Wolfe} Wolfe准则方式寻找迭代优质解可能不会找的那么精确。随着迭代步骤的增加最速下降法后期在最优解附近振动而不容易收敛至最优解。 Reference \text{Reference} Reference 最优化理论与方法-第六讲-无约束优化问题二
