在机器学习中，很多情况下我们想要优化一个函数。举个例子：给定一个函数 f：Rn − >R ，我们要找到一个 x∈Rn 使得 f(x) 取得最大值/最小值。
通常来说，找到一个全局最优解是困难的。但是，对于凸优化问题，局部最优解便是全局最优解。
凸集
在进行凸优化之前，首先我们要知道什么是凸集。
定义：如果集合C是一个凸集，那么对于 ∀x , y ∈ C，θ ∈ R( θ ≤ θ ≤ 1) ，总有
θx + ( 1 − θ )y ∈ C
几何含义：如果我们对于C中任意两个元素进行连接形成一条直线，那么直线上的任意一个点都在C中，我们称之为凸集。
例如上图，左侧是凸集，右侧是非凸集。
凸函数
定义：对于一个函数 f : Rn − > R ，它的定义域是一个凸集 D(f)，且对于 ∀x , y ∈ D(f)，0≤θ≤1， 有
f ( θx + (1− θ ) y) ≤ θf(x) + ( 1− θ )f(y)
几何含义：我们在凸函数的图上任取两个点连成一条直线，在这条直线的范围内，凹函数图上的值小于这个直线上的值。
注意：同济高等数学上凸函数，凹函数的定义和国外凹凸函数的定义是相反的。
凸函数的一阶充要条件：
f(y) ≥ f( x ) + ∇xf( x )T( y − x )
其中要求 f 可微
凸函数的二阶充要条件：
其中要求 f 的二阶可微。
凸优化问题
我们已经知道啦什么是凸函数、凸集，现在可以考虑凸优化问题。
通常一个凸优化问题的形式是：
st 为 subject_to 缩写。其中f是一个凸函数，C 是一个凸集，x 是需要优化的变量。然而，上面的式子表达不够清楚，我们通常写成下面的：
其中 f 是一个凸函数，gi 是凸函数，hi 是仿射函数，x 是需要优化的变量。
对于凸优化问题来说，局部最优解就是全局最优解。
常见的凸优化问题
1. 线性规划（Linear Programming）
如果目标函数ff和约束gg都是仿射函数，那这种凸优化问题被称为线性规划问题。
其中 x ∈ Rn 是需要优化的变量，
2. 二次规划（QP）
如果目标函数f是凸二次函数，约束g是不等式的形式，那么这种凸优化问题被称为二次规划问题。
其中 x ∈ Rn 是需要优化的变量，
3. 二次约束的二次规划（QCQP）
如果目标函数 f 和 g 都是凸二次函数，那么这种凸优化问题被称为二次约束的二次规划问题。
其中 x ∈ Rn 是需要优化的变量，
参考资料
http://www.cnblogs.com/fuleying/p/4481334.html
http://cs229.stanford.edu/section/cs229-cvxopt.pdf
来源：CSDN，作者：四月晴
原文：https://blog.csdn.net/siyue0211/article/details/80592788
版权声明：本文为博主原创文章，转载请附上博文链接！
