On the Absence of Spurious Local Trajectories in Time-varying Nonconvex Optimization

In this paper, 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 \textit{spurio...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-10
Main Authors: Fattahi, S, Josz, C, Ding, Y, Mohammadi, R, Lavaei, J, Sojoudi, S
Format: Article
Language:English
Subjects:
Differential equations
Electrical networks
Invariants
Landscape
Minima
Power flow
Trajectory optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, 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 \textit{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) 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.
ISSN:2331-8422