第7章最优化

7.1 数学本质

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

最小化 $||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)$
超平面与半空间都是凸的