最优化理论的基本概念

一. 最优化理论的定义与分类

1. 一般形式

（1）公式定义：
$$minf(x),且有x\in X$$
其中，对于上式中的字母，含义如下：

• f(x)：代价函数(目标函数)
• x：决策向量（单值或者是向量）
• X：约束集合，约束集合一定是从属于n维实数空间(Rⁿ)中的某个子空间

（2）简单分类：

当X是Rⁿ空间的真子集时，上文描述的问题就称为约束优化问题

形如下式中的问题就是约束优化问题
$$min(x^2)【s.t.x+1\le 0】$$

当X就是Rⁿ空间时，上文描述的问题称为无约束优化问题

形如下式中的问题就是无约束优化问题
$$min(x^2)【x\in R】$$

（3）说明
虽然在定义中，问题被统一定义成最小化的求解形式；其实最小化和最大化之间是可以相互转化的。
Maximize f(x) ↔ Minimize -f(x)

【例】根据给出的实际题目，写出其相应的最优化形式

2. 线性规划问题

前面我们只是根据有没有约束条件，对优化问题进行有约束/无约束的简略分类；
在实际中，最优化问题还有别的分类依据，其中线性规划【Linear Programming】就是一种。

（1）定义

目标函数是线性的+约束条件也是线性的 → 最优化问题是线性规划问题

（2）一般形式
$$Minimizef(x)\equiv c^T\cdot x，且有x\in X$$

其中对于定义中的相关参数，作出以下规定：

• 约束集合X = {x∈Rⁿ，Ax = b，x≥0}

其中Ax = b，表示该线性约束是等式约束；也可以约束为Ax≤b的形式

• 因为是线性的表述，上式中的符号统统采用向量和矩阵的形式：c∈Rⁿ，b∈R^m，A∈R^mxn

（3）NLP(NonLinear Programming)
当目标函数是非线性的，或者限制条件是非线性的时候该最优化问题就属于非线性规划问题。

我们这门课大部分讨论的都还是非线性规划的问题，因为现实生活中的条件复杂，很难满足线性性。

3. 其他类型的优化问题

（1）整数规划(Interger Programming)

也称离散优化(Discrete Optimization)，要求问题定义与求解中的所有决策变量或向量都是离散的整数类型。

（2）混合整数规划(Mixed Integer Programming)

决策变量有些是整型，有些是连续型的。

（3）动态规划/最优控制(Dynamic Optimization)

需要考虑系统的动态性，往往会考虑时间的影响。

（4）随机优化(Stochastic Optimization)

需要考虑问题中的不确定性因素，比如涉及到的部分变量是随机变量，而非确定性的。
e.g. 前台接待系统中某一时段的客流量就是随机、不确定的。

（5）多目标最优化(Multi-Objective Optimization)

在进行优化时，有多个目标函数需要同时达到最优。
e.g. 比如建造房子的时候，需要同时考虑“工期短”、“质量优”、“成本低”等目标。

对于多目标优化问题，往往是不能拆解成若干个单独的最优化问题来求解的；因为各个目标之间也存在着制约、矛盾的关系。

（6）博弈论(Game Theory)

往往有多方决策者参与，且信息分布是不对称的(你不知道别人在想什么)，也就是说你只能拿到局部信息。

二. 最优化的基础概念

1. 凸集

根据凸集的数学定义，其实质含义为——
如果一个空间集合为凸集，那么这个集合中的任意两点的连线，也应该在这个空间集合的内部。

凸集举例：
X = {x| ||x||₂≤5，且x∈R²}，表示二维平面上一个以原点为圆心，半径为5的圆面。

非凸集举例：
Y = {y| 2≤||y||₂≤6，y∈R²}，表示二维平面上一个以原点为圆心，内径和外径分别为2和6的圆环。

其中，||·||₂该符号表示向量的2范数。

2. 超平面

超平面是满足下面约束条件的一个点集
X = { x ∣ c T ⋅ x = z } X = \{x|c^T·x = z\} X={x∣cT⋅x=z}
其中c和z均为向量，且c≠0，z是一个常向量。

二维超平面举例：
x∈R²，点集满足[1,1]·[x₁,x₂]^T = 2，该集合对应的超平面就是二维空间中的一条直线x₁+x₂ = 2。

三维超平面举例：
x∈R³，点集满足[1,2,3]·[x₁,x₂,x₃]^T = 2，该集合对应的超平面就是三维空间中的一个平面x₁+2x₂+3x₃ = 2。

如果定义出了一个超平面，那么超平面就会将其所在空间划分成两个部分，其中一部分是{x|c^T·x ≤z}；另外一部分就是{x|c^T·x >z}。

3. 凸集某一边界点的支撑超平面

给定一个凸集X，且取该集合中的一个边界点w，若称一个超平面c^Tx = z是该边界点w的支撑超平面，则需要满足：

• c^Tw = z（该超平面是经过该边界点的）
• c^Tx≥z（或者是c^Tx≤z） 对于所有的x∈Z（该凸集内的所有点都分布在该支撑超平面的同一侧）
  

4. 凸函数(与凹函数)

“定义在凸集上，且任意两个自变量的线性组合的函数值不大于该两个自变量函数值的线性组合”，这样的函数就称为凸函数。

（1）定义
（2）凸/凹/非凸非凹/又凸又凹函数

【微积分中的知识回顾】

为了后续的理解与计算，现将“微分”、“方向导数”的概念进行回顾。

5. 可微凸函数的凸性三定理

在定义凸函数的时候我们并不限制函数f(x)一定是可导的，但是这里我们只对于可导的函数进行性质讨论。

（1）定理一

如果f(x)是定义在凸集X上的一个可微函数，则f(x)是凸函数的充要条件是
f(x₂)-f(x₁)≥▽f(x₁)^T·(x₂-x₁)

（2）定理二

如果f(x)是定义在凸的开集X上的一个二阶可微的函数，则f(x)是凸函数的充要条件为
f(x)对应的Hessian矩阵H(x)，对于任意一个x都是半正定的。

【背景知识补充】

• 开集：对于集合中的任意一点，都能找到该点的一个邻域，且该邻域一定在集合内部。
  可以近似地认为所谓开集就是“没有边界的集合”,e.g. {x|满足||x||₂＜5}就是开集，如果“<”改成“≤”，则不再是开集。
  
• 半正定矩阵：如果一个矩阵是对称阵，且对于任意一个非零的向量x，都有x^TAx≥0，就称矩阵A是半正定矩阵。
  p.s. 在矩阵论系列博文中《【矩阵论】Hermite二次型(2)》中也对矩阵的正定性定义及定理进行了探讨。

【证明】

梳理了以上证明过程，即可明白，定理2是基于定理1的。

（3）定理三

如果f(x)是定义在一个凸的开集X上的二阶可微的函数，那么f(x)是集合X上的严格凸函数，这一结论的充分非必要条件是对应的Hessian矩阵H(x)对于每一个x∈X都是正定的。

因为根据定理三我们已经知道，由“凸的开集上的二阶可微函数是凸函数”，只能推出H(x)是半正定的，而非正定的。

但是如果H(x)是正定的，则能够推出f(x)一定是凸函数。

【例】考察给定函数的凸性

三. 最优化的条件

1. 局部(全局)最小值

• 局部极小点：在该点某一邻域内的任意点的函数值都不小于在该点处的函数值
• 全局极小点：在定义域内的任意点的函数值都不小于在该点处的函数值

【扫除一些思维定式】
①一个点既可能是极小点，也可能是极大点

②全局极值点也不一定唯一，比如sinx
③全局极值点和局部极值点也可能是同一的，比如sinx

2. 极值的求解

（1）现在可行的大部分理论和定理都可以帮助确定问题的局部极值
（2）凸函数的极值：
①如果目标函数是凸函数，那么找到的局部极小值同样也是全局最小值；

证明

②如果目标函数是严格凸函数，那么全局极小值是唯一的。

（3）目前会使用诸如“模拟退火”或者“遗传算法”等随机化算法来进行全局最优值的求解。

用“没有地图的蚂蚁找最高峰”这个问题来理解上述三种算法的思想：
【经典梯度下降法】：从当前的出发点在局部范围内搜索，那个方向可以去往最高的方向，就沿着该方向进行一小步的移动，然后重复上述过程。
p.s. 为了能够尽量找到全局的最优，可以选择多个起始点进行查找

【模拟退火】：一只喝醉的蚂蚁，会随机地向上或向下进行寻找；但是随着时间的增加，蚂蚁会越来越清醒，会更加可能往高处进行寻找，

【遗传算法】：利用一群蚂蚁，在不同的地方开始寻找，然后会定期地发大水，淹掉那些地势比较低的蚂蚁；而幸存下来的蚂蚁之间会进行信息交流(繁殖)，其后代会在相对更高的地势开始进行寻找。

3. 鞍点与极值判别定理

（1）鞍点的定义

（2）极值判别定理

【例】直接截图，画质不太好请见谅