机器学习的问题一般都可以归结为是优化问题，而优化问题中最重要的一部分就是凸优化问题。凸集保证了在算法运行过程中，计算的点不会跑到定义域外面去；而凸函数保证了局部最优解就是全局最优解
...

优化

一般优化问题

机器学习中的问题基本上都是优化问题。那么什么是优化问题呢：

• 构造一个合适的目标函数，使得这个目标函数取到极值时的解就是你要求的东西
• 找到一个能让这个目标函数取到极值的解的方法

即 机器学习 = 模型 + 优化，其中模型就是我们要求解的目标；优化就是能够求解这个目标的方法。

将上述的概念可以类比数据结构和算法的关系。我们知道 程序 = 数据结构 + 算法，数据结构是研究数据如何在计算机中组织和存储的；而算法是在这些数据结构之上的操作。有了这两方面的东西，才有了我们的程序，这与 机器学习 = 模型 + 优化的概念基本上是一致的。

任何一个优化问题，都可以写为：

其中​f_0(x)就是我们要求解的目标函数，​f_i(x) \le 0,g_j(x) = 0是目标函数​f_0(x)的约束条件，满足这些约束条件的点​x叫做可行解（Feasible Solution）。我们要做的就是在可行解集中找到一个解，使得目标函数取得最小值，这个解称为最优解。

上述的优化问题的写法是一般优化问题的标准形式，在这个标准形式中，没有做出任何假设，即：没有对这个目标函数做任何的假设，也没有假设目标函数所受到的约束条件中的函数是什么类型的函数。它们可以是凸函数也可以是非凸函数、可以是连续的函数也可以是离散的函数等等。

优化的分类

有了优化问题的标准形式之后，就需要判断优化目标——目标函数它属于什么类别。因为对于不同的类别有不同的处理方法。

在优化领域通常会将优化问题分为四个维度，不同维度的组合可以构成不同的优化问题，：

• 凸的和非凸的
• 光滑和非光滑
• 连续和离散
• 有约束条件和无约束条件

机器学习主要关注的是凸优化问题。因为凸优化问题有一个很好的性质，就是：局部最优解就是全局最优解；而对于非凸优化问题来说，局部最优解不一定就是全局最优解。所以对于非凸优化问题来说，我们追求的是找到更好的局部最优解（Better Local Optimal）

对于非凸优化问题来说，常常有以下三种解决方法：

• 如果非凸优化问题简单，可以硬解出来，如：Bruce Force
• 如果可以通过松弛 Relax等方法，将非凸优化问题转为凸优化问题，来求解这个凸优化问题。当把这个凸优化问题求解完毕之后，对求解出来的凸优化问题的解来做一些改进得到非凸优化问题的解。
• 通过常规的算法进行求解，但是求解出来的一定是一个局部最优解（Local Optimal）

优化问题的通用解决思路

1. 首先确定问题所涉及到的参数 Decision Variable
2. 确定目标并写出目标函数 Objective Function
3. 判断是否约束条件，如果有，将所有的约束条件写出来 Constraints
4. 判断优化问题所属的分类，一般判断其是否是凸优化问题 Convex
5. 使用或设计求解器 Solver

优化问题的学习重点（目标）

1. 识别凸函数。如何判断目标函数是凸函数还是非凸函数？
2. 设计模型为凸函数。当设计一个新的模型时，同样条件下更倾向于设计目标为凸函数。
3. 求解非凸函数。如果所设计的模型的目标为非凸函数，如何解决？
4. 问题的松弛化。如果所涉及的模型的目标为非凸函数，同时非常难解决（如NP-Hard），怎么办？

凸优化问题

假设给定的优化问题是如下的标准形式：

那么什么样的问题是凸优化问题呢？即：给定一个标准形式的优化问题，如何判断它属不属于凸优化问题呢？

要解决上述问题，就需要回归概念：需要关注目标函数的定义域和值域是什么样子的。

凸集

定义

定义：假设对于​\forall x, y \in C，并且对​\forall \alpha \in [0, 1]，均有​\alpha x +(1 - \alpha)y \in C，则集合​C是凸集。

上述定义描述的是什么意思呢？简单来说，就是集合​C中任意两点之间的直线段上的点都属于集合​C。怎么看出来的呢？利用控制变量法。当​x, y都给定了的时候，它们就是一个常量了，不会随着​\alpha的变化而变化了。所以​\alpha x + (1 - \alpha)y只有一个自变量​\alpha，令​z = \alpha x + (1 - \alpha)y，有：

根据上式，只有一个自变量，其表示的是一条直线；又因为自变量​\alpha是属于闭区间​[0, 1]的，当​\alpha = 0时，​z = y；当​\alpha = 1时，​z = x。所以上述式子表示的是在点​x, y之间的直线段上的所有点。而​\alpha x +(1 - \alpha)y, \alpha \in [0, 1]它构成了一个新的向量，这个向量还有一个名字，叫做凸组合。

凸集的定义保证了：在这个集合中的任意一个加权凸组合后的点仍然在这个集合内，这个性质保证了在计算过程中不会出可行域。

一个重要定理

两个凸集的交集还是凸集。

这个定理是一个重要的定理，在掌握了常用的凸集之后，在判断一个优化问题的可行域是否是凸集时就简化了。因为优化问题的可行域是满足各个约束条件的点的集合，它是一个交集。所以如果构成这个可行域的满足各个约束条件的点的集合它是一个凸集，那么这个可行域也一定是一个凸集。

常见的凸集

• 所有的​R^n
• 所有的正数集合​R_+^n
• 范数​||x|| \le 1
• 仿集：线性方程组的所有解​Ax = b
• 半空间

凸函数

定义

函数的定义域​domf为凸集，对于定义域中任意的两点​x, y，函数满足：​f(\theta x + (1-\theta)y) \le \theta f(x) + (1 - \theta)f(y), \forall\theta \in [0, 1]，则称该函数为凸函数。

上述定义描述的是什么呢？描述的是：过一个下凸函数上任意两点所作割线一定在这两点间的函数图象的上方，即：凸函数的割线总在函数曲线的上方。

具体来看上述不等式（这个不等式又叫做 琴生不等式），不等式两侧的​\theta是同一个值，也就是说对于给定的两点​x, y和给定的一个确定的​\theta值，其比较的是同一个位置上的割线上的函数值和下凸函数上的函数值的大小。随着​\theta不断改变，取遍​[0, 1]上的所有值，其也就把割线上的所有点和与之对应的下凸函数上的函数值都比较了一遍，根据几何性质可以得到上述结果，即：凸函数上任意两点所做的割线一定在这两点间的函数图像的上方。

从函数定义域和值域的角度上来看：给定的函数的定义域是凸集；函数的值域也是一个凸集。

凸函数的一个重要性质

若干个凸函数的非负加权后，得到的新的函数仍然是一个凸函数，即：若干个凸函数的非负加权和仍然是一个凸函数（权值是非负数，即要求权值要大于等于0）。

凸函数的判别方法

判断凸函数的一阶条件——充要条件

设​f: R^n \to R是可导的，则​f为凸函数，当且仅当​f(y) \ge f(x) + \nabla f(x)^T (y - x)对于​\forall x, y \in domf成立且​domf是凸集

上述一阶条件要验证：

1. 定义域​domf是凸集
2. 对于​\forall x, y \in domf，不等式​f(y) \ge f(x) + \nabla f(x)^T (y - x)成立

上述定理的证明可以使用泰勒公式来进行证明，上述公式描述的是：下凸函数在​x点的附近点y处的函数值不小于以​x点为切点的切线上的函数值。

一阶条件具有清晰的几何意义：凸函数永远位于其切线的上方。

判断凸函数的二阶条件

设​f: R^n \to R是二阶可导的，则​f为凸函数，当且仅当​\nabla^2f(x) \succeq 0对于​\forall x, y \in domf成立且​domf是凸集

上述二阶条件要验证：

1. 定义域​domf是凸集
2. 对于​\forall x, y \in domf，​\nabla^2f(x)是半正定的（Positive-semidefinit ，PSD）

对于二阶条件的证明可以使用带有拉格朗日余项的泰勒公式来进行证明。

补充知识点：半正定矩阵

半正定矩阵的定义

一个矩阵是半正定的定义是：对于任意的实非零向量​v，如果实对称矩阵​M满足​v^TMv \ge 0，则矩阵​M是半正定矩阵。

判断一个矩阵是否是半正定矩阵

判断一个矩阵是半正定矩阵可以通过定义去判断，也可以使用一些判定条件来进行判断：

1. 需要注意的是：对于半正定矩阵来说，顺序主子式非负并不能推出矩阵是半正定的，而应该将相应的条件改为所有的主子式非负（而不仅仅是顺序主子式非负）。
2. 如果一个矩阵的所有特征值均不小于0，则该矩阵是半正定矩阵

半正定矩阵的性质

1. 半正定矩阵的行列式是非负的；
2. 两个半正定矩阵的和是半正定的；
3. 非负实数与半正定矩阵的数乘矩阵是半正定的。