凸优化知识

Definition1.

凸集定义 A set $\Omega$ is convex if $\forall x_{1},x_{2}\in \Omega$ and $\forall t\in [0\;1]$, the convex combination $x=tx_{1}+(1-t)x_{2}$ is also in $\Omega$

显然，集合$\Omega=\{x|Ax=b\}$ 符合上述定义，为凸集。所以，对于优化问题

$(P_J): min_{\substack x} J(x)\quad subject\quad to \quad b=Ax$的可行解集（feasible set）为凸。

为了使该优化问题成为一个凸优化问题，需要对惩罚函数$J(x)$加上一个凸函数的限制。

Definition2

凸函数定义 A function $J(x):\Omega\rightarrow R$ is convex if $\forall x_{1},x_{2}\in \Omega$ and $\forall t\in [0\;1]$, the convex combination point $x=tx_{1}+(1-t)x_{2}$ satisfies $J(tx_{1}+(1-t)x_{2})\leq tJ(x_{1})+(1-t)J(x_{2})$.

如果$J(.)$二次可微，上述定义可以改写为

A function $J(x):\Omega\rightarrow R$ is convex if $\forall x_{1},x_{2}\in \Omega$ if and only if $J(x_{2}) \ge J(x_{1})+\bigtriangledown J(x_{1})^{T}(x_{2}-x_{1})$. or alternatively if and only if $\bigtriangledown^{2} J(x_{1})$ (Hessian matrix) is positive-definite.

The squared $l2$-norm is strictly convex(严格凸)因为其Hessian matrix 严格正定 for all $x$。（$\bigtriangledown^{2} \lVert x \rVert_{2}^{2}=2I \ge 0$）

回到上述优化问题，可以看到其惩罚函数为凸，以及约束条件（constriant-set）均为凸函数，所以可以保证唯一解。（对于非严格凸，不能保证解唯一性）

问题来了，对于$J(x)= \lVert x \rVert_{2}^{2}$可以保证凸，那么也可以由其他的凸或者严格凸的$J(x)$。

$l_{p}$范数:为x向量各个元素绝对值p次方和的1/p次方.

$\lVert x \rVert_{p}^{p}=\sum_{i}\lvert x_{i} \rvert ^{p}$

其中，$l_{\infty}$范数:  为x向量各个元素绝对值最大那个元素的绝对值，$l_{1}$范数：x向量各个元素绝对值之和。