魔王编辑

328页,ACM Fellow、耶鲁CS教授凸优化算法书籍开放下载了

耶鲁大学计算机科学教授 Nisheeth Vishnoi 撰写专著《Algorithms for Convex Optimization》,全面介绍凸优化算法。

凸优化是数学最优化的子领域之一,研究定义于凸集中的凸函数最小化问题。凸性常用于为多类凸规划提出高效算法。因此,凸优化广泛地影响了多个科学和工程学科。


近年来,凸优化算法革新了离散和连续优化问题的算法设计。对于图论中的最大流问题、二分图最大匹配问题和次模函数最小化等问题,最快速的知名算法都使用了凸优化,如梯度下降、镜像下降、内点法和切割平面法。

令人惊讶的是,凸优化算法还用于设计针对离散对象(如拟阵)的计数问题。同时,凸优化算法成为许多现代机器学习应用的核心。更大规模和愈加复杂的输入实例促进了对凸优化算法的需求,同时也极大地推动了凸优化本身的发展。

近日,耶鲁大学计算机科学教授 Nisheeth Vishnoi 撰写专著《Algorithms for Convex Optimization》,目前该书的预发布版本可供个人免费阅读和下载。


书籍地址:https://convex-optimization.github.io/ACO-v1.pdf

这本书旨在让读者深入理解凸优化算法,着重于从基本原理推导凸优化核心算法,并建立精确的运行时间界限。由于凸优化方法应用广泛,无法在一本书中得到全部展示,本书重点介绍了针对多种离散优化和计数问题的快速算法应用。

这本书的目标读者包括高年级本科生、研究生,以及来自理论计算机科学、离散优化和机器学习领域的研究者。

章节目录

这本书大致分为四部分:

  • 第 3、4、5 章简要介绍了凸性、凸优化中的计算模型和效率、对偶性;

  • 第 6、7、8 章介绍了一阶方法,如梯度下降、镜像下降和乘性权重更新方法,以及加速梯度下降

  • 第 9、10、11 章展示了牛顿法和多种适用于线性规划的内点法;

  • 第 12、13 章介绍了切割平面法,如适用于线性规划凸优化的椭球法。


本书的章节目录如下:

作者简介

本书作者 Nisheeth Vishnoi 是耶鲁大学计算机科学教授、Computation and Society Initiative 联合发起人。他的研究重点是计算机科学的基础问题、机器学习和优化问题。同时,他对从计算角度理解和解决自然和社会核心问题也有广泛的兴趣,主要关注点是自然算法、智能的产生,以及算法公平性。

他曾获 2005 年 IEEE FOCS 最佳论文奖、2006 年 IBM Research Pat Goldberg Memorial Award、2011 年印度国家科学院青年科学家奖、2016 年印度理工学院孟买分校年轻校友成就奖以及 2019 年 ACM FAT* 最佳技术论文奖多个奖项。

2019 年,他入选 ACM Fellow。

个人主页:https://www.cs.yale.edu/homes/vishnoi/Home.html

入门耶鲁大学凸优化
相关数据
IBM机构

是美国一家跨国科技公司及咨询公司,总部位于纽约州阿蒙克市。IBM主要客户是政府和企业。IBM生产并销售计算机硬件及软件,并且为系统架构和网络托管提供咨询服务。截止2013年,IBM已在全球拥有12个研究实验室和大量的软件开发基地。IBM虽然是一家商业公司,但在材料、化学、物理等科学领域却也有很高的成就,利用这些学术研究为基础,发明很多产品。比较有名的IBM发明的产品包括硬盘、自动柜员机、通用产品代码、SQL、关系数据库管理系统、DRAM及沃森。

https://www.ibm.com/us-en/
相关技术
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

凸优化技术

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

规划技术

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

线性规划技术

在数学中,线性规划(Linear Programming,简称LP)特指目标函数和约束条件皆为线性的最优化问题。

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

图论技术

图论是以“图”为研究对象的一个数学分支,是组合数学和离散数学的重要组成部分。图是用来对对象之间的成对关系建模的数学结构,由“顶点”(又称“节点”或“点”)以及连接这些顶点的“边”(又称“弧”或“线”)组成。值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。

推荐文章
暂无评论
暂无评论~