最优化（Optimization）道与术

时间：2024-07-01 13:22:37 浏览：次

Authored by 谈谈天

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

最优化的关键技能包括：

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

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

最优化问题一般可描述为 $\\min\\limits_x \\ f(x)\\\\ s.t. \\ x\\in\\chi \ ag{1}$

其中， $x=(x_1,x_2,\\cdots,x_n)^T\\in \\mathbb{R}^n$ 是决策变量； $f:\\mathbb{R}^n\\rightarrow \\mathbb{R}$ 是目标函数； $\\chi\\subseteq \\mathbb{R}^n$ 是约束集合或可行域；记号s.t. 是“subject to”的缩写，专指约束条件。

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

通常地，最优化问题有以下分类方式：

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

针对模型 $(1)$ ，对于可行点 $\\overline{x}$ （即 $\\overline{x}\\in\\chi$ ），
- 如果 $f(\\overline{x})\\leq f(x), \\forall x\\in \\chi$ ，那么称 $\\overline{x}$ 为问题 $(1)$ 的全局极小解（点），有时也称为（全局）最优解或最小值点；
- 如果存在 $\\overline{x}$ 的一个 $\\epsilon$ 邻域 $N_\\epsilon(\\overline{x})$ ，使得 $f(\\overline{x})\\leq f(x), \\forall x\\in N_\\epsilon(\\overline{x})\\cap\\chi$ ，那么称 $\\overline{x}$ 为问题 $(1)$ 的局部极小解（点），有时也称为局部最优解；
- 进一步地，如果 $f(\\overline{x})< f(x), \\forall x\\in N_\\epsilon(\\overline{x})\\cap\\chi, x\ eq\\overline{x}$ 成立，则称 $\\overline{x}$ 为问题 $(1)$ 的严格局部极小解（点）。

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

深度学习，强化学习，压缩感知，最优运输，金融工程，电力系统，物流服务， $\\cdots$

面对一个优化问题，我们有诸多方法进行求解。下面的两张图，展示了我个人梳理的一个分类。

图2、3展示了我对优化问题求解方法的分类，包括：精确算法、（元）启发式算法、新兴学习算法。

『 精确算法 』是最为经典的优化方法，大致可以分为连续和离散/组合两大类。这里着重讨论处理离散/组合类问题的方法，事实上，离散/组合类问题相比于连续问题更加困难。对于此类问题，本质上只能通过隐枚举法或枚举法的思想来求解问题，例如分支定界法（Branch-and-Bound, BB）就是一种隐枚举法。在此基础上，可以动态地增加相应线性规划模型的有效不等式（切），这即是分支定切法（Branch-and-Cut）。若是不加切，而是将相应的线性规划模型转化为等价的Dantzig-Wolfe模型，进而利用列生成（Column generation）方法进行求解，则是分支定价法（Branch-and-Price）。

另外，由于商业/开源求解器（Solver）的日益成熟与强大，我将其单独划分为“一类”。求解器是优化方法与软件工程交融的技术结晶，其中商用的翘楚包括Gurobi、CPLEX以及国产的COPT等，开源的则有SCIP等。除此之外，还有一些领域专用求解器，例如为求解TSP问题服务的Concorde。Concorde目前在公开TSP数据集中，获得了其中110个数据的最优解记录，其中最多的TSP位置点达到了85900个。这样的规模，很难不让一些启发式算法和学习算法汗颜。

『（元）启发式算法 』启发式算法是搜索算法的典型代表之一，在运算过程中利用有效的经验法则来改进给定的可行解，其能较快得到较好的可行解，但解的质量相较于最优解而言存在一定的未知性。更详细的分类见图3。首先是Problem-specific heuristics，这是一类针对特定问题设计的启发式算法，例如TSP、VRP这类路由问题中著名的Lin-Kernighan-Helsgaun (LKH) 算法，其具备精巧的设计，在论文中也是非常强大的baseline的存在。然而，现实中的优化问题灿若繁星，并非每一个都有LKH这么优秀的算法。为了在有限的时间与计算资源下有效求解这些问题，学者们通过模拟一些自然规律（如适者生存，金属冶炼，鸟群飞行等），设计了一系列智能算法，这些算法也称为元启发式算法（Metaheuristic）。

Metaheuristic是优化领域的主要研究分支之一，包罗众多成果。进一步地，我们可以将其分为两类，Single solution-based和Population-based。正如其名，Single solution-based的算法依据问题结构编码一个初始解，并设计一些“不断向好”的更新规则，更新当前的解。爬山法（Hill Climbing）是其中的代表性算法。然而，回顾图1中的Landscape，设想我们在最左侧放置一个小球（对应一个初始解），其会落入局部极小解的“山谷”而无法进一步找到全局极小解。再者，若将小球放入右侧的“高原（Plateau）”，其将不会进一步滚动（对应优化）。为了避免这种情况的发生，在优化初期，我们会依一定概率 $p$ 容许对较差解的“探索（Exploration）”，而在优化后期不断加强“开发（Exploitation）”，如此赋予算法“跳出”局部极小解的能力。这也是著名的模拟退火（Simulated Annealing）算法的思想。

根据上述分析，我们或许可以想到，如果同时放置很多小球（对应多个初始解），应该可以提高找到全局极小解的概率。的确，这多个初始解够成了一个解的种群，这类算法也被划分为Population-based。其代表性算法包括更擅长处理连续优化问题的粒子群算法（Particle Swarm Optimization）、差分进化算法（Differential Evolution），和更擅长处理离散/组合优化问题的遗传算法（Genetic Algorithms）、分布估计算法（Estimation of Distribution Algorithm）等。这个领域的最新进展，可以关注一些领域顶级刊物和会议：IEEE Transactions on Evolutionary Computation, IEEE Computational Intelligence Magazine, Evolutionary Computation, IEEE Transactions on Cybernetics, IEEE Transactions on Emerging Topics in Computational Intelligence, Swarm and Evolutionary Computation, IEEE CEC, ACM GECCO等。

『 新兴学习算法 』

伴随着机器学习等新兴技术的巨大成功，涌现了这类新的优化技术。具体做法很多，这里列举三个。

第一类：Data-driven metaheuristic[4]。旨在引入机器学习技术，为（元）启发式算法领域带来新的活力。

Data-Driven Evolutionary Optimization

第二类：ML4CO[5]。可参考我写过的一篇知乎回答：

运筹学与机器学习结合前景如何？

第三类：Predict-then-Optimize (PTO)，“预测+优化”。

运筹OR帷幄：优化｜当机器学习上运筹学：PyEPO与端对端预测后优化

值得说明的是，针对同一实际问题，从不同的设计角度切入，可以对应性质很不相同的问题，其求解难度和需要的算法也将差别很大。

例如，在投资组合优化（Portfolio Optimization）问题中，人们总体上希望通过寻求最优的投资组合以降低风险、提高收益。

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

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

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