96. A Linear-Quadratic Program for Estimating Performance of Convex Optimization Algorithm
Invited abstract in session WF-2: Recent advances in computer-aided analyses of optimization algorithms II, stream Conic optimization: theory, algorithms and applications.
Wednesday, 16:20 - 18:00Room: M:O
Authors (first author is the speaker)
| 1. | Ashkan Panahi
|
| Chalmers University of Technology |
Abstract
Performance estimation programs (PEP) are a powerful approach for analyzing and designing optimization algorithms using computer programs. However, their superior performance often comes with the price of a rapidly increasing amount of computation. In this talk, we discuss certain relaxations of the standard PEP formulation that lead to a quadratic optimization problem with linear constraints, hence referred to as Linear-Quadratic PEP (LQ-PEP). We show that LQ-PEP can provide both asymptotic and non asymptotic bounds on convergence with a fixed amount of computation. In certain scenarios, we show that LQ-PEP can be tied to the well-known linear-quadratic control problem. In this way, LQ-PEP may employ tools from the theory of control, especially spectral theory, and harmonic analysis, to forego traditional methods such as potential functions.
We showcase LQ-PEP in a few case studies. We look at the problem of decentralized, asynchronous optimization with delays, under a directed communication graph, and with constraints. For this difficult scenario, we propose a novel optimization algorithm called Asymptotic Double Averaging and Gradient projection (ASY-DAGP). We present the analysis of ASY-DAGP by the LQ-PEP formalism and obtain the first set of generic, sub-linear speeds of convergence in the above scenario. Our result characterizes the error induced by asynchrony and delay in a parameter called “delay factor”.
Keywords
- Analysis and engineering of optimization algorithms
- Convex and non-smooth optimization
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers