凸优化算法(Algorithms for Convex Optimization)

2024-04-29 05:29:31

Nisheeth K. Vishnoi 是 A. Bartlett Giamatti 计算机科学教授，也是耶鲁大学计算与社会计划的联合创始人。他的研究重点是计算机科学、机器学习和优化中的基础问题。他还对从计算的角度理解和解决自然和社会中出现的一些关键问题感兴趣。在这里，他目前的重点是自然算法、智能的出现以及算法决策的公平性。

他是 2005 年 IEEE FOCS 最佳论文奖、2006 年 IBM Research Pat Goldberg 纪念奖、2011 年印度国家科学院青年科学家奖、2016 年印度理工学院孟买青年校友成就奖和最佳技术奖的获得者。 2019 年 ACM FAT论文奖。他是 ACM 的 Fellow。

1995-1999 年在印度孟买理工学院获得计算机科学与工程技术学士学位，1999-2004 年在佐治亚理工学院获得算法、组合和优化博士学位。

凸优化研究在凸集上最小化凸函数的问题。凸性及其众多含义已被用于为许多类别的凸程序提供有效的算法。因此，凸优化已经广泛影响了科学和工程的多个学科。

在过去的几年中，凸优化算法已经彻底改变了算法设计，无论是离散优化问题还是连续优化问题。对于诸如图中最大流、二部图中最大匹配和子模函数最小化等问题的已知最快算法，涉及对凸优化算法的基本和非平凡使用，例如梯度下降、镜像下降、内点方法和切割平面方法。令人惊讶的是，凸优化算法也已用于设计离散对象（如拟阵）的计数问题。同时，凸优化算法已成为许多现代机器学习应用的核心。在更大和越来越复杂的输入实例的驱动下，对凸优化算法的需求，

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

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

我们介绍了连续优化和离散优化之间的相互作用。激励性的例子是最大流问题。我们还追溯了线性规划的历史——从椭球法到现代内点法。我们以椭圆体方法最近在一般凸规划问题（如最大熵问题）上取得的一些成功作为结尾。

我们回顾了本书所需的数学预备知识。其中包括来自多元微积分、线性代数、几何、拓扑、动力系统和图论的一些标准概念和事实。

我们介绍了凸集、凸性的概念，并展示了伴随凸性而来的力量：凸集具有分离的超平面，存在次梯度，凸函数的局部最优解是全局最优的。

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

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

我们首先介绍梯度下降方法，并展示如何将其视为最速下降。随后，我们证明了当函数的梯度是 Lipschitz 连续时梯度下降法的收敛时间界限。最后，我们使用梯度下降法为离散优化问题提出了一种快速算法：计算无向图中的最大流量。

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

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

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

我们以牛顿法及其收敛性为基础，推导出用于线性规划的多项式时间算法。该算法的关键是使用屏障函数和相应的中心路径的概念从约束优化到无约束优化。

对于线性规划的情况，我们提出了 IPM 之后路径的各种概括和扩展。作为一个应用，我们推导出了 st 最小成本流问题的快速算法。随后，我们介绍了自相关的概念，并概述了多面体和更一般的凸集的障碍函数。

我们介绍了一类用于凸优化的切割平面方法，并对一个特殊情况进行了分析，即椭球方法。然后，我们将展示当我们只能访问多胞体的分离预言机时，如何使用这种椭球方法来解决 0-1 多胞体上的线性规划。

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

下载

以[pdf 格式]下载整本书的旧版本。请注意，此版本有几个错别字已在印刷版中更正。

版权

该材料将由剑桥大学出版社作为 Nisheeth K. Vishnoi 的 Algorithms for Convex Optimization 出版。此预出版版本仅供个人免费查看和下载。不得再分发、转售或用于衍生作品。? Nisheeth K. Vishnoi 2020。

[Lx=b]

通过近似理论更快的算法

【返回列表】