Titre : Structure, Analysis, and Synthesis of First-Order Algorithms
Résumé : Optimization algorithms can be interpreted through the lens of dynamical systems as the interconnection of a linear system and a set of subgradient nonlinearities. This dynamical systems formulation allows for the analysis and synthesis of optimization algorithms by solving robust control problems. In this work, we use the celebrated internal model principle in control theory to structurally factorize convergent optimization algorithms into a suitable network-dependent internal model and a core subcontroller. As the key benefit, we reveal that this permits us to synthesize optimization algorithms even if information is transmitted over networks featuring phenomena such as time delays or channel memory. Design of these certified-exponentially-convergent networked algorithms is achieved under bisection in the convergence rate through either a nonconvex local search or by alternation of convex semidefinite programs. We demonstrate factorization of existing optimization algorithms and the automated synthesis of new optimization algorithms in the networked setting.
