最优化（Optimization）概述

持续补充更新ing   
By 谈谈天

• 针对实际问题，寻找、改进或构建好的数学模型
  
• 精准判别数学模型的结构和类别
  
• 熟稔优化问题性质的分析
  
• 通过典型优化软件程序进行求解
  
• 待理论功底深厚、实践经验丰富后，进一步地，可以考虑设计新的优化算法
  

Good structure leads to good properties，and good properties can result in wide applications.

• 连续优化，离散优化： 离散优化问题往往更难求解，可以转化（松弛）为一系列连续优化问题进行求解，例如分支定界法。
  
• 无约束优化，约束优化： 很多约束优化问题的求解也是转化为一系列的无约束优化问题来做，例如增广拉格朗日法、罚函数法。然而，约束优化问题也是值得研究的。借助于约束函数，我们能够更好地描述可行域的几何性质，进而更有效地找到最优解。
  
• 随机优化，确定性优化： 随机优化具有未知参数，引入不确定性。此外，很多确定性优化算法都有相应的随机版本，随机性使得这些算法在特定问题上具有更低的计算复杂度或者更好的收敛性质。
  
• 线性规划，非线性规划： 非线性函数 -> 分片线性函数（piece-wise linear approximation）逼近。单纯形法，多项式时间算法的存在性，内点法。
  
• 凸优化，非凸优化： 凸优化具有很好的性质，学术上被广泛研究。正因为凸优化的重要性，我们要学会：1）判断一个问题是否是凸优化问题；2）进一步明晰非凸优化问题中的哪些函数导致了非凸性，以便设计凸优化模型来逼近原问题（例如，压缩感知问题中，用 范数替换 范数）。
  

• 深度学习
  
• 压缩感知
  
• 最优运输
  
• 信号与图像处理
  
• 强化学习
  
• 模式识别
  
• 金融工程
  
• 电力系统
  
• 
  

• 目标函数为极小化收益的方差：二次规划
  
• 目标函数为极小化风险价值（value at risk）函数：混合整数规划
  
• 目标函数为极小化条件风险价值（conditional value at risk）函数：非光滑优化 -> 线性规划
  

• 泰勒（Taylor）展开： 对于一个非线性的目标或者约束函数，我们通过其泰勒展开用简单的线性函数或者二次函数来逼近，从而得到一个简化的问题。Taylor展开在最优性理论的证明中有很重要的应用。
  
• 对偶（Duality）： 每个优化问题都有对应的对偶问题。当原问题比较难解的时候，其对偶问题可能很容易求解，例如：1）无论原问题是否为凸问题，拉格朗日对偶函数为凹函数。又约束集合为凸集，拉格朗日对偶问题是一个凸优化问题，具备良好的性质；2）原问题的约束个数比决策变量维数更小时，对偶问题的决策变量维数会比原问题的小，从而可能在相对较小的决策空间中求解；3）
  
• 拆分： 对于一个复杂的优化问题，可以将变量进行拆分。通过引入更多的变量，得到每个变量的简单问题（较容易求解或解有显式表达式），进而通过交替求解等方式得到原问题的解。例如：
  

• 块坐标下降： 解决决策变量维数很大的优化问题，逐步求解分量。