Absence of Spurious Local Trajectories in Time-Varying Optimization: A Control-Theoretic Perspective
Absence of Spurious Local Trajectories in Time-Varying Optimization: A Control-Theoretic Perspective
复制标题
DOI：
10.1109/ccta41146.2020.9206163
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
S. Fattahi;C. Josz;R. Mohammadi-Ghazi;J. Lavaei;S. Sojoudi
中科院分区：
文献类型：
--
作者：
S. Fattahi;C. Josz;R. Mohammadi-Ghazi;J. Lavaei;S. Sojoudi
在本文中，我们研究了景观的优化问题，其输入数据随时间变化。这个随时间变化的问题由无限多个单独的优化问题组成，其解决方案是随时间变化的轨迹而不是单个点。为了理解何时可能找到时变非凸优化问题的全局解，我们引入了伪（即，非全局）局部轨迹作为非凸（时不变）优化中伪局部解概念的推广。我们开发了一个常微分方程（ODE），在极限情况下，表征了时变优化问题的伪局部解。通过建立在这个连接，我们证明了虚假的本地轨迹的情况下是密切相关的瞬态行为的建议常微分方程。特别地，我们证明了：（1）如果问题是时不变的，虚假的局部轨迹是普遍存在的，因为任何严格的局部极小值是一个局部稳定的平衡点的常微分方程，（2）如果常微分方程是时变的，数据的变化可能会迫使所有的常微分方程轨迹初始化在任意的局部极小值在初始时间逐渐收敛到全局解的轨迹。这意味着问题中的自然数据变化可能会随着时间的推移自动触发逃逸局部最小值。
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.