最优化理论的基本概念

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

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）极值判别定理

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

 

 

1.首先点击‘插入’按钮，点击‘我的加载项’，点击 ‘管理加载项’，找到规划求解加载项，如下图。

接着点击 ‘转到’按钮，如下图

将对应的 规划求解加载项 点击对号。

2.点击‘数据’按钮，右上角有如下图

3.看例子：

 

#

农场占地75公顷，种植两种文化：谷物和水稻。

栽培总成本：每公顷粮食120美元，每公顷水稻210美元。

农场有15000美元

收获后的文化，有必要储存一段时间，最大容量的存储- 120000公斤。

每公顷可种植粮食3500公斤，水稻1000公斤

每公斤粮食的净收入-1.3美元，大米-2.0美元

找到75公顷利用最大净收入的最佳方案。

#

此处是典型的最优化问题：设种植x公顷粮食，y公顷大米。约束条件为以下三个不等式：

（1）x+y<=75

 (2) 120x+210y<=15000

 (3) 3500x+1000y<=120000

优化目标函数：max（1.3*3500x+2*1000y）

#

接下来利用excel解决这个最优化问题。

4.首先建立公式和自变量，粮食面积和大米面积为自变量。如下图：

总收入对应的空格里需要加入公式 =1.3*3500*B1+2*1000*B2  （提醒：excel中公式的输入以=开始）

花费金额对应的空格需要填入公式 =120*B1+210*B2 

储存对应的空格需要填入公式  =3500*B1+1000*B2

种植总面积对应的空格需要填入公式 =B1+B2

其中（B1和B2其实就是x和y所对应的位置）就是所谓的自变量。

接着点击 ‘数据’ 下面的规划求解。如下图

设置目标 为总收入所对应的空格（就是刚才输入的公式）

接着点击最大值或者最小值（根据你需要的情况点击即可），本例子中求最大收入，故点击最大。

可变单元格  点击自变量区域。

遵守约束：添加  出现下图

单元格引用 点击刚才的公式，约束填入值（例如花费金额就要填入15000）.依次类推，将全部约束条件添加完全。

然后求解即可。

 

转自：彬彬有礼的专栏

题目：最优化问题简介

        一年多学习以来，无论是前面学习压缩感知，还是这半年学习机器学习，一直离不开最优化，比如压缩感知的基追踪类重构算法，核心问题就是一个优化问题，而机器学习中的很多算法也需要最优化的知识，比如支持向量机算法。看来必须得把最优化的基本内容学习一下了，不求理解的有多么深，至少要知道怎么用。其实前面已经写过一篇与最优化相关的内容了，就是《压缩感知中的数学知识：凸优化》这篇。

        从本篇起，开始学习一些有关最优化的基础知识，重点是了解概念和如何应用。本篇是参考文献第1.1节的一个摘编或总结，主要是把一些概念集中起来，可以随时查阅。

1、一般形式

        最优化问题的数学模型的一般形式为（以下称为最优化数学模型）：

其中，和为连续函数，通常还要求连续可微。称为决策变量，为目标函数，为约束函数，为等式约束，为不等式约束，并记等式约束的指标集为，不等式约束的指标集为。和分别是英文单词minimize(极小化)和subject to(受约束)的缩写。

2、概念

        如果点 满足最优化数学模型中的所有约束条件就称为 可行点(Feasible Point) ，所有可行点的全体称为 可行域(Feasible Region) ，用 表示。在一个可行点 考虑不等式约束 ，如果有 ，就称不等式约束 在点 考虑不等式约束是 有效约束 或 起作用约束(active constraint) ，并称可行点 位于约束 的边界；如果有 ，就称不等式约束 在点 是 无效约束 或 不起作用约束(inactive constraint) ；对于一个可行点 ，如果没有一个不等式约束是有效的，就称 是可行域的 内点 ，不是内点的可行点就是可行域的 边界点 。显然在边界点至少有一个不等式约束是有效约束，当存在等式约束时，任何可行点都要满足等式约束，因此不可能是等式约束的内点。
        如果一个可行点 满足 ，则称为最优化问题的 全局最优解 （或总体最优解）；如果可行点 满足 ，则称为最优化问题的 严格全局最优解 （或严格总体最优解）；对于可行点 ，如果存在一个邻域 使得 成立，则称为最优化问题的 局部最优解 ，其中 是一个小的正数；对于可行点 ，如果存在一个邻域 使得 成立，则称为最优化问题的 严格局部最优解 。如下图所示，点 是严格全部极小解， 和 则是局部极小解，其中 是严格局部极小解，而 是非严格局部极小解。（注： 附近有一段线是水平的）

        一般常见的最优化方法只适用于确定最优化问题的局部最优解，有关确定全局最优解的最优化方法属于最优化问题的另一个领域——全局最优化。然而，如果最优化问题的目标函数是凸的，而可行域是凸集，则问题的任何最优解（不一定唯一）必是全局最优解，这样的最优化问题又称为凸规划。进一步，对于凸集上的严格凸函数的极小化问题，存在唯一的全局最优解。

3、分类

1）约束最优化问题

        只要在问题中存在任何约束条件，就称为约束最优化问题。

        只有等式约束时，称为等式约束最优化问题，数学模型为：

        只有不等式约束时，称为不等式约束最优化问题，数学模型为：

        既有等式约束，又有不等式约束，则称为混合约束优化问题（或一般约束优化问题）；

        把简单界约束优化问题称为盒式约束优化问题（或有界约束优化问题），数学模型为：

2）无约束最优化问题

        如果问题中无任何约束条件，则称为无约束最优化问题，数学模型为：

3）连续与离散最优化问题

        决策变量的取值是连续的，称为连续最优化问题；

        决策变量的取值是离散的，称为离散最优化问题，又称为组合最优化问题。如整数规划、资源配置、邮路问题、生产安排等问题都是离散最优化问题的典型例子，求解难度比连续最优化问题更大。

4）光滑与非光滑最优化问题

        如果最优化数学模型中的所有函数都连续可微，则称为光滑最优化问题；

        只要有一个函数非光滑，则相应的优化问题就是非光滑最优化问题。

5）线性规划问题

        对于连续光滑最优化问题，如果最优化数学模型中的所有函数都是决策变量的线性函数，则称为 线性规划问题 。线性规划问题的一般形式为：

其中。矩阵向量形式为

其中，

，

6）二次规划问题

        对于连续光滑最优化问题，如果最优化数学模型中的目标函数是决策变量的二次函数，而所有约束都是决策变量的线性函数，则称为二次规划问题。二次规划问题的一般形式为：

其中，为纯量，为阶对称矩阵。如果为半正定矩阵，则称此规划为凸二次规划，否则为非凸规划。对于非凸规划，由于存在比较多的驻点，求解比较困难。

7）非线性最优化问题

        只要最优化数学模型中的函数有一个关于决策变量是非线性的，则称为非线性最优化问题。

        非线性最优化问题是最一般的最优化问题，而线性规划和二次规划问题却是相当重要的特殊的最优化问题，因为在实际中形成的许多最优化问题都是线性规划问题或二次规划问题，而且在用迭代法求非线性最优化问题的最优解时我们常常用线性规划或二次规划来局部近似原非线性最优化问题，并通过求所得近似问题的最优解来对已有最优解的估计进行改进。