The paper authored by Salar Fattahi, a recent IEOR PhD grad and incoming Assistant Professor at University of Michigan, Cedric Josz, a former IEOR/EECS postdoc and Assistant Professor at Columbia University, and Reza Mohammadi, an IEOR postdoc, along with Professors Javad Lavaei and Somayeh Sojoudi was selected as a Best Student Paper Award Finalist at the IEEE Conference on Control Technology and Applications (CCTA). The paper was titled “Absence of Spurious Local Trajectories in Time-Varying Optimization: A Control-Theoretic Perspective”.
CCTA is a long-standing conference of the control systems society and was known as Multi-conference on Systems and Control before a name change four years ago.
Berkeley IEOR congratulates the entire team! The abstract for the paper is below; click here to access the entire paper.
Abstract—In this paper, we study the landscape of an optimization problem whose input data vary over time. This time-varying problem consists of infinitely-many individual optimization problems, whose solution is a trajectory over time rather than a single point. To understand when it is possible to find a global solution of a time-varying non-convex optimization problem, we introduce the notion of spurious (i.e., non-global) local trajectory as a generalization to the notion of spurious local solution in nonconvex (time-invariant) optimization. We develop an ordinary differential equation (ODE) which, at limit, characterizes the spurious local solutions of the time-varying optimization problem. By building upon this connection, we prove that the absence of spurious local trajectory is closely related to the transient behavior of the proposed ODE. In particular, we show that: (1) if the problem is time-invariant, the spurious local trajectories are ubiquitous since any strict local minimum is a locally stable equilibrium point of the ODE, and (2) if the ODE is time-varying, the data variation may force all ODE trajectories initialized at arbitrary local minima at the initial time to gradually converge to the global solution trajectory. This implies that the natural data variation in the problem may automatically trigger escaping local minima over time.