优化 | 最优化问题概述

1 最优化问题概述

1.1 最优化问题的数学表达形式

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

1. 决策变量：，表示我们在最优化问题中要求解的变量。
2. 目标函数：，表示我们需要最大化或者最小化的表达式
3. 约束条件： ，表示我们需要满足的等式条件或者不等式条件。

所以说只要把优化问题的三要素都描述出来，那么该优化问题就已经被精确的表述了出来。接下来我们将上述三个要素写在一起构成最优化问题的一般形式为：

是 "subject to" 的缩写，表示约束条件的意思。目标函数 (1.1) 表示极小化函数 ，约束条件 (1.2) 表示不等式约束， 约束条件 (1.3) 表示等式约束。

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

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

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

1.2 从一个直观的例子看最优化问题

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

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

1.3 最优化问题的一些应用实例

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

我们考虑一个相亲男女嘉宾匹配的问题，如下图所示：上图代表着一个相亲的匹配方案。我们尝试用优化问题来解决上述的相亲问题。

定义如下决策变量：

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

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

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

2 最优化问题的分类

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

2.1 有约束 vs 无约束

无约束的例子：

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

有约束的例子：

由于添加了一条约束 ，导致最优解从 变为

2.2 连续优化 vs 离散优化

连续的例子：

离散的例子：

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

2.3 随机性优化 vs 确定性优化

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

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

2.4 线性规划 vs 非线性规划

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

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

2.5 凸优化 vs 非凸优化

凸优化是指目标函数和约束函数都是凸函数的优化问题。也就是说在优化问题(1.4-1.5)中 和 都必须是凸函数。

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

3 全局最优和局部最优

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

定义 3.1：对于可行点 ， 定义如下概念：

1. 如果 ，那么称 为优化问题(1.4-1.5)的全局最优解或者极小值。
2. 如果存在 的一个 领域 使得 ，那么称 为优化问题(1.4-1.5)的局部最优解。
3. 进一步地， 如果有 ，那么称 为优化问题(1.4-1.5)的严格局部最优解。
   
   

   

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

参考文献：

[1] Wright S, Nocedal J. Numerical optimization[J]. Springer Science, 1999, 35(67-68): 7.

[2] 刘浩洋、户将、李勇锋、文再文，最优化：建模、算法与理论[M]. 高等教育出版社, 2021.