凸优化

凸优化是研究在凸集上最小化凸函数的问题，这类问题具有局部最优解即全局最优解的特性，并且存在高效的算法。

Definition

凸优化问题是在凸不等式约束和仿射等式约束下最小化凸目标函数的问题；其可行集是凸的，这确保了任何局部最小值也是全局最小值。

Scope

本主题涵盖凸集和凸函数、凸问题的识别和建模、线性规划、二次规划、二阶锥规划和半定规划、凸问题的拉格朗日对偶和Karush-Kuhn-Tucker条件，以及内点法和一阶算法及其复杂性保证。

Core questions

• 如何识别或将问题重新表述为凸问题？
• 为什么凸性保证局部最优解是全局最优解？
• 对偶性揭示了凸问题及其解的哪些信息？
• 哪些算法能高效地解决凸问题，并提供哪些保证？

Key theories

凸问题的全局最优性

由于凸集上的凸函数没有伪局部最小值，任何局部最优解都是全局最优解，这使得凸问题能够可靠地求解。

拉格朗日对偶和KKT条件

每个凸问题都有一个相关的对偶问题，提供最优性证书，并且在约束资格条件下，Karush-Kuhn-Tucker条件是达到最优的必要和充分条件。

内点法

内点法沿着可行域内部的中心路径前进，可以在可证明的多项式时间内求解包括半定规划在内的凸问题。

Clinical relevance

凸优化在机器学习、信号和图像处理、控制、金融和工程设计中无处不在，因为许多估计和决策问题都可以转化为凸规划，并能可靠地大规模求解。

History

该领域建立在Rockafellar于1970年左右系统化的凸分析基础上。Karmarkar在1984年提出的内点法以及随后Nesterov和Nemirovski的理论表明，广泛的凸问题类别可以在多项式时间内求解，从而激发了现代以建模为导向的凸优化方法。

Key figures

• R. Tyrrell Rockafellar
• Stephen Boyd
• Yurii Nesterov
• Narendra Karmarkar

Seminal works

• boyd2004
• rockafellar1970

Frequently asked questions

为什么在可能的情况下优先选择凸模型？

凸问题保证所找到的任何解都是全局最优的，并且拥有成熟高效的算法。非凸模型可能会使求解器陷入次优的局部最优解，因此大量的应用工作都致力于将问题重新表述为凸问题。

线性规划是凸优化的一种吗？

是的。线性规划是在多面体上最小化线性目标函数，而线性函数和多面体都是凸的，因此线性规划是凸优化中一个特殊且被充分理解的案例。