AI4OPT Seminar Series

Date: Thursday, November 10, 2022

Location: 9th floor Atrium in Coda Building (756 W Peachtree St NW, Atlanta, GA 30308)

Time: Noon – 1:00 pm

Meeting Link: https://gatech.zoom.us/j/99381428980

Speakers: Weijun Xie & Yongchun Li

On Dantzig-Wolfe Relaxation of Rank Constrained Optimization: Exactness, Rank Bounds, and Algorithms

Abstract: This paper studies the rank constrained optimization problem (RCOP) that aims to minimize a linear objective function over intersecting a prespecified closed rank constrained domain set with two-sided linear matrix inequalities. The generic RCOP framework exists in many nonconvex optimization and machine learning problems. Although RCOP is, in general, NP-hard, recent studies reveal that its Dantzig-Wolfe Relaxation (DWR), which refers to replacing the domain set by its closed convex hull, can lead to a promising relaxation scheme. This motivates us to study the strength of DWR. Specifically, we develop the first-known necessary and sufficient conditions under which the DWR and RCOP are equivalent. Beyond the exactness, we prove the rank bound of optimal DWR extreme points. We design a column generation algorithm with an effective separation procedure. The numerical study confirms the promise of the proposed theoretical and algorithmic results.

Bio: Weijun Xie is the Coca-Cola Foundation Early Career Professor and assistant professor in the H. Milton Stewart School of Industrial and Systems Engineering (ISyE) at Georgia Tech. Prior to joining ISyE, he was an assistant professor at the Grado Department of Industrial and Systems Engineering at Virginia Tech from 2017-2022. Xie obtained his Ph.D. in Operations Research at Georgia Tech August 2017. His research interests are in theory and applications of stochastic, discrete, and convex optimization. His works have received multiple awards, including the 2022 New Investigator Award from the Virginia Space Grant Consortium (VSGC), which is a coalition of five Virginia colleges and universities, NASA, state educational agencies, Virginia’s Center for Innovative Technology, and other institutions representing diverse aerospace education and research, as well as the 2021 NSF's Faculty Early Career Development Program (CAREER) Award, and winner of the 2020 INFORMS Young Researchers Paper Prize. He currently serves as the Vice Chair of optimization under uncertainty at INFORMS Optimization Society and is an associate editor of mathematical programming with the Journal of Global Optimization.

Bio: Yongchun Li is a Ph.D. student in Operations Research in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech, and advised by Weijun Xie. Before joining Georgia Tech, Li was a Ph.D. candidate in Operations Research in the Grado Department of Industrial and Systems Engineering at Virginia Tech. Her research interests lie in the development of scalable algorithms with theoretical performance guarantees to address problems in large-scale optimization and machine learning. Li's research also establishes connections between theoretical significance and practical impacts, where the proposed algorithms have been applied to the optimal sensor placement in power systems, anomaly detection of solar flare phenomena, and factor analysis of substance abuse.

Note: Lunch with be served at the seminar. Please arrive 15 minutes before the seminar to pick up lunch.

Please subscribe to ai4opt-seminars mailing list at https://lists.isye.gatech.edu/mailman/listinfo/ai4opt-seminars