optimization、operation research等方向的科研中，你读过哪些惊艳的论文？

欧陆资讯 | 2024-04-15 11:59

RT 谢谢

All papers by Nesterov alone.

SVRG & SPIDER

SVRG精炼的结构和证明的将随机梯度的复杂度从 $O(n \\epsilon^{-2})$ 下降到了 $O(n^{2/3}\\epsilon^{-2})$ , SPIDER 精炼的结构和证明的将随机梯度的复杂度下降到了 $O(n^{1/2}\\epsilon^{-2})$ 。惊艳之处在于没有复杂的证明，却有惊喜的结果。

SVRG: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, 2013, R. Johnson, T. Zhang.

SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator, 2018， C. Fang, C. Li, Z. Lin, T. Zhang.

Alexandre Jacquillat&Amedeo R. Odoni

用扎实的数理基础解决传统问题，非常深刻

国内找不到

A. Jacquillat and A. Odoni,"An Integrated Scheduling and Operations Approach to Airport Congestion Mitigation," Operations Research, 63(6): 1390-1410, 2015.

A. Jacquillat and V. Vaze, “Inter-Airline Equity and Airline Collaboration in Airport Scheduling Interventions”, Transportation Science, 52(4): 941–964, 2018.

Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging[J]. Journal of mathematical imaging and vision, 2011, 40(1): 120-145.

还有最近看的一个，虽然关注的人不多：

Sabach S, Shtern S. A first order method for solving convex bilevel optimization problems[J]. SIAM Journal on Optimization, 2017, 27(2): 640-660.

巧妙的把双层优化问题和不动点联系到了一起。

更新几个：

Becker S R, Candès E J, Grant M C. Templates for convex cone problems with applications to sparse signal recovery[J]. Mathematical Programming Computation, 2011, 3(3): 165.

简单方法做出牛逼工作的代表，这篇文章没有很复杂的数学推导，但是绝对能让你对锥规划的认识上升好几个层次。

Becker S, Bobin J, Candès E J. NESTA: A fast and accurate first-order method for sparse recovery[J]. SIAM Journal on Imaging Sciences, 2011, 4(1): 1-39.

这篇文章让你明白怎么样合理的套用别人的方法，然后做出顶级工作。

Chandrasekaran V, Recht B, Parrilo P A, et al. The convex geometry of linear inverse problems[J]. Foundations of Computational Mathematics, 2012, 12(6): 805-849.

严格来说，这篇文章不属于优化领域，但是又跟优化关系紧密。这篇文章已经不止是惊艳了，简直是惊呆了。现在很多做recovery bound的工作都是以这篇文章为起点的。

Wen Z, Yin W. A feasible method for optimization with orthogonality constraints[J]. Mathematical Programming, 2013, 142(1-2): 397-434.

北大文再文老师的文章，这篇文章指出，如果你的feasible set是stiefel manifold（满足(X^T)X=I的X集合，X可以是矩阵也可以是向量，一个特殊的例子就是球面，(x^T)x=1），你其实可以一直贴着球面，在球面上search，而不需要像其他的梯度投影之类的算法一样每次都跳出去，然后又投影回球面。。

美国李海大学2002年

列出了一个整数规划、组合优化领域的经典paper list

堪称经典中的经典了

（感谢 @运筹OR帷幄优化版块责编群推荐）

这里就放我硕士博士阶段俩位师爷和俩个老板的几篇

M. Gr?tschel, L. Lovász, and A. Schrijver, The Ellipsoid Method and its Consequences in Combinatorial Optimization, Combinatorica 1 (1981), 169.
M. Gr?tschel, L. Lovász, and A. Schrijver, Corrigendum to our Paper "The Ellipsoid Method and its Consequences in Combinatorial Optimization", Combinatorica 4 (1984), 291.
M. Gr?tschel and W. Padberg, Partial Linear Characterizations of the Asymmetric Travelling Salesman Polytope, Mathematical Programming 8 (1975), 378.
M. Jünger, G. Reinelt, and S. Thienel,Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science20(1995), 111.
H. Sherali and W. Adams,A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems, SIAM Journal on Discrete Mathematics3(1990), 411.