Department of Industrial Engineering & Decision Analytics [IEDA Seminar] - Robust Optimization at Scale: A Max-min-max Algorithm

10:30am - 12:00pm
Room 2302 (lift 17-18)

Robust optimization (RO) is a powerful paradigm for decision making under uncertainty. Existing computational approaches, including the reformulation approach and the cutting-plane method, do not scale well, hindering the application of RO to modern high-dimensional decision problems. In this paper, we devise a novel first-order algorithm for solving RO based on a max-min-max perspective. Our algorithm operates directly on the model functions and sets through the subgradient and projection oracles, which enables easy exploitation of problem structures and is especially suitable for large-scale instances. Theoretically, we prove that the oracle complexity of our algorithm for attaining an ε-approximate optimal solution is O(ε−3) or O(ε−2), depending on the smoothness of the model functions. The algorithm and convergence analysis are then extended to distributionally robust optimization. We also show via extensive numerical experiments that the proposed algorithm significantly outperforms the reformulation approach, the cutting-plane method and two other recent first-order algorithms, often by an order of 102−104 in terms of accuracy and/or computational speed.

讲者/ 表演者:
Dr. Man-Chung Yue
Institute of Data Science & Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong (HKU)

Dr. Man-Chung Yue is an Assistant Professor at The University of Hong Kong, jointly affiliated with the Institute of Data Science and the Department of Industrial and Manufacturing Systems Engineering. Prior to his current position, he worked as an Assistant Professor at The Hong Kong Polytechnic University and as a Research Associate at Imperial College London. He obtained his Ph.D. in Systems Engineering and Engineering Management and B.Sc. in Mathematics both from The Chinese University of Hong Kong. He is a recipient of the Early Career Award 20/21 of Hong Kong Research Grants Council. His recent paper has been awarded the INFORMS Optimization Society Student Paper Prize. The focus of his research lies in continuous optimization and its interplay with decision-making under uncertainty, signal processing, machine learning and operations research.

Department of Industrial Engineering & Decision Analytics