07-youhua.Rmd

# 最优化 {#opt}

## 数学本质

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

## 简史

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

- 1960s，早期内点法

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

- 1980s，线性规划的多项式时间内点法

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

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

## 凸集

- 仿射集 $x = \theta x_1 + (1-\theta)x_2$，包含所有经过任意两个集合内点的线

- 凸集 包含所有集合内任意两点间线段

- 凸组合 $x = \theta_1x_1+\theta_2x_2+...+\theta_kx_k$，其中$\theta_1+...+\theta_k = 1, \theta_i \geq 0$

## 最小二乘法

最小化$||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$是求函数一阶与二阶导数的时间，实际问题转化为凸优化问题不容易发现但确实可以求解。