07-youhua.Rmd

# 最优化 {#opt}

## 数学本质

当$f_i(x)\leq b_i,(i = 1,...,m)$时，最小化$f_0(x)$。也就是满足限制条件下最小化某函数时其变量$x$的取值。

## 简史

- 1900-1970 理论发展期

- 1947，Dantzig 提出线性规划的 simplex 算法

- 1960s，早期插值方法

- 1970s，椭球法与其他亚梯度方法

- 1980s，线性规划的多项式时间插值法

- 1990之前主要运筹学里用，后来用到工程里

- 1990年后，应用于工程

- 现在，非线性凸优化的多项式时间内点法

## 最小二乘法

最小化$||Ax-b||_2^2$，其解析解为$x^\star = (A^TA)^{-1}A^Tb$，该算法比较成熟，计算时间正比于$n^2k(A\in R^{k\times n})$

## 线性规划

线性规划问题没有解析解，求解算法比较成熟，如果$m\geq n$,求解时间正比于$n^2m$

## 凸优化

将问题转化为凸函数$f_i(\alpha x+\beta y)\geq \alpha f_i(x)+\beta f_i(y)$ ，如果$\alpha + \beta = 1$，$\alpha \geq 0, \beta\geq 0$，最小二乘法与线性规划是凸优化的特殊形式。

求解凸优化问题没有解析解，求解时间正比于 $max\{ n^3,n^2m,F\}$，$F$是求函数一阶与二阶导数的时间，实际问题转化为凸优化问题不容易发现但确实可以求解。

## 仿射集

- $$x = \theta x_1 + (1-\theta)x2$$
- 仿射集：穿过任意两点的线的集合
- 凸集：仿射集里的线性片段 `$0\leq \theta \leq 1$`
- 凸组合 $$x = \theta_1 x_1 + \theta_2 x_2+...+\theta_kx_k, \theta_1+\theta_2+...+\theta_k = 1, \theta_i\geq0$$
- 超平面 $${x|a^Tx = b}(a\neq 0)$$
- 半空间$${x|a^Tx \leq b}(a\neq 0)$$
- 超平面与半空间都是凸的