Yingjie Bi, a Berkeley IEOR post-doctoral researcher with Professor Javad Lavaei, recently received the Best Student Paper Prize from the INFORMS Optimization Society.
Yingjie, who completed his PhD in Electrical and Computer Engineering from Cornell University earlier this year, was awarded for his co-authored paper titled ‘Duality gap estimation via a refined Shapley-Folkman lemma.’ Through his work, Yingjie addresses an important question in optimization: estimating the duality gap for optimization problems with a non-convex, separable objective. The results also extend to the setting of non-convex constraints, an equally important yet much less studied problem class.
Below is the abstract to Yingjie’s work.
Based on concepts like the kth convex hull and finer characterization of non-convexity of a function, we propose a refinement of the Shapley-Folkman lemma and derive a new estimate for the duality gap of non-convex optimization problems with separable objective functions. We apply our result to the network utility maximization problem in networking and the dynamic spectrum management problem in communication as examples to demonstrate that the new bound can be qualitatively tighter than the existing ones. The idea is also applicable to cases with general non-convex constraints.
Click here to read the prize announcement by INFORMS. Berkeley IEOR congratules Yingjie Bi for the Best Student Paper Prize!