On the Absence of Spurious Local Trajectories in Time-Varying Nonconvex Optimization
On the Absence of Spurious Local Trajectories in Time-Varying Nonconvex Optimization
复制标题
DOI：
10.1109/tac.2021.3137147
复制
发表时间：
2020-11
影响因子：
6.8
通讯作者：
S. Fattahi;C. Josz;Yuhao Ding;R. Mohammadi;J. Lavaei;S. Sojoudi
中科院分区：
文献类型：
--
作者：
S. Fattahi;C. Josz;Yuhao Ding;R. Mohammadi;J. Lavaei;S. Sojoudi
在这篇文章中，我们研究了一个在线非凸优化问题，其输入数据随时间变化，其解是轨迹而不是单个点。为了理解寻找这个问题的全局解的复杂性，我们引入了伪(即非全局)局部轨迹的概念，作为非凸(时不变)优化中伪局部解概念的推广。我们建立了一个与时变非线性动力系统相关的常微分方程组，它在极限下刻画了时变优化问题的伪局部解。证明了无伪局部轨迹的存在与系统的暂态行为密切相关。特别地，我们证明了如果问题是时变的，数据的变化可能会迫使初始时刻在任意局部极小值处初始化的所有常微分方程组的轨迹逐渐收敛到全局解轨迹。我们研究了沿局部最小轨迹的动力系统的雅可比矩阵，并展示了它的特征值是如何被问题中的自然数据变化操纵的，这可能导致随着时间的推移而逃脱局部极小点。
In this article, we study the landscape of an online nonconvex optimization problem, for which the input data vary over time and the solution is a trajectory rather than a single point. To understand the complexity of finding a global solution of this problem, we introduce the notion of spurious (i.e., nonglobal) local trajectory as a generalization to the notion of spurious local solution in nonconvex (time-invariant) optimization. We develop an ordinary differential equation (ODE) associated with a time-varying nonlinear dynamical system which, at limit, characterizes the spurious local solutions of the time-varying optimization problem. We prove that the absence of spurious local trajectory is closely related to the transient behavior of the developed system. In particular, we show that if the problem is time-varying, the data variation may force all of the ODE trajectories initialized at arbitrary local minima at the initial time to gradually converge to the global solution trajectory. We study the Jacobian of the dynamical system along a local minimum trajectory and show how its eigenvalues are manipulated by the natural data variation in the problem, which may consequently trigger escaping poor local minima over time.