【伯克利博士论文】最优化无所不在-凸优化、组合优化与经济学（附256页全文下载）

【导读】作者Sam Wong是伯克利 the Theory group的研究生，近期公开发布了他的博士论文，该论文系统性的论述了优化问题广泛的应用价值，并提出了自己的新式算法，非常有学习价值，特此编译如下。

介绍：

在过去的一个世纪里，最优化已经成为了数学的重要分支，它与工程、自然和社会科学息息相关。作为重要的组成部分，从航空公司的调度到互联网商务，众多应用场景中均隐藏着最优化的影子，随着基础理论的发展，它将持续在多个领域发挥作用。由于现代社会，对于效率的要求要比以往任何时候都要高，因此对优化问题的持续研究至关重要。我们设想在未来，优化技术将无处不在，在本文中，我们研究了优化中的各种基本问题，组合与连续，并开发了新的可被证明的算法。

在本文中，我们研究了最优化与其应用场景中出现的基本问题，我们的方法中借鉴了凸优化和组合优化理论，以及一些经济学中的工具包实现。通过这些学科技术的交叉运用，我们在多个新旧问题上取得了进展。

请关注专知公众号（扫一扫最下面专知二维码，或者点击上方蓝色专知）

• 后台回复“BKSW” 就可以获取本文的下载链接~ 

本文大纲：

• 介绍

• 基本概念与问题

• 一种更快的平面切割方法（Cutting Plane Method）

• 凸面最小化和交叉点切割平面法的问题

• 基于平面切割法的次模函数最小化（Submodular Function Minimization via Cutting Plane Method）

• 计算瓦尔拉斯均衡（Walrasian Equilibria）：快速算法和结构属性
  

• 基于一阶方法的次模函数最小化

• Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

• s-t有效网络抵抗性设计

-END-

专 · 知

   专知开课啦!《深度学习: 算法到实战》, 中科院博士为你讲授！

请加专知小助手微信（扫一扫如下二维码添加），加入专知主题群, 咨询《深度学习:算法到实战》等~

欢迎微信扫一扫加入专知人工智能知识星球群，获取专业知识教程视频资料和与专家交流咨询！

请PC登录www.zhuanzhi.ai或者点击阅读原文，注册登录专知，获取更多AI知识资料！

点击“阅读原文”，了解报名专知《深度学习:算法到实战》课程