凸优化(Convex Optimization)

1.1 应用
1. 资金分配规划，比如投资一笔钱建工厂生产某种产品，用多少钱雇工人，多少钱买原料，多少买设备，多少钱投资技术，才获得最大的收益。
2. 电路板设计，目标是电路板的面积尽量小（成本尽量低），但需要满足一定的限制，比如元件之间的间距，布线之间的间距都需要大于一定的阈值。
3. 数据的拟合，给定一堆数据点，怎么在一个函数集合选择一个最有拟合的函数。
上面举的实际问题（决策，系统设计，系统分析，系统操作），都可以转化为数学上的优化问题。
凸优化的两个特殊例子，最小二乘和线性规划。
最小二乘：

\min \quad f_0(x)=\|Ax-b\|_2^2

线性规划：

\begin{array}{l}
\min \quad c^Tx \\
s.t. \quad a_i^Tx \leq b_i,i=1,\ldots,m
\end{array}

chebyshev近似问题

\min \quad \max_{i=1,\ldots,k}|a_i^Tx-b_i|

可以转化为线性规划问题

\begin{array}{l}
\min \quad t \\
s.t. \quad a_i^T-t \leq b_i, \quad i=1,\ldots,k \\
\quad\quad -a_i^T-t \leq -b_i, \quad i=1,\ldots,k
\end{array}

凸优化

\begin{array}{l}
\min \quad f_0(x)
s.t. \quad f_i(x) \leq b_i,\quad i=1,\ldots,m, \\
\end{array}

其中\inline f_0,\ldots,f_m:\boldmath{R}^n \to \boldmath{R}are convex
优化问题分类

optimization\left \{ 
\begin{array}{l}
convex \left \{\begin{array}{l} linear \quad programming\\ least-squares\\ general \quad convex \end{array}\\
noconvex
\end{array}