.[TOC].

本文中的课件来自清华大学深圳国际研究生院，物流与交通学部张灿荣教授《高级运筹学》课程。

在无约束非线性函数的最优化中，最速下降法(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问题)去更新当前位置。 就像上图一样，一步一步，最终走到最优解对应的点。

我们看下面的函数 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​)=​2x1​x2​+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之后，可视化非常不错，所见即所得。

这个是用来构造两个符号变量 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​)=​2x1​x2​+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(函数, 变量)

如下图

有了符号函数，我们怎么知道自变量 x 1 , x 2 x_1, x_2 x1​,x2​取具体值得时候，符号函数的取值呢？我们用函数函数.subs({变量1:变量1的取值, ....}).evalf()，具体代码为

如果说只有一个变量已知，那就是下面的情况

还是非常智能的。

为了寻找下降速度最快的方向，我们需要利用之前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，准备好了上述函数，我们就可以开心的把最速下降法写出来了。具体代码见接下来的部分。

运行结果如下

这样就完成了。

当然了，在这个例子中，从第3步左右的迭代开始，后续的点就非常近了，因此，步长就需要动态的调整。具体文献之后补充。

作者：刘兴禄，清华大学，清华伯克利深圳学院 (博士在读) 邮箱：[email protected]