课程主要内容2在线视频

第二个

就进入到优化方法的简述

这里面我们看一看

在咱们课程里所学的

运筹学问题

实际是一个什么样的问题

拿一个例子来看

包括它一些特性是什么样子的

我们举一个比较简单的例子

这个例子

它的决策变量

我们后面会在

具体的线性规划里面会把

每一个概念的定义

非常明晰地给大家

我们这里提出这个概念

是求一个目标函数

只有一个决策变量

这个一维的问题

它可以在图形表示上比较清晰一点

这里的 x 是它的决策变量

问题整个的取值空间

是在 a 和 b 之间

那么

对于这个一般性的函数

我们用 f(x) 来表示

它具体的形状

变化的可能就比较多了

我们也不知道是什么样子

这里就是示意图

给大家画了这么一个

对应的样子

但实际来做这个优化问题的时候

是不可能看到

这个函数的整体面貌的

要是能看到的话

就不用去做这个优化问题了

假设是求这个问题的一个最大值

那么从这个图形上的话

大家事实上是可以看到的

也是很容易就可以知道

这个问题的最大值

实际上是在

对应的这个b点上取到的

一个最大值

但是

我们在解决这个问题的时候

刚才也说到了是不可能

开始的时候让

整个函数的所有形态展现在我面前

让我们在这里选出最大值

我们当然不可能去遍历所有的点

然后通过比大小的方式来取最大值

大家知道因为 x 是连续的

它在整个在数轴 [a,b] 之间是连续的

整个取值是有无穷多的

而且是不可列的

所以这也是不可能的事情

那么对这样的问题我们怎么解决呢

我们解决这个问题的思路就是

当然

有的同学可能这个时候也会

产生自己的想法

我学过高等数学

包括数学分析里面提到过的

可以求导数

导数等于 0 的地方

这个也是在实际应用中是不可实现的

因为求完导数之后

对于复杂的问题

需要求非线性方程组的解

这个求解的困难度

比这个优化问题可能也不简单

所以真正求解这个问题的一些办法

是怎么做呢

我们的办法是这样的

实际上就是我们看啊这里面

当然刚才提到了 c 和 d 都是

导数等于 0 的点

你是不太期望说把它找到的

那么我们解决办法是这样

我们在任意一点出发

比如说我们选定任意一点 x1

这个点就是咱们如图所示

选到了这个点

在 [c,d] 这个区间内的这么一个点

那么有这个点 x1 之后

现在我们要朝着能够改进

目标函数的方向进行搜索

什么叫改进目标函数的方向

就是 对这个问题来说

我们求的是目标函数的最大值

有点像爬山

那显而易见

大家都有爬山的经验

我们肯定要

往更高的地方爬

所以 在这个这个问题里面显而易见

在 x1 点出发的时候

沿着 x1 减小的方向

在这个里面发现另外一个点

x1-Δ 这么一个点

往这个方向去走的时候

这目标函数值肯定会越来越大

那么对于更一般的情况

你可能是可以通过求导数

可以把这个

使目标函数值改进的方向

可以求出来

即使说这个导数很难求

这个我们也可以

考虑用试探的办法

还是可以找到局部的

可以改进的方向的

然后

我们就走到一个新的点

在这个图里面就是 x1-Δ 这个点

那么走到这个点之后呢

我们还当然还有一些判断的准则

可以考虑说它在邻域里面

在附近里面找一找

是不是还有比这个点更小更好的点

如果有更好还可进一步走

那么实际上大家可以看到

这种方式

在这里我写了个公式

就是 x_k+1=x_k+λ_k*D_k

那么这个公式

是贯穿咱们课程始终的

解决优化问题的一个基本思路

那么这个我后面会讲

这是一个迭代的思路去解决问题

那么每一步都是从一个点出发

然后

找到一个搜索方向

再后 会沿着这个方向走到一定的步长

从而得到一个新的点

从这个新的点

我们再进一步再去找方向再去走

直到不能改进为止

这个应该跟我们

生活中

实际的很多例子是一样的

就是阶段性目标

那么我们在考大学之前

我们都瞄准了考清华

考上之后

进入到清华校门之后

我们再考虑下一步的努力的方向是什么

进一步去走

这个是很朴素的一个解决问题的思路

那么直到不能改进为止

我们就结束

但是

对这个问题的话可能会遇到点小麻烦

我们从这个图里就可以看到

如果是这么走的话

从 x1 点出发

最终这个按照这个方法结束之后

我们这个问题一定会停留到这个

c 点所对应的目标函数值

那么实际上

这个目标函数值

它只是在局域之内是

对应的一个最大值

它并不是这个真正的这个问题本身的

全局的最大值

因为这个问题的最大值

刚才我们说过了

是在最优点 b点所对应的目标函数

所以对应的问题是什么呢

这种方法是肯定能够

收敛到一个局部最优解

但是

是不能保证这个全局最优的

这个是这种方法

所遇到的最主要的一个问题

就是说

这种 找方向 沿着方向进行

搜索的 这种确定性的方法

什么叫确定性

我们每次的方向的选择都是

沿着能改进目标函数值的方向

进行搜索的

那么这个问题

显然有解决问题的方法了

但是

我们也看到

这个也会给解决的问题

这个带来的一些新问题

那么怎么来克服这个问题呢

沿着这个确定性的方向进行搜索

只能收敛到局部最优解

不能保证全局最优

怎么来解决这个问题

要解决它的话

需要走出局部最优解

当然有同学可能想到

我不选择这个点

选择别的点行不行

但是你不管怎么选

对一个完全未知的这么一个

非线性函数来说

或者一般性的函数

你总是不知道

如果停到的这个

按照确定性搜索的这个方向

停到这个点是不是就一定是

这个问题的全局最优解

所以这个问题

换点也不是一个好办法

能确保能走出局部最优解的

唯一的一个途径呢是什么呢

就是在搜索的过程中

允许前进到

目标函数值变得更差的点

也就说刚才咱们说的这个

对应的搜索方向

不能始终沿着

改变目标函数值

去让它变得更优的方向走

比如说这个问题来说

如果我允许

x 从往对应 x 值增加的方向走的话

也就向 d 点靠近的时候

那么显而易见 这个方向里对应

这个目标函数值是在减小的

它并不是改进目标函数值的

但是大家可以看到

一旦通过了 d 点我就有可能

在这个原来确定的规则下

它就会收敛到 b 点去

那么这里面的才有可能找到全局最优解

但是讲解过程中

大家也会意识到一个问题

这个问题是什么呢

也就说看着是好

但是

怎么保证这个算法能收敛啊

什么叫算法收敛

也就说最后我能不能停到一个点

就像这里面

我一会儿又可以往

目标函数值增加的方向走

我又可以往目标函数值减小的方向走

那我到底怎么做呀

开玩笑的话就是

人家给你指点方向的时候说

一件事情怎么做

这么做也行

那么做也行

这就跟没有指点一样了

所以

这里面就存在了

这个算法到底是怎么收敛的问题

也就是说

像这个我们只给了一个

允许目标函数值往变差走

没有任何意义

因为它不能保证

具体的算法收敛

怎么解决这个算法收敛性呢

一个具体的办法就是

为了使得这个算法收敛

我们只能来引入不确定性

什么叫引入不确定性

也就说我是允许

往目标函数实变差的方向走

但是呢

要把这个

向变差方向

移动的概率

和我对应的目标函数值

具体的改善

它们两个之间能建立起关系

也就像刚才的问题

因为我们求的是

目标函数的最大值

所以 我们使得这个移动的概率

尽可能地和这个目标函数值正相关

那我们就可以得到这个

按图中这个例子

也就是我们以这种概率

去改变的时候

是可以保证咱们这个问题里面

它是这个引入了这个不确定性

这个引入不确定性的好处在哪呢

按照这个方式引入的话

那么它不能保证

每次的时候都能收敛到这个 c 点

也不能保证说每次都收敛到 b 点

这个 c 点和 b 点

在这个问题里面

大家可以知道

一个代表了局部最优解

一个代表了全局最优

也不能保证说

你做的结果和我做的结果都是一样的

但是呢在概率层面上

就跟我们掷骰子一样

我们不能说

某次我掷的就一定是一点

一个就一定掷的是个五点

或者跟扔硬币一样

但是从这个整体概率上来说

它一定会那个收敛到一个

最后的稳定的状态

那这个也是一样

从概率上是可以保证

这种方法

只要以这个规则去做的时候

是可以收敛到最后的

全局最优解 b 点的

所以呢

引入这个不确定性之后

产生的算法

它的结果是不确定的一个算法

就是我们说具有随机性的算法

但是 能保证在概率上面

它具有收敛性

所以

在前面的例子里

我们就介绍了这个

优化方法的一个最基本的一个类型

那么 可以看到

它带来了

确定性的搜索与

不确定的搜索两种类型

那么简而言之

前者确定性搜索

我们再回顾一下

就是对一个问题来说

从一个点出发

然后按着迭代的思路

这个从这个点

选择一个使目标函数值

可以进一步优化的方向

然后

按这个方向 走一定步长之后

然后我们得到一个新的点

沿着新的点

我再去选方向

再去往前走啊

这叫确定性搜索

每一步的对应的

优化的方向的都是

使得目标函数值进行改善的方向

这是确定性的

那么后者

就是我们可以引入这个不确定性

引入随机性

不确定性的搜索方法

那么就变成这个另外的一种类型

前者是我们刚才说过了

这是我们课程介绍的主要内容

这后者就包括各种各样

包括模拟退火

遗传算法

免疫算法

蚂蚁算法

等等

这个就是这个不一一列举了

这个统一称为智能算法

还有蜂群算法

各种各样的

你可以看到各种各样的名字

但是不管它是怎么去做

包括像这个禁忌搜索

也是搜索方向

到了一定的时候

我们就可以把这个方向禁用掉

再也不去选择

这样的方向

这个类型从本质来说

都是在这个确定型搜索里面引入了

一定的随机性和不确定性之后来做的

只不过你是怎么设计这个

像刚才说这个概率

往这个更差的概率

要和这个函数值之间的关系

使这个算法变得更加的有效一点

所以

这个就是我们

关注的一些方法

那么我们课程主要的

就是基于确定性搜索的

优化方法

这是我们课程主要讨论内容

另外

还是要特别地叮嘱一下

就是那咱们课程的内容

相对来说的话还是比较严谨和保守的

为什么这么说呢

就是我们可以看出

实际上运筹学

是在解决怎么样去优化系统效率

所以它本质来说是一个

解决最优化的问题

但是

谈到“优化”二字

在咱们运筹学课程里面

给大家介绍的还是非常严谨

和非常“狭窄”

这个“狭窄”打引号

一个部分

我个人的一个感受是

所有的科学

它一定是很严谨和很保守的

你不能上就说

我这个东西放之四海皆准

什么都能解决

不是这个样子的

我们所介绍内容里面是

它解决问题的方面是很受限的

后面会看到很严格的一类问题

那么我们在日常生活中看到其他的很多

比如说

大家经常谈到的一些优化的问题

跟我们这个后面讲的还是有一些区别的

它的范围可能更广一点

我们包括说

把这个稍微改善一点啊

这个甚至说有一些

都不是通过咱们

讲过的用数学工具

数学模型的进行精确的

去进行分析和刻画的

那它也就叫优化

但是我们这个方法相对是

比较严谨的那个部分