March 27, 2023 Monday
We study the conditions that underlie the asymptotic and exponential convergence of saddle flow dynamics of convex-concave functions to a saddle point. First, we propose a certificate rooted in observability for asymptotic convergence of saddle flows. It generalizes conventional conditions for convergence, e.g., strict convexity-concavity, and leads to a novel regularization method that is separable and makes minimal requirements on convexity-concavity for asymptotic convergence. Second, we show that saddle flows’ global exponential stability is a direct consequence of strong convexity-concavity, which provides a lower-bound estimate of the convergence rate. This insight explains some existing algorithms’ convergence properties for equality constrained convex optimization, e.g., proximal gradient. It is further exploited to design a novel alternative regularized algorithm that achieves exponential convergence at a rate depending only on the strong convexity of the objective. Our results generalize to saddle flow dynamics with projections on the vector field and have immediate applications in inequality constrained convex optimization, in particular, distributed linear programs and constrained reinforcement learning.
Dr. Pengcheng YOU
Assistant Professor, Department of Industrial Engineering and Management, Peking University
Dr. Pengcheng You is currently an Assistant Professor in the Department of Industrial Engineering and Management, College of Engineering, at Peking University. He holds a joint appointment at the National Engineering Laboratory for Big Data Analysis and Applications, Peking University. He was a postdoc and lecturer with the Whiting School of Engineering (ME & ECE) at Johns Hopkins University, and also worked at Caltech and PNNL. His research focuses on control, optimization, operations research, reinforcement learning and market mechanisms, with main applications to power and energy systems. Dr. You earned his Ph.D. and B.S. (with honors) degrees both from Zhejiang University.