何键浩 李绿周

(中山大学计算机学院 广州 510006)

优化(optimization)是计算机科学与数学领域十分重要的基础研究之一，同时也是机器学习的核心工具[1].相关理论与方法广泛应用于各类工业生产[2]、工程设计与管理[3-5]、交通运输[6]、经济决策[7]、市场管理[8]等关乎国计民生的重要领域.一个具体的优化问题由3个基本要素组成：1)目标函数(或损失函数)，即决策者需要优化的指标，如总消耗、总收益等，数学形式表现为由优化变量到指标的函数/映射.2)优化变量，即决策者可以调整且会影响到目标函数的变量，如产品工艺、资金分配等.3)约束条件，即在决策过程中必须遵守的限制，如安全标准、资源储备总量等.优化过程就是在约束条件的限制下，寻找能最小化或最大化目标函数的优化变量的赋值.优化有时候也被称为数学规划，下文中优化与规划意义等价，具体使用的词汇将根据该细分方向的用词习惯决定.

根据优化问题的变量是否连续，优化技术可以分为离散变量优化(也称为组合优化)和连续变量优化两大类.其中，根据目标函数是否是凸的，连续变量优化又可分为凸优化和非凸优化.凸优化主要研究的是目标函数为凸函数且优化变量可行域为凸集的优化问题，由于凸集凸函数有许多优秀的性质(例如极小值即最小值)，使得凸优化问题有很多高效的解法，在应用迭代方法求解时也能获得良好的收敛速度.因此，凸优化技术方面已有成体系的方……