【斯坦福大学博士论文】凸优化和图算法的新基元，404页pdf

迭代方法，尤其是凸优化方法，构成了许多现代算法的基础。这类方法的成功依赖于它们的通用性:像梯度下降法和牛顿法这样的方法通常只需要对目标进行最小的假设就能收敛到高质量的最小化。然而，在许多现实环境中，这些算法所获得的理论保证在实践中往往是不够的。本文通过开发凸优化方法和利用问题特定结构的图算法来解决这个问题。

https://searchworks.stanford.edu/view/14239649

第一部分给出了求解拉普拉斯线性系统的最先进算法，以及求解最小成本流的更快算法。我们的结果是通过新颖的组合经典迭代方法，从凸优化与基于图的数据结构和预调节器。第二部分给出了若干类结构凸优化问题的新算法。给出了凸函数极小化的近似最优方法，包括球优化oracle和N个凸函数的最大值极小化，以及投影极小化和复合凸极小化的新算法。我们的结果是通过对经典加速梯度方法的更精细的理解实现的，并为各种重要的机器学习任务，如逻辑回归和硬边界支持向量机提供了新的算法。第三部分讨论了离散最优传输问题算法的进展，这是一个近年来由于深度学习的新应用而引起极大兴趣的任务。我们给出了简单的并行算法来逼近离散最优传输，并进一步证明了这些算法可以在空间界和流设置中实现。通过进一步利用我们的机制，我们还对半流模型中的图优化问题(如二部匹配和转运)给出了改进的复杂度边界。