最优化（Optimization）概述

redhat9i

持续补充更新ing   
By 谈谈天

最优化问题（也称为优化问题）泛指定量决策问题，主要关心如何对有限资源进行有效分配和控制，并达到某种意义上的最优。
最优化的关键技能包括：

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

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

最优化问题一般可描述为
其中， 是决策变量； 是目标函数； 是约束集合或可行域；记号s.t. 是“subject to”的缩写，专指约束条件。

最优化模型与算法相辅相成，促进最优化学科不断发展。实际应用导出的各种各样的最优化模型给最优化学科不断注入新鲜的血液，对现有的优化算法进行挑战并推动其向前发展；最优化算法的设计及理论分析帮助实际问题建立更鲁棒稳定的模型。
通常地，最优化问题有以下分类方式：

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

针对模型  ，对于可行点  （即 ），
- 如果 ，那么称  为问题  的全局极小解（点），有时也称为（全局）最优解或最小值点；
- 如果存在  的一个 邻域 ，使得 ，那么称  为问题  的局部极小解（点），有时也称为局部最优解；
- 进一步地，如果 成立，则称  为问题  的严格局部极小解（点）。



现实中，最优化具备广泛的应用，可谓“万物皆优化”：

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

针对同一实际问题，从不同的设计角度切入，可以对应性质很不相同的问题，其求解难度和需要的算法也将差别很大。
例如，在投资组合优化问题中，人们总体上希望通过寻求最优的投资组合以降低风险、提高收益。

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

在设计优化算法时，我们有一些基本的准则或技巧。对于复杂的优化问题，基本的想法是将其转化为一系列简单的优化问题（其最优解容易计算或者有显式表达式）来逐步求解。 典型技巧有：

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

可以拆分成

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

参考文献
[1] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[2] 文再文等. 最优化：建模、算法与理论. 高等教育出版社, 2020.