凸函数优化笔记（1）
向量的范数 norm
我们用符号双竖杠来表示向量范数，例如
来表示向量
的范数。向量的范数是我们可以用来衡量向量“大小”或者“长度”的一个指标。其定义形式如下，我们通常说一个向量的
-norm为：
其中
为一个大于1的实数
如果
，那么的范数就是我们熟知的曼哈顿距离的公式：
如果
，那么的范数就是我们熟知的欧几里得距离，他描述了向量的长度：
如果我们没有注明的值，通常我们默认，即
描绘
描述了向量
而当趋于
的时候，向量的范数趋向于中绝对值最大的分量，即：
柯西-施瓦茨不等式（Cauchy-Schwarz inequality）
柯西不等式公式为：
或者进一步可以写为：
回忆一下向量乘法的规则：
所以柯西不等式式其实只是在另一个方面论证了一个简单的事实 :
赫尔德不等式（Holder’s Inequality）
赫尔德不等式是柯西不等式的推广形式，其公式如下：
如果有一个和
，满足
，那么对于向量和
，以下不等式成立：
当和都等于 2 时，赫尔德不等式就是柯西不等式。换句话说，柯西不等式就是赫尔德不等式的特殊情况。
凸集（Convex Set）定义
对于集合中任意两点的连线，线上所有点仍然都在集合内的集合，叫做凸集（Convex Set）。例如：
对于任何在集合C内的两点
，有：
例如在上图中第一个图形是一个典型的凸集，因为图形内包括图形边线上任意两点的连线始终都在图形内；第二个图形是一个典型的非凸集，因为我们可以找到两个图形中的点，这两点的连线上的点并不是全在图形中；第三个图形也不是凸集，因为正方形边线上的点的连线可以不在集合内。
还有一些特殊的凸集，例如一个无限延展的二维平面或者三维空间，集合中任意两点的连线都在集合内；一条直线分割的平面的两个部分也都可以算作凸集。
凸集性质一：凸集的交集仍然是凸集
凸集性质二：非膨胀性（Non-expensiveness）
凸集外的任意两点，在凸集上的投影之间的距离，不会比两点本身之间的距离更远。用数学表示为：
画图表示为：
我们把这种性质叫做“Non-expensiveness”，非膨胀性。
什么是凸集外一点在凸集上的投影？例如上图中点在凸集
上的投影为：在凸集中，我们能找到的距离最近的点，用数学公式可以表示为：
这样的投影有一个性质：如果集合满足非空、闭集、凸集，集合外任意一点在集合上的投影是唯一的。
利普希茨条件 L-Lipschitz
我们说一个函数
是L-Lipschitz的，如果其满足：
利普希茨的条件在高维空间中也成立，其在高维空间的表示为：
对于一个函数
是L-Lipschitz的，如果其满足:
其中
是一个常数，如果是小于等于1的，那么我们说函数
是 non-expensiveness 的。
L-Lipschitz衡量了一个函数最快变化能有多快：例如
，在这样的情况下，
就是一个在二维平面上的函数，此时表示了斜率的最大值，即函数的导数存在上界，
。
L-光滑（L-Smooth）
我们说一个函数是L-光滑的（L-Smooth）如果函数符合以下条件：
- 是 “continuously differentiable”，或者说函数的梯度
存在且连续。 
这条定理其实描述了函数的二阶导数是有上界的，即
。
再进一步思考，如果一个函数的二阶导数是有上界的，那么其一定存在一个二次函数，作为函数的上界（upper bound）以及一个二次函数，作为函数的下届（lower bound）。
可导
可导和连续
**连续的定义：**如果函数
处连续，那么对于任意
，总存在一个
，使得对于所有满足
的
这个定义描述了函数
- 函数在
- 函数在
- 并且极限值等于其函数值
**可导的定义：**函数
)，使得对于任意给定的
的
，都有：
或者说，函数
或者我们还可以从左极限右极限的角度定义可导：
如果一个
可导意味着函数在
不可导一般意味着函数在
- 该点左极限 ≠ 右极限
- 该点极限无穷大
- 该点极限完全不收敛
可导一定连续，但是连续不一定可导
如果一个函数在其定义域内处处可导，那么我们称这个函数是一个可导的函数（differentiable function）。可导函数上任意一点都可以找到一条非垂直的、经过该点的切线。假设我们的函数可导，那么其在点上的切线为：
凸函数（Convex Funtion）
一个函数是凸函数如果其满足：
- 函数的定义域是一个凸集。
- 函数上任意两点的连线都大于等于函数本身。
用数学的语言来描述则为：dom()是一个 凸集，而且对于任何
，以及任意
，有：
用图像可以表示为：
常见的凸函数例如
、
、
。
吧所有的范数函数
也都是凸函数。范数函数满足两点性质：一是三角不等式（Triangle Inequality）
；二是绝对其次性（Absolute Homogeneity）
。因此我们可以证明：
这正好是凸函数的定义。
函数图像（Graph）和上方图（Epigraph）
我们定义一个函数的图像（graph）为构成函数的线条，定义为
而一个函数上方图（epigraph）为构成函数的线条以及其上方的空间组成的平面，定义为
一个函数的图像为构成函速的线条（下图中的深黑色线条），而epigraph为线条以及线条上方围成的面积组成：
我们可以观察到如果一个函数是凸函数，那么其的epigraph是一个凸集，反之亦然。
is convex function
is convex set
琴生不等式（Jensen’s Inequality）
对于凸函数来说，如有
，并且
，则存在：
证明TODO
根据凸函数的一阶性质，我们有：
我们令 
，
，于是我们有：
两边乘以一个整数
得到：
加起来所有式子，得到：
，所以
：
是凸函数
这基本上就是在另一个方面定义了凸函数，一个函数如果是凸函数，那么他大于等于自己的每一条切线。用图像可以表示为：
凸函数的二阶性质
如果函数的定义域
是凸集，而且函数二阶可导（即
Hessian矩阵存在），那么有：
**是凸函数 **
我们说一个矩阵A是半正定的（Positive Semidefinite），用符号表示为
，如果对于所有非零实向量，都满足
凸函数操作
- 如果有
多个凸函数，
，那么函数
在定义域
上也是凸函数。
证明
取
，因为
是凸函数，我们有对于
：
两边同时乘以一个正数，我们有：
把所有式子加起来，我们有：
即：
即：
是凸函数
证明
因为
是一个凸函数，所以我们有：
因为
是一个仿射函数，
:
所以
也是一个凸函数
凸函数的局部最小值即为全局最小值
**任何凸函数的局部最小值都是全局最小值（Global Minima）。**用数学语言表示为，如果是凸函数
的局部最小值（Local Minima），那么是这个函数的全局最小值（Global Minima），意味着
凸函数梯度为0的点即为其全局最小值
**如果一个凸函数可导，那么其梯度为0的点就是其全局最小值。**用数学语言表示为，如果函数可导并且是凸函数，而且定义在一个开放的域中。那么如果存在一个使得
，那么是一个全局最小值。
严格凸函数
一个函数
是严格凸函数（Strictly Convex）如果其满足：
- 函数定义域是一个凸集
- 对于所有
以及 
来说，我们有：
例如下图中左图不是严格凸函数，而右图是严格凸函数：
严格凸函数最多只有一个全局最小值
最小值点
设 
为一个凸函数，且 
为一个凸集。点 
是函数 在集合 
上的最小化点（Minimizer），若其满足：
求最小化点
设函数 是凸函数且在其开定义域 
上可微，并设 为一个凸集。点 
是函数 在集合 上的最小化点，当且仅当满足以下条件：
下水平集（Sublevel Set）
如果有一个函数
，我们说集合
是函数的
-下水平集（-sublevel set）。
用图像可以表示成：
凸优化（Convex Optimization）
最后我们定义凸优化问题：
- 是一个凸函数。
是一个凸集。
凸优化问题有以下我们梦寐以求的性质：
- 在凸优化问题中，每一个局部最小值都是全局最小值。
课后思考
最小二乘法
回忆一下我们在线性回归中使用的损失函数，
，其中
。
