15.099 优化理论文献前沿研讨

MIT Course 15 · Operations Research/Statistics · 课号 15.099

TL;DR

• 精读优化领域近现代经典与里程碑文献，研讨凸优化、非凸优化与锥优化的前沿突破。
• 内斯捷罗夫加速梯度法（Nesterov accelerated gradient）与一阶算法理论复杂度下界推导。
• 大规模分布式优化（ADMM）在数据驱动与分布式机器学习系统中的收敛性证明与应用。

课程简介 / Description

In keeping with the tradition of the last twenty-some years, the Readings in Optimization seminar will focus on an advanced topic of interest to a portion of the MIT optimization community: randomized methods for deterministic optimization. In contrast to conventional optimization algorithms whose iterates are computed and analyzed deterministically, randomized methods rely on stochastic processes and random number/vector generation as part of the algorithm and/or its analysis. In the seminar, we will study some very recent papers on this topic, many by MIT faculty, as well as some older papers from the existing literature that are only now receiving attention.

讲义 / Lecture Notes

• 1
  • _MAXCUT; Semidefinite Programming; and the Goemans-Williamson Paper, "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming."
  • _
  • Presentation courtesy of Rob Freund (
  • PDF
  • ). This is a summary presentation based on: Goemans, Michel X., and David P. Williamson. "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming."
  • Journal of the ACM
  • 42, no. 6 (November 1995): 1115-45.
• 2
  • _Dunagan and Vempala Paper, "Simple Polynomial-Time Rescaling Algorithm for Solving Linear Programs."
  • _
  • Dunagan, John, and Santosh Vempala. "A Simple Polynomial-Time Rescaling Algorithm for Solving Linear Programs." In Proceedings of the 36th Annual Association for Computing Machinery Symposium on Theory of Computing. New York, NY: ACM Press, 2004.
  • Storn and Price Paper, "Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces."
  • Presentation courtesy of David Craft. Used with permission (
  • PDF
  • ). This is a summary presentation based on: Storn, Rainer, and Kenneth Price. "Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces."
  • Journal of Global Optimization
  • 11 (1997): 341-59.
• 3
  • Clarkson Paper, "Las Vegas Algorithms for Linear and Integer Programming When the Dimension Is Small."
  • Presentation courtesy of Susan Martonosi. Used with permission (
  • PDF
  • ). This is a summary presentation based on: Clarkson, Kenneth L. "Las Vegas Algorithms for Linear and Integer Programming When the Dimension Is Small."
  • Journal of the ACM
  • 42, no. 2 (March 1995): 488-99.
  • _Motwani and Raghavan, Chapter 9 in Randomized Algorithms.
  • _
  • Presentation courtesy of Jan De Mot. Used with permission (
  • PDF
  • ). This is a summary presentation based on:
  • Motwani, Rajeev, and Prabhakar Raghavan. Chapter 9 in
  • Randomized Algorithms
  • . Cambridge, UK: Cambridge University Press, 1995. ISBN: 0-521-47465-5.
• 4
  • _Kalai Paper #1, "A Subexponential Randomized Simplex Algorithm."
  • Kalai Paper #2, "Linear Programming, the Simplex Algorithm and Simple Polytopes."_
  • Both presentations courtesy of Dan Stratila. Used with permission (
  • PDF
  • ). This is a summary presentation based on two papers: Kalai, Gil. "A Subexponential Randomized Simplex Algorithm (Extended Abstract)." In Proceedings of the 24th Annual Association for Computing Machinery Symposium on Theory of Computing. New York, NY: ACM Press, 1992. and,
  • Kalai, Gil. "Linear Programming, the Simplex Algorithm and Simple Polytopes." Jerusalem, Israel: Hebrew University of Jerusalem, May 1997.
• 5
  • Solis and Wets Paper, "Minimization by Random Search Techniques."
  • Presentation courtesy of Michele Aghassi. Used with permission (
  • PDF
  • ). This is a summary presentation based on: Solis, F. J., and R. J-B. Wets. "Minimization by Random Search Techniques."
  • Mathematical Operations Research
  • 6 (1981): 19-30.
  • Romeijn Thesis Book, "Global Optimization by Random Walk Sampling Methods."
• 6
  • Zabinsky and Smith Paper, "Pure Adaptive Search in Global Optimization."
  • Presentation courtesy of Michael Yee. Used with permission (
  • PDF
  • ). This is a summary presentation based on: Zabinsky, Zelda B., and Robert L. Smith. "Pure Adaptive Search in Global Optimization."
  • Mathematical Programming
  • 55 (1992): 323-38.
  • Presentation courtesy of Michael Yee and Kwong-Meng Teo. Used with permission (
  • PDF
  • ). This is a summary presentation based on: Zabinsky, Zelda B., and Robert L. Smith. "Pure Adaptive Search in Global Optimization."
  • Mathematical Programming
  • 55 (1992): 323-38.
• 7
  • Simonovits Paper, "How to Compute the Volume in High Dimension?"
• 8
  • Romeijn and Smith Paper, "Simulated Annealing for Constrained Global Optimization."
• 9
  • _Bertsimas and Vempala Paper, "Solving Convex Programs by Random Walks."
  • Zabinsky, Smith, etc. Paper, "Improving Hit-and-Run for Global Optimization."_
• 10
  • _Zabinsky, Graesser, etc. Paper, "Global Optimization of Composite Laminates Using Improving Hit and Run."
  • Sanjeev Paper, "Approximation Schemes for NP-hard Geometric Optimization Problems: A Survey."_

本资料整理自 MIT OpenCourseWare，遵循 Creative Commons BY-NC-SA 4.0 许可协议，仅供个人学习使用。