2024 ICS Prize Winners
The 2024 INFORMS Computing Society Prize is awarded to Krishnakumar Balasubramanian (UC Davis), Shixiang Chen (University of Science and Technology of China), Jiaxiang Li (University of Minnesota), Shiqian Ma (Rice University), Anthony Man-Cho So (Chinese University of Hong Kong), and Tong Zhang (University of Illinois Urbana-Champaign) for their path-breaking work in Riemannian optimization published in
- Shixiang Chen, Shiqian Ma, Anthony Man-Cho So, and Tong Zhang. Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold. SIAM Journal on Optimization, 30 (1): 210-239, 2020.
- Shixiang Chen, Shiqian Ma, Anthony Man-Cho So, and Tong Zhang. Nonsmooth Optimization over the Stiefel Manifold and Beyond: Proximal Gradient Method and Recent Variants. SIAM Review, 66 (2): 319-352, 2024.
- Jiaxiang Li, Krishnakumar Balasubramanian, and Shiqian Ma. Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization. Mathematics of Operations Research, 48(2): 1183-1211, 2022.
Riemannian optimization involves minimizing a function over a Riemannian manifold by leveraging its geometry. Traditionally used for smooth objective functions, the awarded body of work has extended its applicability to nonsmooth objectives. Key contributions include the manifold proximal gradient method (ManPG), which efficiently minimizes nonsmooth functions on the Stiefel manifold and significantly improves iteration complexity. Another breakthrough is the development of zeroth-order algorithms that operate without gradient information, resulting in the first provably convergent method using Gaussian smoothing, whose iteration complexity depends only on the manifold's dimension, not that of the ambient space. The theoretical and algorithmic innovations demonstrate superior speed and accuracy against benchmarks and have proven valuable in practical applications such as sparse PCA, orthogonal dictionary learning, and robotics. This body of work encompasses a collection of theoretical insights, rigorous analysis, robust empirical tests, and relevant practical applications, collectively representing a significant contribution to nonsmooth optimization.
The 2024 ICS Prize Committee members are:
Simge Kucukyavuz, Chair (Northwestern University)
George Lan (Georgia Tech)
Nick Sahinidis (Georgia Tech and The Optimization Firm)
Juan Pablo Vielma (Google Research)
2023 ICS Prize Winners
The 2023 INFORMS Computing Society prize is awarded to Alberto del Pia and Aida Khajavirad for their path-breaking research on convexification of mixed-integer polynomial optimization problems, as detailed in the papers:
- A. Del Pia and A. Khajavirad, "A polyhedral study of binary polynomial programs", Mathematics of Operations Research, 42(2) 389‐410, 2017.
- A. Del Pia and A. Khajavirad, "On decomposability of multilinear sets", Mathematical Programming, 170(2) 387‐415, 2018.
- A. Del Pia and A. Khajavirad, "The multilinear polytope for acyclic hypergraphs", SIAM Journal on Optimization, 28(2) 1049–1076, 2018.
- A. Del Pia, A. Khajavirad, and N. V. Sahinidis, "On the impact of running intersection inequalities for globally solving polynomial optimization problems", Mathematical Programming Computation, 12 165‐191, 2020.
- A. Del Pia and A. Khajavirad, "The running intersection relaxation of the multilinear polytope", Mathematics of Operations Research, 46(3) 1008‐1037, 2021.
- A. Del Pia and A. Khajavirad, "Rank‐one Boolean tensor factorization and the multilinear polytope", arXiv:2202.07053, 2022.
- A. Del Pia and A. Khajavirad, "A polynomial‐size extended formulation for the multilinear polytope of beta‐acyclic hypergraphs", Mathematical Programming, 2023.
These papers make significant theoretical and computational advances for a wide range of mixed-integer nonlinear programming (MINLP) problems that contain a multilinear set as a substructure. Such problems arise in a range of settings, including computer vision, material design, and process systems in chemical engineering. A multilinear set is a set of binary points that must satisfy a collection of multilinear equations, and the focus of these works is the study of convexification of these sets by building strong and tractable relaxations. A special case of bilinear sets reduces to the important and well-studied Boolean Quadric Polytope (BQP). While some convexification results for BQP can be applied to multilinear sets, doing so requires working in a potentially much larger extended space, leading to weakening of the relaxations. In these papers, the authors instead directly study the multilinear set, leading to strong classes of valid inequalities, identification of cases when the convex hull of a set can be obtained from the convex hull of different components independently, and a thorough understanding of the complete convex hull for different notions of acyclic hypergraphs. The authors also demonstrated that these results can lead to significant computational improvements when incorporated within a state-of-the-art MINLP solver. Collectively, these papers make deep and insightful contributions to the field of mixed-integer nonlinear programming and the contributions are expected to have enduring impact from the standpoint of both theory and computation.
Honourable mentions:
- David Bergman (Connecticut), Andre Cire (Toronto), Willem-Jan van Hove (Carnegie Mellon), John Hooker (Carnegie Mellon), for laying the foundation for a fundamentally new research direction for discrete optimization based on decision diagrams.
- Hussein Hazimeh (MIT), Rahul Mazumder (MIT), Peter Radchenko (Sydney), for breakthroughs in the ability to compute sparse statistical estimators at scale in the big data era.
The 2023 ICS Prize Committee members are:
- Mirjam Dür (Augsburg)
- Yufeng Liu (UNC)
- Jim Luedtke (Wisconsin)
- Uday Shanbhag, Chair (Penn State)
2022 ICS Prize Winners
The 2022 INFORMS Computing Society prize is awarded to Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang, for their pioneering work on nonconvex stochastic optimization methods, as detailed in the papers:
- Saeed Ghadimi and Guanghui Lan, “Stochastic first- and zeroth-order methods for nonconvex stochastic programming”, SIAM Journal on Optimization 23(4), 2341-2368, 2013.
- Saeed Ghadimi, Guanghui Lan and Hongchao Zhang, “Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization”, Mathematical Programming 155(1-2), 267-305, 2016.
- Saeed Ghadimi and Guanghui Lan, “Accelerated gradient methods for nonconvex nonlinear and stochastic programming”, Mathematical Programming 156 (1-2), 59-99, 2016.
Nonconvex stochastic optimization comprises an important class of problems that are extremely challenging and have many applications. The three prize-winning papers contain several groundbreaking results in this area. In the first paper, the authors propose a novel randomized stochastic gradient descent method for unconstrained problems and establish, for the first time in the literature, complexity results for such types of algorithms. In the second paper, the authors adapt their methods to the constrained case by using a mini-batch of samples at each iteration. Their complexity results in such situations are shown to be near-optimal for the convex case. The third paper provides a generalization of Nesterov’s accelerated gradient (AG) method for nonconvex stochastic optimization problems and derives for the first time convergence results for these kinds of algorithms in the nonconvex case, showing optimal/best known rates of convergence when applied to some specific classes of problems. This work is based on solid, original, and innovative mathematical ideas and significantly advances the state-of-the-art in the field. In addition, given the amount of interest in these kinds of algorithms, the work is expected to have a significant impact in Operations Research, Computer Science, and other areas. Indeed, the three papers already have a total of over 1800 citations.
Runner-up: Dilek Gunnec (Ozyegin), S. Raghu Raghavan (Maryland), and Rui Zhang (CU Boulder) for their contributions on Influence Diffusion on Social Networks.
The 2022 ICS Prize Committee members are:
- Ricardo Fukasawa, Chair (Waterloo)
- Jonathan Eckstein (Rutgers)
- Ignacio Grossmann (Carnegie Mellon)