【最优化(一)】最优化问题概述和分类

行业资讯

首页 > 新宝GG动态 > 行业资讯

公司动态行业资讯

【最优化(一)】最优化问题概述和分类

国内工科系很多都会开设一门名为最优化的课程，当然这门课程的名称也不一定就是最优化，也可能起名为优化理论，优化方法，数学优化方法，决策方法之类的名称，但内容上基本大同小异都是以连续优化问题为主要内容。

目前来说最优化的课程存在的问题有：

过于侧重手动计算：计算机普及的时代我们课程的主要内容不应该放在考察计算上。首先实际工程中都是用计算机编程运算，几乎没有手动计算，其次大量的手动计算也使得学生的精力被牵扯在细枝末节上而忽视了优化领域中最珍贵的一些思想性的东西，最后大量的手动计算还在一定程度上折磨学生的兴趣，让本就枯燥的课程进一步雪上加霜。
忽视几何观点：这一点其实在数学类的课程上也是非常明显的，大量的教材都是一上来给出一堆定义，然后就自顾自的开始各种理论推导和计算过程，却很少谈到为什么这样定义的动机。究其原因就是缺乏几何观点的解释，所以只能诉诸于从公式到公式的强行推导。这就导致学生的将理科的学习文科化，即依靠强行记忆来学习而不是理解内在逻辑关系。

针对以上的问题，本笔记的特点是

侧重计算机编程实现：在笔记中配套一些代码供大家学习参考。
用manimce制作一些动画来给出几何直观解释：manimce 是一个数学公式可视化的引擎，可以实现对很多数学公式的可视化。

最优化问题一般由三个要素构成：

决策变量： $x=\\left( x_1,x_2,...,x_n \\right) ^T\\in R^n$ ，表示我们在最优化问题中要求解的变量。
目标函数： $f:R^n\\rightarrow R$ ，表示我们需要最大化或者最小化的表达式
约束条件： $c_i:R^n\\rightarrow R$ ，表示我们需要满足的等式条件或者不等式条件。

将上述三个要素写在一起构成最优化问题的一般形式为：

$\緻set{x}{\\min\ ext{ }}f\\left( x \\right) \\quad (1.1) \\\\$ $\ ext{s.t. }c_i\\left( x \\right) \\le 0,\\ i=1,..,m \\quad (1.2) \\\\$ $c_i\\left( x \\right)=0,\\ i=m+1,..,m+l \\quad (1.3) \\\\$

$\ ext{s.t.}$ 是 "subject to" 的缩写，表示约束条件的意思。目标函数 (1.1) 表示极小化函数 $f(x)$ ，约束条件 (1.2) 表示不等式约束，约束条件 (1.3) 表示等式约束。

事实上等式约束可以被两个不等式约束等价替换，如下所示：

$c_i\\left( x \\right)=0\\ \\leftrightarrow c_i\\left( x \\right) \\le 0\\ \ ext{and}-c_i\\left( x \\right) \\le 0 \\\\$

我们在后边的讨论中为了方便不会特殊的强调等式约束，由此可知：

$\緻set{x}{\\min\ ext{ }}f\\left( x \\right) \\quad (1.4) \\\\$ $\ ext{s.t. }c_i\\left( x \\right) \\le 0,\\ i=1,..,m \\quad (1.5) \\\\$

$X$ 是可行域集合。可行域集合中的元素被称为可行解。

$X=\\left\\{ x\\in R^n|\\ c_i\\left( x \\right) \\le 0,i=1,..,m \\right\\}\\quad (1.6) \\\\$

例如我们可以考虑如下的优化问题：

$\緻set{x\\in R}{\\min\ ext{ }}\\frac{1}{2}\\left( x-1 \\right) ^2+1 \\\\$

我们可以画出该函数的图像为：

https://www.zhihu.com/video/1524807106738085888

通过上面一个目标函数为二次函数的优化问题，我们可以初步对优化问题产生一个感受，但是干巴巴的数学式子可能并不能让大家体会到优化问题有什么实际应用。接下来我们采用一个生活中的例子来说明，最优化问题的一个应用实例。

我们考虑一个相亲男女嘉宾匹配的问题，如下图所示：

上图代表着一个相亲的匹配方案。我们尝试用优化问题来解决上述的相亲问题。

定义如下决策变量：

$x_{ij}=\\left\\{ \\begin{array}{l}1,\\ \ ext{男性}i\ ext{和女性}j\ ext{匹配}\\\\ 0,\\ \ ext{男性}i\ ext{和女性}j\ ext{不匹配}\\\\ \\end{array}\\right. \\\\$

假设 $N$ 位男性和 $N$ 位女性来相亲

$\\begin{aligned}& \\max \\sum_{i=1}^N{\\sum_{j=1}^N{c_{ij}x_{ij}}}\\;\\;\\;\\;\\;\\;\\;\\;(1.7)\\\\ s.t.\\ &\\sum_{i=1}^N{x_{ij}}=1,\\ \\forall j=1,2,...,N \\;\\;\\;\\;(1.8)\\\\ &\\sum_{j=1}^N{x_{ij}}=1,\\ \\forall i=1,2,...,N \\;\\;\\;\\;(1.9)\\\\ \\end{aligned}\\\\$

约束 (1.8) 表示一个男生匹配一个女生，约束 (1.9) 表示一个女生匹配一个男生。 $c_{ij}$ 表示男性 $i$ 和女性 $j$ 的匹配度， $c_{ij}$ 越大表示男女生越合适，反之越小的话表示男女生越不合适。目标函数 (1.7) 表示让总的匹配度最大。

从以上例子中就可以感受到优化问题在我们的日常生活有着非常大的应用前景，类似像美团骑手派单（通过决定哪个订单由哪个外卖员配送使得总的配送时间最小），快递员送货路径规划（通过决定快递员先送哪个货使得总的经过的路径最短）等场景本质上都是一个优化问题。

为了方便对最优化问题进行研究，我们需要对最优化问题进行一个分类，不同类别的最优化问题根据其特性有针对性的设计其算法。

无约束的例子：

$\緻set{x\\in R}{\\min\ ext{}}\\frac{1}{2}\\left( x-1 \\right) ^2 +1 \\\\$

如下图所示：

https://www.zhihu.com/video/1524807224484028416

这个例子在前面我们已经展示过了，就不再赘述了，主要对比一下无约束和下面有约束例子的区别。

有约束的例子：

$\緻set{x\\in R}{\\min\ ext{}}\\frac{1}{2}\\left( x-1 \\right) ^2+1 \\\\$ $\ ext{s.t. }x \\ge 2 \\\\$

如下图所示：

https://www.zhihu.com/video/1524807264740925440

由于添加了一条约束 $x\\ge2$ ，导致最优解从 $x=1$ 变为 $x=2$

连续的例子：

$\緻set{x\\in R}{\\min\ ext{}}\\left( x-1.4\\right) ^2+1 \\\\$

离散的例子：

$\緻set{x\\in Z}{\\min\ ext{ }}\\left( x-1.4\\right) ^2+1 \\\\$

如下图所示：

https://www.zhihu.com/video/1524807320357429248

从上图中可以很容易看到可行解由于多了整数（离散）的要求，就会让最优解发生变化。

在前面我们举例的优化问题中均未含有随机变量，所以前面的优化问题实际上都是确定性的优化问题。随机优化是指目标函数或者约束函数中涉及随机变量而带有不确定性的问题。

在实际问题中，我们往往只能知道一些参数的估计值。常见的一些例子例如：机器发生故障的可能性就是一个随机变量，外卖骑手配送订单所花费的时间也是一个随机变量。

线性规划是指目标函数和约束函数都是线性的优化问题。也就是说在优化问题(1.4-1.5)中 $f(x)$ 和 $c_i(x)$ 都必须是线性函数，线性规划的一般形式可以表达为如下形式：

$\\begin{aligned}& \緻set{x\\in R^n}{\\min}\\; c^Tx\\\\ s.t.\\ & a_{i}^{T}x \\le b_i,\\ \\forall i=1,...,m\\\\ \\end{aligned}\\\\$

目前来说线性规划可以比较容易的可以被求解的。其主要的求解方法分别为单纯形法和内点法。具体关于线性规划的内容，我们之前已经有了详细的笔记进行介绍，想系统性了解线性规划的同学可以参考我的笔记：

凸优化是指目标函数和约束函数都是凸函数的极小化问题。也就是说在优化问题(1.4-1.5)中 $f(x)$ 和 $c_i(x)$ 都必须是凸函数。需要注意的是为了方便起见我们针对的都是优化问题(1.4-1.5)来谈的。

如果其中有一个或者两者都不是凸的，那么相应的最小化问题是非凸优化问题．因为凸优化问题的任何局部最优解都是全局最优解，其相应的算法设计以及理论分析相对非凸优化问题简单很多．

在求解最优化问题之前，我们先介绍最优化(求极小值)问题的最优解的定义。

定义 3.1：对于可行点 $\\hat{x}$ ，定义如下概念：

如果 $f(\\hat{x}) \\le f(x), \\forall x\\in X$ ，那么称 $\\hat{x}$ 为优化问题(1.4-1.5)的全局最优解或者极小值。
如果存在 $\\hat{x}$ 的一个 $\\epsilon$ 领域 $N_e(x)$ 使得 $f(\\hat{x}) \\le f(x), \\forall x\\in N_e(x)$ ，那么称 $\\hat{x}$ 为优化问题(1.4-1.5)的局部最优解。
进一步地，如果有 $f(\\hat{x}) < f(x), \\forall x\\in N_e(x)$ ，那么称 $\\hat{x}$ 为优化问题(1.4-1.5)的严格局部最优解。

https://www.zhihu.com/video/1524807543024574465

从上图中可以很直观的观察到全局最优解，局部最优解和严格局部最优解三个概念。

定义 4.1(范数)：一个向量空间 $R^n$ 到实数域 $R$ 的非负函数 $$ 为范数，如果它满足：

正定性：对于所有的 $v \\in R^n$ ，有 $\\lVert v \\rVert \\ge 0$ ，且 $\\lVert v \\rVert=0$ 当且仅当 $v=0$ ；
齐次性：对于所有的 $v \\in R^n$ 和 $\\alpha\\in R$ ，有 $\\lVert \\alpha v \\rVert=|\\alpha| \\lVert v \\rVert$ ；
三角不等式：对于所有的 $v,w \\in R^n$ ，有 $\\lVert v+w \\rVert \\le \\lVert v \\rVert +\\lVert w \\rVert$