凸优化学习（1）——什么是凸优化、凸集、凸函数

🍅 写在前面
👨‍🎓 博主介绍：大家好，这里是hyk写算法了吗，一枚致力于学习算法和人工智能领域的小菜鸟。
🔎个人主页：主页链接（欢迎各位大佬光临指导）
⭐️近期专栏：机器学习与深度学习
LeetCode算法实例
张量分解

凸优化系列知识，详见下方链接：

凸优化学习(1)——什么是凸优化、凸集、凸函数
凸优化学习(2)——梯度类方法求解(gradient descent)
本系列文章主要参考：卡耐基梅隆凸优化系列课程

什么是凸优化

优化

首先介绍什么是优化问题。优化可等同于数学规划，指的是在一系列可行解中找到最优的元素。

凸优化

在凸集上进行的最优化过程就是凸优化。在众多最优化过程中，凸优化是一种最为常见并且最重要的优化过程。因为凸优化有一个良好的性质：局部最优解也是全局最优解。 有了这个性质，我们就不需要证明局部解是否能收敛到全局最优。因此，凸优化有着广泛的应用范围，在有的问题不是凸的时候，我们往往也会将问题转化为凸优化问题来解决。

凸集

在这里插入图片描述
即凸集中任意两点连线均还在凸集中，下图中左侧为凸集，右侧为非凸集。

凸函数

h(x)为在n维空间定义域为凸集S的函数，若对于任意实数 $\alpha (0<\alpha<1)$ ，以及凸集S中任意两个不同的点x和y，都有：

$h(\alpha x+(1-\alpha) y) \leq \alpha h(x)+(1-\alpha) h(y)$
即任意两点的连线都在函数的上方，下图就是一个标准的凸函数。
在这里插入图片描述
凸函数f拥有以下几个重要性质
1、一阶特性

$\ge f(x) + \nabla f(x)(y - x)$
2、二阶特性
${\nabla ^2}f(x) \succ 0$
这里的 $\succ 0$ 表示的是矩阵是半正定的
3、Jensen不等式

$f(E(x)){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \le {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} E(f(x))$

向量范数

这里补充一个非常重要的概念，很多运算都是基于其：向量范数
1、0范式： ${\left\| x \right\|_0}$ 表示向量或集合中非零元素的个数。
2、1范式： ${\left\| x \right\|_1}$ 表示向量或集合中所有元素绝对值之和。
3、2范式： ${\left\| x \right\|_2}$ 表示向量或集合中所有元素平方和的平方根。

凸优化一般形式

在这里插入图片描述
当f(x),g(x)均为凸函数，而h(x)为仿射函数时，该优化问题是一个凸优化问题。凸优化也可以解释为目标函数 f(x) 为凸函数而起约束围成的可行域为一个凸集。

常见的凸优化问题有：线性规划(linear programs)、二次规划(quadratic programs)、半正定规划（semidefinite programs）。接下来详细介绍每一种凸优化问题的形式。

线性规划（c为向量，D、A为矩阵）
${\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$
二次规划(要求Q为半正定矩阵)
${\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$
半正定规划（X一般表示矩阵）

$\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}$