2020 INFORMS Optimization Society Student Paper Prizes
Winner
Yingjie Bi (Electrical and Computer Engineering Cornell University)’s paper titled “Duality gap estimation via a refined Shapley-Folkman lemma" (jointly authored with A. Kevin Tang)
Citation
This research addresses an important question in optimization: estimating the duality gap for optimization problems with a nonconvex, separable objective. This problem has classical roots based on the Shapley-Folkman lemma from the 1950s. Yet, the best known gap estimates go back to the 1980s, with the exception of a 2016 paper (by M. Udell and S. Boyd) which improves the coefficients but not the order of the gap estimate. In this paper, by introducing new concepts, such as the k-th convex hull, the authors are able to refine the Shapley-Folkman lemma considerably. Their geometric approach to this problem coupled with convex analysis tools not only provides new insights into this classical problem, but also allows for elegant derivations and clean results that significantly improve the best known duality gap estimates. Their results also extend to the setting of nonconvex constraints, an equally important yet much less studied problem class. They substantiate many of their insights through convincing applications in engineering, e.g., internet routing, power control in communications, for which this paper improves upon the best known gap bounds in the literature. Collectively, this paper paves the way for a novel understanding of duality gap estimation of nonconvex separable optimization problems. We expect this work to endure and to find exciting applications in domains including operations research, machine learning, and engineering where nonconvexities are prevalent.
Second Prize
Digivijay Boob (Industrial and Systems Engineering, Georgia Institute of Technology) for the paper "Stochastic First-order Methods for Convex and Nonconvex Function Constrained Optimization" (jointly authored with George Lan and Qi Deng)
Prize committee
Fatma Kilinc-Karzan (chair), Maryam Fazel, Daniel Kuhn, Andrea Lodi