凸优化
- 提出者
- Stephen Boyd & Lieven Vandenberghe
- 年份
- 2004
- 类型
- Mathematical optimization framework
- 类别
- Mathematical programming
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
凸优化是数学优化中的一个子领域,研究在凸集上最小化凸函数的问题。该框架由 Stephen Boyd 和 Lieven Vandenberghe 在其里程碑式的 2004 年教科书中正式化并推广,它将包括线性规划、二次规划、半定规划和二阶锥规划在内的广泛问题家族统一在一个理论框架之下。其定义性特征是任何局部最优解也是全局最优解,这使得它在工程、统计学、机器学习和运筹学中具有可处理性和可靠性。
方法背后的直觉
想象一个碗状的山谷:无论你从哪里开始滚一个球,它最终都会停在同一个最低点。凸优化在数学上将这种几何形状形式化。目标函数是碗,可行域是凸形状的地形,算法是沿着斜坡滚动的球。由于没有隐藏的局部凹陷或欺骗性的山脊,你一定能找到真正的全局最小值——这使得该方法与一般的非线性优化在根本上不同且更可靠。
历史学
凸分析的理论基础可以追溯到 20 世纪初 Minkowski 和 Farkas 的工作,线性规划则在 20 世纪 40 年代通过 Dantzig 出现。内点法由 Karmarkar 于 1984 年引入并在 20 世纪 90 年代得到改进,使得一般的凸规划在计算上变得可处理。Boyd 和 Vandenberghe 于 2004 年出版的剑桥大学出版社教科书(在线免费提供)将数十年的研究成果综合成一个连贯、易于理解的框架,并催生了在 CVX、CVXPY 和相关工具中实现的规范凸规划范式。
何时使用
当目标函数和所有约束都可以表达或重构为凸函数时,使用凸优化。它适用于投资组合优化、带正则化的回归、网络流、支持向量机和控制设计。关键假设是可行集和目标函数的凸性;违反这些假设将消除全局最优性保证。当问题是非凸的时,考虑凸松弛或局部非线性求解器。当问题是线性的时,优先使用线性规划求解器以获得额外的效率。
局限与注意事项
- 适用性完全取决于问题是否可以以凸形式提出或近似;许多现实世界的问题本质上是非凸的。
- 内点法需要存储和分解大型矩阵,这使得内存和时间需求对于高维问题来说相当可观。
- 组合或整数问题的凸松弛可能产生分数解,这些解在没有舍入启发式方法的情况下无法直接处理。
- 问题建模需要专业知识:不正确的凸性断言会悄悄地消除理论保证,而求解器仍然会返回一个答案。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 只要能实现凸规划,就保证能获得全局最优解——没有收敛到局部最小值的风险。
- 通过内点法可实现多项式时间求解,即使对于大规模问题也具有实际效率。
- 对偶理论以零额外成本提供了最优性证明、具有经济学解释的对偶变量以及敏感性分析。
- 丰富的组合规则集 (DCP) 能够系统地验证凸性,并自动转换为求解器就绪形式。
应用
- 投资组合优化:在量化金融中,以收益目标和配置约束为条件下最小化方差或 CVaR。
- 机器学习:训练支持向量机、Lasso 和 Ridge 回归以及逻辑回归是典型的凸规划。
- 信号与图像处理:压缩感知、全变分去噪和稀疏恢复被构建为凸规划。
- 网络与资源分配:在容量约束下的最优路由、无线网络中的功率控制和带宽分配。
- 控制系统:基于半定规划的 H-infinity 控制器综合和李雅普诺夫稳定性验证。
使用方式
使用方式
分析师将决策问题构建为标准形式的凸规划:在凸不等式约束 fi(x) ≤ 0 和仿射等式约束 Ax = b 下最小化凸目标函数 f0(x)。正确构建模型——选择正确的变量表示并将所有约束表达为凸形式——是决定强大保证是否适用的关键第一步。
公式
\min_{x \in \mathcal{C}} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0,\; i=1,\ldots,m,\; Ax = b在求解之前,需要验证问题中的每个函数都是凸函数,这意味着其上图是一个凸集,或者等价地,它满足中点不等式。Boyd 和 Vandenberghe 的规范凸规划 (DCP) 规则集提供了一种系统的方法,通过组合规则来确认凸性,因此分析师无需为每个问题从头证明凸性。
公式
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \quad \forall x,y \in \text{dom}\,f,\; \theta \in [0,1]通过松弛带对偶乘子的约束来形成拉格朗日函数 L(x, λ, ν)。在 Slater 的约束限定条件下,强对偶性成立:原问题和对偶问题的最优值重合,并且 KKT 条件——平稳性、原/对偶可行性以及互补松弛性——既是全局最优性的必要条件也是充分条件。对偶性还提供了最优性证明和关于最优值如何随问题数据变化的敏感性信息。
公式
L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^T(Ax-b), \quad \lambda_i \geq 0内点法、梯度下降变体或近端算法通过可行集迭代地向最优值移动。对于光滑的无约束问题,具有合适步长的梯度步长以已知速率收敛。对于有约束或结构化问题,内点法以高精度实现多项式时间收敛,而像 ADMM 这样的首阶方法可以扩展到非常大的实例。
公式
x^{(k+1)} = x^{(k)} - t_k \nabla f_0(x^{(k)}), \quad t_k > 0常见陷阱
- 假设一个问题是凸的而没有正式验证——必须严格检查组合规则,而不是通过目标函数的视觉检查。
- 忽略数值条件:缩放不当的问题会导致求解器报告不准确或不可解的解,尽管理论上可行。
- 在非标准求解器或 Slater 条件失败的情况下忽略对偶间隙,这可能会使基于 KKT 的最优性声明无效。
- 在问题松弛掉整数或组合约束后,将凸松弛解视为原始问题的解。
常见问题
我如何知道我的问题是否是凸的?
检查目标函数和每个约束函数是否满足中点凸性不等式,或使用规范凸规划规则集验证凸性。如果每个函数都由已知的凸基元根据保持凸性的组合规则(例如,非减的凸外函数、凸内函数等)构建而成,则该问题是凸的。Boyd 和 Vandenberghe 的第三章提供了凸函数的广泛目录。
凸优化与线性规划有什么区别?
线性规划是凸优化的一种特例,其中目标函数和所有约束函数都是仿射(线性)函数。凸优化更为通用,包括二次规划、二阶锥规划和半定规划。虽然单纯形法和内点法可以求解线性规划,但只有内点法可以直接扩展到整个凸类。
凸优化能处理整数或二元变量吗?
不能直接处理——整数约束使问题在组合上变得困难且通常是非凸的。一种常见的方法是求解凸松弛(忽略整数约束)以获得下界,然后应用分支定界法或舍入。混合整数凸规划求解器结合了这些思想,但纯凸优化的全局最优性保证不再普遍适用。
相关方法
参考文献
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
ISBN:978-0-521-83378-3已复制。