凸优化总览

优化/数学规划 Optimization/Mathematical Programming

$\mathrm {minimize} f_0(x)(\mathrm{objective\ function})\\ s.t. f_i(x)\le b_i,i=1,\cdots,m (\mathrm{inequality\ constrant})$

其中 $f_i,f_0:R^n \to R$。

$X^*$ 最优(optimal)，不一定只有一个 $\Leftrightarrow$ $\forall z, z\in \{f_i(z)\le b_i,i=1,\cdots,m\}$(feasible set)

$f_0(z)\ge f_0(X^*)$

应用：数据拟合问题

Minimize Squared Error

应用：线性二次调节器 LQR

$X_k=AX_{k-1}+BU_k$

$\min_{\{U_k\}} J=\sum_{k=1}^N(X_k^TQX_k+U_k^TRU_k)$

多用户能量控制问题

$SINR_i=\frac{P_i}{\sigma_i^2+\sum_{j\not=i} \alpha_{ji} P_j}$

图像处理

分片光滑

$\Phi_0(x,y)\to\Phi(x,y)$

TV 范数

$||\Phi||_{TV}=\sum_{x,y} \sqrt{(\Phi(x,y)-\Phi(x,y-1))^2+(\Phi(x,y)-\Phi(x-1,y))^2}$

$\min_{\Phi} ||\Phi||_{TV}+\lambda||\Phi-\Phi_0||_F^2$

$TV-L_2$

模型。

最短路问题

$\min_{j} \sum_{i,j\in E} w_{i,j} X_{i,j}\\ s.t. X_{i,j}=0或1\\ \sum_{j} X_{ij}-\sum_{j} X_{ji}=1,i=s;-1,i=d;0;$

线性规划/非线性规划

$f_i(\alpha x+\beta y)=\alpha f_i(x)+\beta f_i(y)$

单纯形法。可行解一定在点或者边上。

凸规划/非凸规划

凸函数：

$f_i(\alpha x+\beta y)\le \alpha f_i(x)+\beta f_i(y)$

光滑/非光滑

在每个点可微。

连续/离散

单目标/多目标

$\alpha_1f_1(x)+\alpha_2 f_2(x)$