Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 29, Issue 3, Pages 1879-1907Publisher
SIAM PUBLICATIONS
DOI: 10.1137/18M1217644
Keywords
nonconvex optimization; optimization landscape; synchronization on networks; dynamical system; Kuramoto model
Categories
Funding
- NSF [DMS-1712730, DMS-1719545]
- Sloan Foundation
Ask authors/readers for more resources
Studying the landscape of nonconvex cost functions is key towards a better understanding of optimization algorithms widely used in signal processing, statistics, and machine learning. Meanwhile, the famous Kuramoto model has been an important mathematical model for studying the synchronization phenomena of coupled oscillators over various network topologies. In this paper, we bring together these two seemingly unrelated objects by investigating the optimization landscape of a nonlinear function E(theta) = 1/2 Sigma(1 <= i,j <= n) a(ij)(1 - cos(theta(i) - theta(j))) associated with an underlying net- work and exploring the relationship between the existence of local minima and the network topology. This function arises naturally in the Burer-Monteiro method applied to Z(2) synchronization as well as matrix completion on the torus. Moreover, it corresponds to the energy function of the homogeneous Kuramoto model on complex networks for coupled oscillators. We prove that the minimizer of the energy function is unique up to a global translation under deterministic dense graphs and Erdos-Renyi random graphs with tools from optimization and random matrix theory. Consequently, the stable equilibrium of the corresponding homogeneous Kuramoto model is unique and the basin of attraction for the synchronous state of these coupled oscillators is the whole phase space minus a set of measure zero. In addition, our results address when the Burer-Monteiro method recovers the ground truth exactly from highly incomplete observations in Z(2) synchronization and shed light on the robustness of nonconvex optimization algorithms with respect to certain types of so-called monotone adversaries. Numerical simulations are performed to illustrate our results.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available