凸优化

凸集

设 ，对于所有的 及 都有 ，则称 为凸集。

凸组合

设 ， 是一组非负实数且 ，则

称为一个凸组合。

为凸集的充要条件是 中有限个点的凸组合仍在 中。

重要凸集

超平面

形如 的集合

半空间

形如 的集合

多面体

形如 的集合，其中 。
多面体是有限个半空间和超平面的交集。

球

球是空间中到某个点距离（或两者差的范数）小于等于某个常数的点的集合。

称为中心为 ，半径为 的（欧几里得）球。

范数球：当使用不同的范数定义距离时候，我们还可 以得到不同类型的范数球。

椭球

形如 的集合，其中 （即 。

（半）正定锥

记 为 对称矩阵的集合；

为 半正定矩阵的集合；

为 半正定矩阵的集合；

称为半正定锥， 称为正定锥。

保凸运算

• 任意多个凸集的交为凸集：若 是 中的凸集，则 是 凸 集 。
• 设 为
  则 是凸集是凸集；是凸集 是凸集；即缩放、平移和投影变换等（仿射变换）都是保凸运算。

凸函数

设 上的，定义域 是凸集，如果对于所有的 都有

则称 为 上的凸函数 。

如果将上式的 改为 ，则称 为 上的严格凸函数。

实际上 是 上的凸函数的 对任意的正整数 ，及任意不完全相同的 ，如果，有

凸函数判定

对于可微函数，可以利用导数判断其凸性。
（一阶条件）设 是凸集， 在 上可微，则 在 上是凸函数的充要条件是对任意的 ，都有：

证明：（必要性）设 且

$$f(\alpha\boldsymbol{y}+(1-\alpha)\boldsymbol{x})\leq\alpha f(\boldsymbol{y})+(1-\alpha)f(\boldsymbol{x})\\\Rightarrow f(\boldsymbol{y})-f(\boldsymbol{x})\geq\frac{f(\boldsymbol{x}+\alpha(\boldsymbol{y}-\boldsymbol{x}))-f(\boldsymbol{x})}\alpha$$

由泰勒定理

因此，

（充分性）设对任意的 ，由于 是凸集， ​​

$$f( \boldsymbol{x}) \geq f( \mathbf{z} ) + \nabla f( \mathbf{z} ) ^{T}( \mathbf{x} - \mathbf{z} )\tag{1}$$ $$f( \boldsymbol{y}) \geq f( \mathbf{z} ) + \nabla f( \mathbf{z} ) ^{T}( \mathbf{y} - \mathbf{z})\tag{2}$$

$\alpha(1)+(1-\alpha)(2)$ 得：

$$\alpha f(\boldsymbol{x})+(1-\alpha)f(\boldsymbol{y})\geq f(\mathbf{z})+\nabla f(\mathbf{z})^T0=f(\mathbf{z})=f(\alpha\boldsymbol{x}+(1-\alpha)\boldsymbol{y})$$

所以 是凸函数。

梯度单调性判定

设 ， 在凸集 上可微，则 为凸函数当且仅当 为凸集，且 为单调映射，即：

二阶条件判定

设 ， 是凸集， 在 上连续二阶可微，则 在 上是凸函数的充要条件是 是半正定矩阵。

常见凸函数

凸优化

如果优化问题

满足：

1. 是定义在凸集 上的凸函数；
2. 是凸集。

则上述问题为凸优化问题。

凸优化重要性质

设优化问题 是凸优化，则 的任何局部最优解也是全局最优解。

证明： 设是P问题的局部最优解，则存在 ，当 （即 ）

$$f(x^{(1)})\leq f(x)$$

假设 不是全局最优解，则存在 ，满足 由于可行集是凸集， 是凸函数，所以

$$f(\alpha x^{(1)}+(1-\alpha)x^{(2)})\leq\alpha f(x^{(1)})+(1-\alpha)f(x^{(2)})\\<\alpha f(x^{(1)})+(1-\alpha)f(x^{(1)})=f(x^{(1)})$$

当 充分接近1时，
由于 ，这与 是局部最优解矛盾。