EE364a Lecture1

1. 数学优化问题的定义和组成

2. 数学优化问题的求解

• 一般的优化问题不容易求解：计算时间长，不能总是找到解等因素；
• 有一些问题容易求解：
  • 最小二乘
  • 线性规划
  • 凸优化

3. 最小二乘问题 $min\mathrm{\mid }\mathrm{\mid }Ax-b\mathrm{\mid }{\mathrm{\mid }}_2^{2}min\; ||Ax-b||\_2^2$

• 有解析解；
• 可靠有效的算法；
• 时间复杂度与$A^{m\ast n}A^\{m*n\}$相关，为$n^{2}mn^2m$；
• 容易识别最小二乘问题，可以有一些调整，如正则、权重等；

4. 线性规划

$min{c}^{T}xmin\backslash \; c^Tx$
$s\mathrm{.}t\mathrm{.}{a}^{T}x\le bs.t.\backslash \; a^Tx\backslash leq\; b$

• 无解析解；
• 有成熟的算法；
• 时间复杂度正比于$n^{2}m(m>n)n^2m(m>n)$
• 可以将一些问题转化为线性规划，如$l_{1}l\_1$范数，$l_{\mathrm{\infty }}l\_\backslash infty$范数，分段线性函数问题等；

5. 凸优化问题

• 定义：目标和约束函数都是凸的；

• $f(\alpha x+\beta y)\le \alpha f(x)+\beta f(y)f(\backslash alpha\; x+\backslash beta\; y)\backslash leq\; \backslash alpha\; f(x)+\backslash beta\; f(y)$
  $\alpha +\beta =1,\alpha \ge 0,\beta \ge 0\backslash alpha\; +\; \backslash beta\; =1,\; \backslash alpha\backslash geq\; 0,\backslash beta\backslash geq\; 0$

• 计算时间$max\{n^3,n^{2}m,F\}max\backslash \{n^3,n^2m,F\backslash \}$，$FF$是估计函数$f_{i}f\_i$及其一二阶梯度的代价；

• 很难识别一个问题是凸优化问题；

• 很多问题可以转化为凸优化问题，利用成熟的技术求解；

6. 非线性优化

• 局部最优问题
  • 需要初始值设定
  • 计算快，可拓展到大规模问题
  • 与全局最优无直接关联
• 全局最优问题：一般利用凸优化解决，但最坏情况可能是指数时间；