凸优化学习（1）——什么是凸优化、凸集、凸函数
🍅 写在前面
👨🎓 博主介绍：大家好，这里是hyk写算法了吗，一枚致力于学习算法和人工智能领域的小菜鸟。
🔎个人主页：主页链接（欢迎各位大佬光临指导）
⭐️近期专栏：机器学习与深度学习
LeetCode算法实例
张量分解
凸优化系列知识，详见下方链接：
凸优化学习(1)——什么是凸优化、凸集、凸函数
本系列文章主要参考：卡耐基梅隆 凸优化系列课程
目录
- 什么是凸优化
- 优化
- 凸优化
- 凸集
- 凸函数
- 向量范数
- 凸优化一般形式
什么是凸优化
优化
首先介绍什么是优化问题。优化可等同于数学规划，指的是在一系列可行解中找到最优的元素。
凸优化
在凸集上进行的最优化过程就是凸优化。在众多最优化过程中，凸优化是一种最为常见并且最重要的优化过程。因为凸优化有一个良好的性质：局部最优解也是全局最优解。 有了这个性质，我们就不需要证明局部解是否能收敛到全局最优。因此，凸优化有着广泛的应用范围，在有的问题不是凸的时候，我们往往也会将问题转化为凸优化问题来解决。
凸集
即凸集中任意两点连线均还在凸集中，下图中左侧为凸集，右侧为非凸集。
凸函数
h(x)为在n维空间定义域为凸集S的函数，若对于任意实数 α ( 0 < α < 1 ) \alpha (0<\alpha<1) α(0<α<1)，以及凸集S中任意两个不同的点x和y，都有：
h
(
α
x
+
(
1
−
α
)
y
)
≤
α
h
(
x
)
+
(
1
−
α
)
h
(
y
)
h(\alpha x+(1-\alpha) y) \leq \alpha h(x)+(1-\alpha) h(y)
h(αx+(1−α)y)≤αh(x)+(1−α)h(y)
即任意两点的连线都在函数的上方，下图就是一个标准的凸函数。
凸函数f拥有以下几个重要性质
1、一阶特性
f
(
y
)
≥
f
(
x
)
+
∇
f
(
x
)
(
y
−
x
)
f(y) \ge f(x) + \nabla f(x)(y - x)
f(y)≥f(x)+∇f(x)(y−x)
2、二阶特性
∇
2
f
(
x
)
≻
0
{\nabla ^2}f(x) \succ 0
∇2f(x)≻0
这里的
f
(
x
)
≻
0
f(x) \succ 0
f(x)≻0表示的是矩阵是半正定的
3、Jensen不等式
f ( E ( x ) ) ≤ E ( f ( x ) ) f(E(x)){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \le {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} E(f(x)) f(E(x))≤E(f(x))
向量范数
这里补充一个非常重要的概念，很多运算都是基于其：向量范数
1、0范式：
∥
x
∥
0
{\left\| x \right\|_0}
∥x∥0表示向量或集合中非零元素的个数。
2、1范式：
∥
x
∥
1
{\left\| x \right\|_1}
∥x∥1表示向量或集合中所有元素绝对值之和。
3、2范式：
∥
x
∥
2
{\left\| x \right\|_2}
∥x∥2表示向量或集合中所有元素平方和的平方根。
凸优化一般形式
当f(x),g(x)均为凸函数，而h(x)为仿射函数时，该优化问题是一个凸优化问题。凸优化也可以解释为目标函数 f(x) 为凸函数而起约束围成的可行域为一个凸集。
常见的凸优化问题有：线性规划(linear programs)、二次规划(quadratic programs)、半正定规划（semidefinite programs）。接下来详细介绍每一种凸优化问题的形式。
- 线性规划（c为向量，D、A为矩阵）
min x c T x s . t . D x ≤ d A x = b {\min _x}{\kern 1pt} {\kern 1pt} {c^T}x\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Dx \le d\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Ax = b xmincTxs.t.Dx≤dAx=b - 二次规划(要求Q为半正定矩阵)
min x c T x + 1 2 x T Q x s . t . D x ≤ d A x = b {\min _x}{\kern 1pt} {\kern 1pt} {c^T}x + \frac{1}{2}{x^T}Qx\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Dx \le d\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Ax = b xmincTx+21xTQxs.t.Dx≤dAx=b - 半正定规划（X一般表示矩阵）
min C X s . t . A i X ≤ b i , i = 1 , . . . . . m X ≻ 0 \begin{array}{l} {\min _{{\kern 1pt} {\kern 1pt} {\kern 1pt} }}CX\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {A_i}X \le {b_i},i = 1,.....m\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} X \succ 0 \end{array} minCXs.t.AiX≤bi,i=1,.....mX≻0
下一节讲解如何具体进行凸优化方法分析问题。