🍅 写在前面
👨🎓 博主介绍：大家好，这里是hyk写算法了吗，一枚致力于学习算法和人工智能领域的小菜鸟。
🔎个人主页：主页链接（欢迎各位大佬光临指导）
⭐️近期专栏：机器学习与深度学习
LeetCode算法实例
张量分解
凸优化系列知识，详见下方链接：
凸优化学习(1)——什么是凸优化、凸集、凸函数
凸优化学习(2)——梯度类方法求解(gradient descent)
凸优化学习（3）——对偶方法、KKT条件、ADMM)
本系列文章主要参考：卡耐基梅隆 凸优化系列课程
什么是凸优化
优化
首先介绍什么是优化问题。优化可等同于数学规划，指的是在一系列可行解中找到最优的元素。
凸优化
在凸集上进行的最优化过程就是凸优化。在众多最优化过程中，凸优化是一种最为常见并且最重要的优化过程。因为凸优化有一个良好的性质：局部最优解也是全局最优解。 有了这个性质，我们就不需要证明局部解是否能收敛到全局最优。因此，凸优化有着广泛的应用范围，在有的问题不是凸的时候，我们往往也会将问题转化为凸优化问题来解决。
凸集
即凸集中任意两点连线均还在凸集中，下图中左侧为凸集，右侧为非凸集。
凸函数
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
下一节讲解如何具体进行凸优化方法分析问题。