【耶鲁2020新书】凸优化算法, 328页pdf

凸优化研究在凸集上最小化凸函数的问题。凸性，连同它的许多含义，已经被用来为许多类凸程序提出有效的算法。因此，凸优化已经广泛地影响了科学和工程的几个学科。

过去几年，凸优化算法彻底改变了离散和连续优化问题的算法设计。对于图的最大流、二部图的最大匹配和子模函数最小化等问题，已知的最快算法涉及到对凸优化算法的基本和重要使用，如梯度下降、镜像下降、内点方法和切割平面方法。令人惊讶的是，凸优化算法也被用于设计离散对象(如拟阵)的计数问题。同时，凸优化算法已经成为许多现代机器学习应用的中心。由于输入实例越来越大、越来越复杂，对凸优化算法的需求也极大地推动了凸优化技术本身的发展。

这本书的目的是使读者能够获得对凸优化算法的深入理解。重点是从第一性原理推导出凸优化的关键算法，并根据输入长度建立精确的运行时间界限。由于这些方法的广泛适用性，一本书不可能向所有人展示这些方法的应用。这本书展示了各种离散优化和计数问题的快速算法的应用。本书中所选的应用程序的目的是为了说明连续优化和离散优化之间的一个相当令人惊讶的桥梁。

目标受众包括高级本科生、研究生和理论计算机科学、离散优化和机器学习方面的研究人员。

https://convex-optimization.github.io/

第一章-连续优化和离散优化的衔接

我们提出了连续优化和离散优化之间的相互作用。最大流问题是一个激励人心的例子。我们也追溯了线性规划的历史——从椭球法到现代内点法。最后介绍了椭球法在求解最大熵问题等一般凸规划问题上的一些最新成果。

第二章 预备知识

我们复习这本书所需的数学基础知识。这些内容包括多元微积分、线性代数、几何、拓扑、动力系统和图论中的一些标准概念和事实。

第三章-凸性

我们引入凸集，凸性的概念，并展示了伴随凸性而来的能力:凸集具有分离超平面，子梯度存在，凸函数的局部最优解是全局最优解。

第四章-凸优化与效率

我们提出了凸优化的概念，并正式讨论了它意味着什么，有效地解决一个凸程序作为一个函数的表示长度的输入和期望的精度。

第五章-对偶性与最优性

我们引入拉格朗日对偶性的概念，并证明在一个称为Slater条件的温和条件下，强拉格朗日对偶性是成立的。随后，我们介绍了拉格朗日对偶和优化方法中经常出现的Legendre-Fenchel对偶。最后，给出了Kahn-Karush-Tucker(KKT)最优性条件及其与强对偶性的关系。

第六章-梯度下降

我们首先介绍梯度下降法，并说明如何将其视为最陡下降。然后，我们证明了梯度下降法在函数的梯度是连续的情况下具有收敛时间界。最后，我们使用梯度下降法提出了一个快速算法的离散优化问题:计算最大流量无向图。

第七章-镜像下降和乘法权值更新

我们推出我们的凸优化的第二个算法-称为镜面下降法-通过正则化观点。首先，提出了基于概率单纯形的凸函数优化算法。随后，我们展示了如何推广它，重要的是，从它推导出乘法权值更新(MWU)方法。然后利用后一种算法开发了一个快速的近似算法来解决图上的二部图匹配问题。

第八章-加速梯度下降

提出了Nesterov的加速梯度下降算法。该算法可以看作是前面介绍的梯度下降法和镜像下降法的混合。我们还提出了一个应用加速梯度法求解线性方程组。

第九章-牛顿法

IWe开始了设计凸优化算法的旅程，其迭代次数与误差成对数关系。作为第一步，我们推导并分析了经典的牛顿方法，这是一个二阶方法的例子。我们认为牛顿方法可以被看作是黎曼流形上的最速下降，然后对其收敛性进行仿射不变分析。

第十章 线性规划的内点法

利用牛顿法及其收敛性，推导出一个线性规划的多项式时间算法。该算法的关键是利用障碍函数的概念和相应的中心路径，将有约束优化问题简化为无约束优化问题。

第十一章-内点法的变种与自洽

给出了线性规划中路径遵循IPM的各种推广。作为应用，我们推导了求解s-t最小代价流问题的快速算法。随后，我们引入了自一致性的概念，并给出了多边形和更一般凸集的障碍函数的概述。

第十二章 线性规划的椭球法

介绍了凸优化的一类切割平面方法，并分析了一种特殊情况，即椭球体法。然后，我们展示了如何使用这个椭球方法来解决线性程序超过0-1多边形时，我们只能访问一个分离oracle的多边形。

第十三章-凸优化的椭球法

我们展示了如何适应椭球法求解一般凸程序。作为应用，我们提出了子模函数最小化的多项式时间算法和计算组合多边形上的最大熵分布的多项式时间算法。