文章目录
最速下降法(The steepest descent method)最速下降法的原理Python实现最速下降法实例`sympy`包中用到的函数构建符号变量和符号函数对符号函数求导求函数值求解方程的零点 Python实现最速下降法求解上述算例的完整代码.[TOC].
最速下降法(The steepest descent method)
本文中的课件来自清华大学深圳国际研究生院，物流与交通学部张灿荣教授《高级运筹学》课程。
在无约束非线性函数的最优化中，最速下降法(The steepest descent method)是一个著名的基础算法。本文就来用一个实例来学习最速下降法。
最速下降法的原理
假设有一个多元非线性函数 f ( x 1 , x 2 , ⋯ , x n ) f(x_1, x_2, \cdots, x_n) f(x1,x2,⋯,xn)，其定义域为 x ∈ R n x \in \mathbb{R}^n x∈Rn, 那么如何求该函数的最大值或者最小值呢？
当然，我们可以用求导的方法。但是有些时候直接求导并不方便，此时我们可以用最速下降法来求解。
最速下降法的基本思想就是：
从一个初始点开始，逐步沿着以当前点为基准，函数值变化最快的方向走，一直走到最优解为止。因此，在有了一个初始点以后，我们就需要决策以下两个事情：
（1）下一步要朝着什么方向走(
方向);（2）沿着该方向走多远(
步长)。
具体如何选择方向和步长，见下面的PPT。
下图是一个很直观的例子，在当前点，沿着不同的方向走，函数值的变化速度是不同的，但是在等高线的切线的垂直方向，是变化最快的。
也就是说，我们得去找平行于该点梯度的方向，沿着这个方向(当为max问题)或者沿着这个方向的反方向(当为min问题)去更新当前位置。
就像上图一样，一步一步，最终走到最优解对应的点。
Python实现最速下降法实例
我们看下面的函数
f ( x 1 , x 2 ) = 2 x 1 x 2 + 2 x 2 − x 1 2 − 2 x 2 2 , x 1 , x 2 ∈ R 1 \begin{aligned} f(x_1,x_2)=&2x_1x_2 +2x_2-x_1^2-2x_2^2 , \\ &x_1, x_2 \in \mathbb{R^1} \end{aligned} f(x1,x2)=2x1x2+2x2−x12−2x22,x1,x2∈R1
给定初始点 ( 0.5 , 0.5 ) (0.5, 0.5) (0.5,0.5)，用最速下降法找到该函数的最大值。
我们用python中的sympy包来实现最速下降法求解上面的问题。
首先，我们来介绍我们将要用到的sympy包中的几个函数。结合jupyter notebook来给大家做个展示。ps.这个包还是挺好用的，结合jupyter notebook之后，可视化非常不错，所见即所得。
sympy包中用到的函数
构建符号变量和符号函数
from sympy import * x_1 = symbols('x_1')x_2 = symbols('x_2') fun = 2 * x_1 * x_2 + 2 * x_2 - x_1**2 - 2 * x_2**2fun
这个是用来构造两个符号变量 x 1 , x 2 x_1, x_2 x1,x2，就像代数中用字母代替变量一样。然后可以定义出我们的函数
f ( x 1 , x 2 ) = 2 x 1 x 2 + 2 x 2 − x 1 2 − 2 x 2 2 , \begin{aligned} f(x_1,x_2)=&2x_1x_2 +2x_2-x_1^2-2x_2^2 , \end{aligned} f(x1,x2)=2x1x2+2x2−x12−2x22,
jupyter notebook中的显示效果是这样的
可以看到jupyter notebook中直接就显示出了数学公式格式的形式，这是因为jupyter notebook中内嵌了LaTeX相关支持包的缘故。总之这样可视化就非常不错。
对符号函数求导
下面我们来计算 f ( x 1 , x 2 ) f(x_1,x_2) f(x1,x2)的偏导数， ∂ f ∂ x 1 \frac{\partial f}{\partial x_1} ∂x1∂f，代码很简单，用函数diff(函数, 变量)
grad_1 = diff(fun, x_1) grad_1
如下图
求函数值
有了符号函数，我们怎么知道自变量 x 1 , x 2 x_1, x_2 x1,x2取具体值得时候，符号函数的取值呢？我们用函数函数.subs({变量1:变量1的取值, ....}).evalf()，具体代码为
fun_value = fun.subs({x_1:4, x_2: 2}).evalf()fun_value
如果说只有一个变量已知，那就是下面的情况
fun_value = fun.subs({x_1:4, x_2: 2}).evalf()fun_value
还是非常智能的。
求解方程的零点
为了寻找下降速度最快的方向，我们需要利用之前PPT中的方法去求解方程组。这里我们用到函数solve(函数，变量)
我们举一个例子，假设有函数
g ( x ) = 4 x + 5 \begin{aligned} g(x) = 4x + 5 \end{aligned} g(x)=4x+5
我们求解
g ( x ) = 4 x + 5 = 0 \begin{aligned} g(x) = 4x + 5 = 0 \end{aligned} g(x)=4x+5=0
OK，准备好了上述函数，我们就可以开心的把最速下降法写出来了。具体代码见接下来的部分。
Python实现最速下降法求解上述算例的完整代码
import mathfrom sympy import *# define symbol variablex_1 = symbols('x_1')x_2 = symbols('x_2')# define objective function fun = 2 * x_1 * x_2 + 2 * x_2 - x_1 ** 2 - 2 * x_2 ** 2fun# take derivative of x_1 and x_2 grad_1 = diff(fun, x_1)grad_2 = diff(fun, x_2)# define parametersMaxIter = 100 epsilon = 0.0001# define initial point x_1_value = 0.5x_2_value = 0.5iter_cnt = 0current_step_size = 10000 grad_1_value = (float)(grad_1.subs({x_1:x_1_value, x_2: x_2_value}).evalf())grad_2_value = (float)(grad_2.subs({x_1:x_1_value, x_2: x_2_value}).evalf()) current_obj = fun.subs({x_1: x_1_value, x_2: x_2_value}).evalf()print('itCnt: %2d cur_point (%3.2f, %3.2f) cur_Obj: %5.4fgrad_1: %5.4fgrad_2 : %5.4fstep_size : %5.4f' % (iter_cnt, x_1_value, x_2_value, current_obj, grad_1_value, grad_2_value, current_step_size)) # while (iter_cnt <= MaxIter and abs(grad_1_value) + abs(grad_2_value) >= epsilon):while(abs(grad_1_value) + abs(grad_2_value) >= epsilon): iter_cnt += 1# find the step sizet = symbols('t')x_1_updated = x_1_value + grad_1_value * tx_2_updated = x_2_value + grad_2_value * tFun_updated = fun.subs({x_1: x_1_updated, x_2: x_2_updated})grad_t = diff(Fun_updated, t)t_value = solve(grad_t, t)[0] # solve grad_t == 0# update x_1_value and x_2_valuegrad_1_value = (float)(grad_1.subs({x_1: x_1_value, x_2: x_2_value}).evalf()) grad_2_value = (float)(grad_2.subs({x_1: x_1_value, x_2: x_2_value}).evalf()) x_1_value = (float)(x_1_value + t_value * grad_1_value)x_2_value = (float)(x_2_value + t_value * grad_2_value) current_obj = fun.subs({x_1: x_1_value, x_2: x_2_value}).evalf()current_step_size = t_valueprint('itCnt: %2d cur_point (%3.2f, %3.2f) cur_Obj: %5.4fgrad_1: %5.4fgrad_2 : %5.4fstep_size : %5.4f' % (iter_cnt, x_1_value, x_2_value, current_obj, grad_1_value, grad_2_value, current_step_size))
运行结果如下
itCnt: 0 cur_point (0.50, 0.50) cur_Obj: 0.7500grad_1: 0.0000grad_2 : 1.0000step_size : 10000.0000itCnt: 1 cur_point (0.50, 0.75) cur_Obj: 0.8750grad_1: 0.0000grad_2 : 1.0000step_size : 0.2500itCnt: 2 cur_point (0.50, 0.75) cur_Obj: 0.8750grad_1: 0.5000grad_2 : 0.0000step_size : 0.0000itCnt: 3 cur_point (0.75, 0.75) cur_Obj: 0.9375grad_1: 0.5000grad_2 : 0.0000step_size : 0.5000itCnt: 4 cur_point (0.75, 0.75) cur_Obj: 0.9375grad_1: 0.0000grad_2 : 0.5000step_size : 0.0000itCnt: 5 cur_point (0.75, 0.88) cur_Obj: 0.9688grad_1: 0.0000grad_2 : 0.5000step_size : 0.2500itCnt: 6 cur_point (0.75, 0.88) cur_Obj: 0.9688grad_1: 0.2500grad_2 : 0.0000step_size : 0.0000itCnt: 7 cur_point (0.88, 0.88) cur_Obj: 0.9844grad_1: 0.2500grad_2 : 0.0000step_size : 0.5000itCnt: 8 cur_point (0.88, 0.88) cur_Obj: 0.9844grad_1: 0.0000grad_2 : 0.2500step_size : 0.0000itCnt: 9 cur_point (0.88, 0.94) cur_Obj: 0.9922grad_1: 0.0000grad_2 : 0.2500step_size : 0.2500itCnt: 10 cur_point (0.88, 0.94) cur_Obj: 0.9922grad_1: 0.1250grad_2 : 0.0000step_size : 0.0000itCnt: 11 cur_point (0.94, 0.94) cur_Obj: 0.9961grad_1: 0.1250grad_2 : 0.0000step_size : 0.5000itCnt: 12 cur_point (0.94, 0.94) cur_Obj: 0.9961grad_1: 0.0000grad_2 : 0.1250step_size : 0.0000itCnt: 13 cur_point (0.94, 0.97) cur_Obj: 0.9980grad_1: 0.0000grad_2 : 0.1250step_size : 0.2500itCnt: 14 cur_point (0.94, 0.97) cur_Obj: 0.9980grad_1: 0.0625grad_2 : 0.0000step_size : 0.0000itCnt: 15 cur_point (0.97, 0.97) cur_Obj: 0.9990grad_1: 0.0625grad_2 : 0.0000step_size : 0.5000itCnt: 16 cur_point (0.97, 0.97) cur_Obj: 0.9990grad_1: 0.0000grad_2 : 0.0625step_size : 0.0000itCnt: 17 cur_point (0.97, 0.98) cur_Obj: 0.9995grad_1: 0.0000grad_2 : 0.0625step_size : 0.2500itCnt: 18 cur_point (0.97, 0.98) cur_Obj: 0.9995grad_1: 0.0312grad_2 : 0.0000step_size : 0.0000itCnt: 19 cur_point (0.98, 0.98) cur_Obj: 0.9998grad_1: 0.0312grad_2 : 0.0000step_size : 0.5000itCnt: 20 cur_point (0.98, 0.98) cur_Obj: 0.9998grad_1: 0.0000grad_2 : 0.0312step_size : 0.0000itCnt: 21 cur_point (0.98, 0.99) cur_Obj: 0.9999grad_1: 0.0000grad_2 : 0.0312step_size : 0.2500itCnt: 22 cur_point (0.98, 0.99) cur_Obj: 0.9999grad_1: 0.0156grad_2 : 0.0000step_size : 0.0000itCnt: 23 cur_point (0.99, 0.99) cur_Obj: 0.9999grad_1: 0.0156grad_2 : 0.0000step_size : 0.5000itCnt: 24 cur_point (0.99, 0.99) cur_Obj: 0.9999grad_1: 0.0000grad_2 : 0.0156step_size : 0.0000itCnt: 25 cur_point (0.99, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0156step_size : 0.2500itCnt: 26 cur_point (0.99, 1.00) cur_Obj: 1.0000grad_1: 0.0078grad_2 : 0.0000step_size : 0.0000itCnt: 27 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0078grad_2 : 0.0000step_size : 0.5000itCnt: 28 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0078step_size : 0.0000itCnt: 29 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0078step_size : 0.2500itCnt: 30 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0039grad_2 : 0.0000step_size : 0.0000itCnt: 31 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0039grad_2 : 0.0000step_size : 0.5000itCnt: 32 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0039step_size : 0.0000itCnt: 33 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0039step_size : 0.2500itCnt: 34 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0020grad_2 : 0.0000step_size : 0.0000itCnt: 35 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0020grad_2 : 0.0000step_size : 0.5000itCnt: 36 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0020step_size : 0.0000itCnt: 37 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0020step_size : 0.2500itCnt: 38 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0010grad_2 : 0.0000step_size : 0.0000itCnt: 39 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0010grad_2 : 0.0000step_size : 0.5000itCnt: 40 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0010step_size : 0.0000itCnt: 41 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0010step_size : 0.2500itCnt: 42 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0005grad_2 : 0.0000step_size : 0.0000itCnt: 43 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0005grad_2 : 0.0000step_size : 0.5000itCnt: 44 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0005step_size : 0.0000itCnt: 45 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0005step_size : 0.2500itCnt: 46 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0002grad_2 : 0.0000step_size : 0.0000itCnt: 47 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0002grad_2 : 0.0000step_size : 0.5000itCnt: 48 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0002step_size : 0.0000itCnt: 49 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0002step_size : 0.2500itCnt: 50 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0001grad_2 : 0.0000step_size : 0.0000itCnt: 51 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0001grad_2 : 0.0000step_size : 0.5000itCnt: 52 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0001step_size : 0.0000itCnt: 53 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0000grad_2 : 0.0001step_size : 0.2500itCnt: 54 cur_point (1.00, 1.00) cur_Obj: 1.0000grad_1: 0.0001grad_2 : 0.0000step_size : 0.0000
这样就完成了。
当然了，在这个例子中，从第3步左右的迭代开始，后续的点就非常近了，因此，步长就需要动态的调整。具体文献之后补充。
作者：刘兴禄，清华大学，清华伯克利深圳学院 (博士在读)
邮箱：hsinglul@
