最优化
数学本质
当\(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)\]
- 超平面与半空间都是凸的