Dimitris Bertsimas:基于现代优化视角的机器学习和统计

统计领域在历史上一直与概率论联系在一起。然而，分类、回归和估计的一些核心问题可以自然地写成优化问题。虽然连续优化方法对统计学有重大影响，但混合整数优化(MIO)发挥的作用非常有限，主要是因为相信MIO模型在计算上难以处理

1991年至2015年期间，a）混合整数优化（MIO）算法的进步，加上硬件的改进，使得解决MIO问题的速度提高了8000亿倍，b）我们建模和解决超高维鲁棒凸优化模型的能力有了显著提高。

在这次演讲中，我们演示了现代凸、鲁棒、特别是混合整数优化方法，当应用于各种经典机器学习(ML) /统计(S)问题时，可以为大规模实例带来可认证的最优解决方案，与ML/S中使用的启发式方法相比，这些实例的样本外准确率通常有显著提高。

具体来说，我们报告的结果

1)目前Lasso启发式地解决了回归中的经典变量选择问题。

2)我们表明，与ML/S中广泛持有的信念相比，Lasso成功的主要原因是鲁棒性而不是稀疏性。

3)基于MIO的线性和logistic回归模型的系统设计方法。

4) CART启发式算法求解的最优分类树。

5） 稳健分类包括稳健逻辑回归、稳健最优树和稳健支持向量机。

6)稀疏矩阵估计问题:主成分分析、因子分析和协方差矩阵估计。

在所有的例子中，我们证明大规模实例的最优解决方案(a)可以在几秒钟内找到，(b)可以在几分钟内证明是最优的，(c)优于经典方法。最重要的是，这一研究表明，将ML/S与现代优化相结合会带来重大进展。

次二次子模函数最小化*

子模函数最小化(SFM)是离散优化中的一个基本问题。最著名的SFM多项式时间算法是由来自focs2015的Lee, Sidford和Wong提出的，该算法进行\(O(n^2polylog M)\)查询，其中M是函数的最大绝对值。与此同时，据我们所知，由于Edmonds, SFM已知的最短(非确定性)证书进行\(O(n²)\)查询。目前还不知道\(n²\)是否是一个障碍，或者SFM可以在次二次多次查询中完成。

在这次演讲中，我们将看到两种对SFM的弛豫可以在次二次时间内完成。给出了整数子模函数的\(\tilde{O (nM^3)\)查询算法。此外，如果函数有界于[-1,1]，我们在\(O(n^{1.67}eps^{-2})\)-query算法中给出了eps-可加性近似。

与李殷达、亚伦·西德福、黄森锋合作。

Daniel Dadush：使Banaszczyk的边界对Komlos问题具有建设性

我们首先考虑了稀疏集系统中每个元素位于不超过t个集合的低差异着色问题。我们给出了一种有效的算法，它可以找到一个具有偏差的着色\(O(t log n)^{1/2})\)，从而匹配了Banaszczyk给出的最著名的非构造界。之前的算法只达到了一个\(O(t^{1/2} log n)\)界。结果也扩展到更一般的Komlos设置，其中每个向量的范数最多为1，并给出算法\(O(log^{1/2} n)\)界。

与Nikhil Bansal和Shashwat Garg的联合工作。

Jesús de Loera：关于线性优化的基础：两个最新进展

毫无疑问，线性规划（LP）及其相关多面体是数学优化理论和实践的核心（在离散优化中，LP用于实际计算，例如分支和定界，以及近似算法，例如舍入方案）。尽管这些问题非常重要，但许多关于LPs的简单易懂的数学问题仍然悬而未决。与此同时，大数据的新应用提出了我们需要推进的新算法问题。在本次演讲中，我将概述这一数学优化领域的两项最新贡献：

首先，是否存在一种运行多项式时间的单纯形法的开放问题激发了确定多面体直径的最坏情况上界这一众所周知的几何挑战。虽然已经取得了很大的进展，但今天即使是最初级的线性程序教科书，我们仍然不知道确切的直径上界是什么。我将提出最终证明网络流多面体图的直径满足Hirsch线性界的关键思想(与S. Borgwardt和E. Finhold联合工作)。

其次，受大数据分析挑战的激励，我将讨论用于解决(非常)大规模线性不等式系统的迭代投影算法(考虑不能完全在内存中读取系统或约束只能抽样)。我们推广了Agmon、Motzkin等人的松弛方法和随机Kaczmarz方法，并证明了这一新抽象具有吸引人的理论收敛结果。我们的计算实验表明，我们的算法优于原始的迭代方法(与J. Haddock和D. Needell联合工作)。

Santanu-Dey：用于包装和覆盖整数规划的基于聚合的剖切面

我们研究了包装和覆盖整数规划（IP）的Chvatal-Gomory（CG）割和更一般的聚合割的强度。聚合割的获得如下：给定IP公式，我们首先使用原始约束的聚合生成单个隐含不等式，然后获得由该单个不等式定义的具有可变边界的集的整数外壳，最后使用描述整数外壳的不等式作为割平面。我们的第一个主要结果是表明，对于包装和覆盖IP，CG和聚合闭包可以通过简单地为每个原始公式约束生成相应的闭包来进行2-近似，而不使用任何聚合。另一方面，我们使用计算实验证明，对于一般IP，聚合切割可以任意强于单个约束切割。最后，我们同时检验了基于k个不同聚合不等式的割集的强度，即所谓的多行割集，并证明了每一个具有大完整性间隙的包装或覆盖IP也有一个大的k-聚合闭包秩。特别是，该秩始终至少为完整性差的对数阶。

这是与Merve Bodur、Alberto Del Pia、Marco Molinaro和Sebastian Pokutta的联合工作

弗里茨Eisenbrand:稍后通知

Samuel Fiorini：单调电路背包覆盖不等式的小扩展公式

摘要背包覆盖不等式最初是针对最小背包问题而发展起来的，目前已被用于众多覆盖型组合优化问题的最优松弛问题。尽管它们的广泛使用，这些不等式产生指数大小的线性规划(LP)松弛，它不知道如何在多项式时间内精确优化。在本文中，我们解决了这个问题，并得到了拟多项式大小的LP松弛至少与背包覆盖不等式给出的松弛一样强。

对于最小背包覆盖问题，我们的主要结果可以正式表述如下：对于任何\（\varepsilon>0\），存在一个\（（1/\varepsilon）^{O（1）}n^{O（\log n）}）大小的LP松弛，其完整性间隙最多为\（2+\varepsilon\），其中\（n\）是项数。在这项工作之前，还没有已知的完整性间隙上具有恒定上界的次指数大小的松弛。

我们的构造灵感来自于通过Karchmer-Wigderson博弈将扩展公式与单调电路复杂性联系起来。特别是，我们的LP是基于\（O（\log^2 n）\）深度单调电路和扇入\（2\）来评估带有\（n\）输入的加权阈值函数，如Beimel和Weinreb构造的。我们相信，对这一联系的进一步理解可能会产生更积极的结果，补充最近证明的扩展公式的众多下限。

这是与Abbas Bazzi, Sangxia Huang和Ola Svensson (EPFL)的合作。

牛顿方法与次模多面体上的可分离凸极小化

我们给出了关于子模多面体的两个结果。我们首先给出了牛顿法求解子模多面体上任意（不一定非负）方向的线搜索问题的迭代次数的第一个强多项式界。这推广了Radzik对于线性分式组合优化的牛顿方法的结果。我们还提出了一个概念上简单的算法来最小化子模基多面体上的可分离凸函数。我们讨论了它的效率依赖于凸函数和子模函数的结构。

这是与斯瓦蒂·古普塔和帕特里克·贾利特的合作。

马丁·亨克:背包问题的预期Frobenius数和完整性差距

（基于与Iskander Aliev和Timm Oertel的联合工程）

在一系列论文中，V.I.Arnold发起了研究Frobenius数的平均大小的研究，2007年Bourgain&Sinai表明，“大”Frobenius数的概率是“可比小”。从那时起，Frobenius数的平均大小以及高维类似物都得到了深入的研究。我们将调查最近的发展，我们还将展示一个应用程序的完整性差距的预期大小的整数背包问题。

Jochen Könemann：低维公路图到有界树宽图的概率嵌入

[Abraham et al.，SODA 2010]中介绍了具有有界公路维度的图作为交通网络的模型。我们证明了任何这样的图都可以嵌入到具有任意小失真的有界树宽图的分布中。更具体地说，如果G的公路维度是常数，我们将展示如何随机计算输入图G的最短路径度量的子图，该子图具有以下两个属性：它将G的距离扭曲了1+\eps的因子，并且具有在G的纵横比中为多段对数的树宽。特别是，这一结果意味着拟多项式时间近似方案适用于交通网络中自然出现的许多优化问题，包括旅行商、Steiner树、k-中值和设施位置。

与A.E.Feldmann、I.Fung和I.Post的联合工作

Matthias Köppe:面向切割平面定理的计算机辅助发现和自动证明

受20世纪80年代多面体组合优化方法突破的启发，几代研究人员研究了凸包的面结构，以开发出强大的切割面。我们问这个过程有多少是自动化的：特别是，我们能用算法来发现和证明关于切割平面的定理吗？我们关注一般整数和混合整数规划，而不是组合优化，并使用切割生成函数框架（Conforti等人，2013）。

我们的做法是务实的。我们的定理和证明来自于元编程技巧，应用于对Gomory-Johnson(1972)模型中切割生成函数的basu - hildebrandt - koeppe(2014)极值检验的无网格实现;接着是用半代数胞形进行的实际计算。我们证明的正确性取决于底层实现的正确性。

我们报告我们的软件的早期成功。我们对文献中的各种定理进行了验证，对已发表的若干定理进行了修正，并发现了新的割母函数族及其相应定理的自动证明。我们的计划是大量地提出这样的新定理。

与周元(加州大学戴维斯分校)合作。

Daniel Kuhn：两阶段鲁棒二进制规划中的K-适应性

在过去的二十年中，稳健优化已经成为一种计算上有吸引力的方法，用来描述和解决受不确定性影响的单阶段决策问题。近年来，鲁棒优化已成功地应用于具有连续追索权的多阶段问题。本文进一步将鲁棒优化方法扩展到具有整数追索权的问题，这类问题迄今为止存在很大的求解阻力。为此，我们通过相应的K-适应性问题来逼近两阶段鲁棒二进制程序，其中决策者此时此刻预先提交K个第二阶段策略，一旦观察到不确定参数，就会实现这些策略的最优。我们研究了k -适应性问题的逼近质量和计算复杂度，提出了两个可以用现成软件求解的混合整数线性规划的重新公式。我们演示了我们对供应链设计、路线规划和资本预算问题的程式化实例的改进的有效性。

Jon Lee：通过体积比较多面体松弛

我们考虑使用体积作为比较松弛的一种手段，在可分解公式的全局优化的空间分支定界算法的背景下。我们比较了一系列的三重产品松弛的选择，并获得了在其中选择的指导。我们还获得了制定分支决策的指导，并将其与软件实践进行了比较。最后，我们着眼于旨在验证我们的理论结果的实际意义的计算实验。

Neil Olver：一种快速简单的广义流最大化强多项式算法

在过去的几十年里，人们对最大流量问题进行了深入的研究。直到最近Végh才获得了一个强多项式时间算法。我们给出了一个新的强多项式算法，它比Végh的算法更快，也明显地简单。在许多情况下，它甚至比Radzik的最佳弱多项式算法略快。我们还演示了我们的结果在项目调度中的经典净现值问题中的一个重要应用。

(与J. Correa、A. Schulz和L. Végh合作)

Shmuel Onn:移位组合优化

我将介绍任意集合上的组合优化的广泛扩展，即集合上的移位组合优化。我将描述一些关于这个问题复杂性的积极结果，并希望这次演讲将刺激对这个巨大的开放的新领域的研究。

我将以在多种商品流动的复杂性方面取得的进展作为总结。

R. Ravi:平面流言:近似于在平面图表中传播的谣言

我们研究了多商品组播调度的设计，这是一组源-目的对之间的有效点对点通信问题。在这个问题中，我们给出了一个无向图和一个源-目标对的集合，目标是安排一个最小长度的匹配序列，将每个源与其各自的目标连接起来。多商品组播模型模拟了网络中的一个经典信息传播问题，其中主要的通信约束是给定节点所能建立的连接数，而不是链路带宽。多种商品多播及其特殊情况,广播和多播,都是np完备性和最佳逼近已知因素\ (2 ^ {\ widetilde {O} \√{\ log n})} \), \ (O (\ log n / \ log \ log n) \),和\ (O (\ log k / \ log日志k) \ \),分别在\ (n \)是节点的数量和\ (k \)的终端数量多播实例。

多商品组播问题与寻找具有最优平衡的子图问题密切相关，其中平衡定义为子图的最大度与子图中任意源-目的对之间的最大距离之和。我们首先证明，对于组播问题的任何实例，在有k个源-目的对的\(n\)节点图中，最小平衡子图相对于LP的自然松弛值可以近似为\(O(\log k\ log n)\)。利用这个完整性间隙上界，我们得到了平面图多商品组播的一个\(O(\log^ 2k \log^ 2n)\)近似。

与Jennifer Iglesias（CMU）、Rajmohan Rajaraman（东北部）和Ravi Sundaram（东北部）的联合工作

托马斯Rothvoß:稍后通知

András Sebő: The Salesman’s Matroid intersection

关于旅行商问题或其变体的各种最新结果（对于与Jens Vygen联合工作中的图度量，对于与Anke van Zuylen联合工作中的路径，对于Singh和Zenklusen工作中的k-轨迹，或者对于JenőLehel的哈密顿循环可行性问题的超图推广）Edmonds的拟阵交或分划定理有助于使用。

拟阵是这些问题中固有的吗？其表面上独立的事件是否与事实相关？它们的出现有共同的原因吗？

我们无法回答这些问题，但可以展示一些推销员在连通性、奇偶性和拟阵交叉道路上的旅行经历。我们展示了上述问题的一些共同特征，以及它们导致的一些开放性问题。

布鲁斯·谢泼德:《树、流和簇》

合著者：阿德里安·维塔（麦吉尔）、戈登·威尔丰（贝尔实验室）

树型结构一直出现在组合优化的模型和算法中。毫不奇怪，针对这些问题有一个开发良好的相关工具包。也许令人惊讶的是，当流必须在一棵树上路由时，网络中的流的经典模型(又名Max-flow Min-cut)承认了几个自然的开放问题:所谓的合流。我们讨论了其中一个问题的解决方案，并解释了与IP路由、根集群和稳定匹配的连接。

Mohit-Singh：划分约束下的行列式最大化

摘要给出了列和行由集合U作索引的正半定矩阵L，研究了如何选择满足一定组合约束条件的集合B，使L的子矩阵受限于B的行和列的行列式最大。这个问题出现在不同的领域，包括机器学习中的确定性点过程、实验设计、地理布局问题、差异理论和凸几何。我们的主要结果是当组合约束由划分矩阵给出，并且r表示矩阵的秩时，给出exp(r)近似。

我们的方法首先给出一个多项式优化问题作为最大行列式问题的松弛。为了分析一种自然的随机取整算法，我们求助于双曲多项式理论及其在逼近非负矩阵的永久值方面的作用。

与萨索·尼科洛夫合作。

Ola Svensson:稍后通知

Rekha-Thomas：k-子集超立方体上的对称平方和

超立方体上的多项式优化在组合优化中有着重要的应用。我们发展了一种对称约化方法，该方法在k-子集超立方体上找到非负对称多项式的平方和证书，改进了Gatermann和Parrilo的技术。对于每个具有固定阶sos表达式的对称多项式，我们的方法找到一个简洁的sos表达式，其大小仅取决于阶，而不取决于变量的数量。我们的结果自然与Razborov的flag代数演算有关，用于解决极值组合数学中的问题。这导致了新的结果，涉及到标志及其在有限环境中查找sos证书的能力，这是一个以前从未探索过的角度。

与安妮·雷蒙德，詹姆斯·桑德森和莫希特·辛格合作。

Nisheeth-Vishnoi：稀疏恢复、迭代加权最小二乘法及其他

Jens Vygen:旅行推销员的近似算法

在s-t路径TSP中，我们给出了一个包含两个元素s和t的有限度量空间，要求从s到t访问所有元素的最短路径。自然LP松弛被推测具有3/2的完整性比。

对于图表实例，比例确实是3/2(即使是t -tour，与András Sebő联合工作)。我们的证明使用了Rado定理和两种“耳感应”。在这里我将建议一种新的，通常更强的耳朵感应。

高志涵(Zhihan Gao)对图的3/2比给出了一个更简单的证明，他将LP解写成生成树的凸组合，而这些生成树很多都被称为“高树”。我将展示为什么这适用于s-t-tour，而不适用于一般的t-tour(与Corinna Gottschalk合作)。