凸集

1. 基本集合

* 仿射集合

• 集合C内任意两点的直线，仍在C内
• 直线，平面，超平面

* 凸集

• 集合C内任意两点的线段，仍在C内

* 锥

• 过原点的射线，射线族，角

* 分离和支撑超平面

P43页(凸优化)

• 分离超平面
• 支撑超平面

2. 凸函数

* 凸函数

$f(\theta x+(1-\theta )y)\leq \theta f(x)+(1-\theta)f(y)$

* 上境图

• P83(凸优化)

• 一个函数是凸函数，当且仅当其上境图是凸集

* Jessen不等式

$f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y)$

$f(Ex)\leq Ef(x)$

* 保凸算子

• 凸函数的非负加权和

$f(x)=\omega_1f_1(x)+...+\omega_nf_n(x)$

• 凸函数的仿射函数

$g(x)=f(Ax+b)$

• 凸函数逐点最大值，逐点上确界 （函数离散，是逐点求最大值；函数是连续，是逐点求上确界）

$f(x)=max(f_1(x),...,f_n(x))$

$f(x)=\sum\limits_{y\in A}g(x,y)$

* 共轭函数

原函数：f的共轭函数

$f^*(y)=\sup\limits_{x\in dom f}(y^Tx-f(x))$

等式右边是关于y的仿射函数，他们逐点求上确界得到共轭函数； 共轭函数是凸函数

* Fenchel不等式

• 设 $f^*(y)=\sup\limits_{x\in dom f}(y^Tx-f(x))$

则：

• $f(x)+f^*(y) \geq x^Ty$

应用

• $f(x)=\frac{1}{2}x^TQx$；$f^*(y)=\frac{1}{2}y^TQ^{-1}y$

=>

• $x^TQx+y^TQ^{-1}y \geq 2x^Ty$