We expose in a tutorial fashion the mechanisms which underlie the synthesis of optimization algorithms based on dynamic integral quadratic constraints. We reveal how these tools from robust control allow to design accelerated gradient descent algorithms with optimal guaranteed convergence rates by solving small-sized convex semi-definite programs. It is shown that this extends to the design of extremum controllers, with the goal to regulate the output of a general linear closed-loop system to the minimum of an objective function. Numerical experiments illustrate that we can not only recover gradient decent and the triple momentum variant of Nesterov's accelerated first order algorithm, but also automatically syn-thesize optimal algorithms even if the gradient information is passed through non-trivial dynamics, such as time-delays.
%0 Conference Paper
%1 SchEbe23
%A Scherer, Carsten W.
%A Ebenbauer, Christian
%A Holicki, Tobias
%B 2023 62nd IEEE Conference on Decision and Control (CDC)
%D 2023
%K EXC2075 PN4-3(II) inReview
%P 2995-3002
%R 10.1109/CDC49753.2023.10384198
%T Optimization Algorithm Synthesis Based on Integral Quadratic Constraints: A Tutorial
%X We expose in a tutorial fashion the mechanisms which underlie the synthesis of optimization algorithms based on dynamic integral quadratic constraints. We reveal how these tools from robust control allow to design accelerated gradient descent algorithms with optimal guaranteed convergence rates by solving small-sized convex semi-definite programs. It is shown that this extends to the design of extremum controllers, with the goal to regulate the output of a general linear closed-loop system to the minimum of an objective function. Numerical experiments illustrate that we can not only recover gradient decent and the triple momentum variant of Nesterov's accelerated first order algorithm, but also automatically syn-thesize optimal algorithms even if the gradient information is passed through non-trivial dynamics, such as time-delays.
@inproceedings{SchEbe23,
abstract = {We expose in a tutorial fashion the mechanisms which underlie the synthesis of optimization algorithms based on dynamic integral quadratic constraints. We reveal how these tools from robust control allow to design accelerated gradient descent algorithms with optimal guaranteed convergence rates by solving small-sized convex semi-definite programs. It is shown that this extends to the design of extremum controllers, with the goal to regulate the output of a general linear closed-loop system to the minimum of an objective function. Numerical experiments illustrate that we can not only recover gradient decent and the triple momentum variant of Nesterov's accelerated first order algorithm, but also automatically syn-thesize optimal algorithms even if the gradient information is passed through non-trivial dynamics, such as time-delays.},
added-at = {2024-03-12T11:05:21.000+0100},
author = {Scherer, Carsten W. and Ebenbauer, Christian and Holicki, Tobias},
biburl = {https://puma.ub.uni-stuttgart.de/bibtex/23a6d5e5a71520ed5a9b6a61970cbcb88/simtech},
booktitle = {2023 62nd IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC49753.2023.10384198},
interhash = {4b9e04e232bfbff5e5132fa53ca53d32},
intrahash = {3a6d5e5a71520ed5a9b6a61970cbcb88},
issn = {2576-2370},
keywords = {EXC2075 PN4-3(II) inReview},
pages = {2995-3002},
timestamp = {2024-05-08T17:15:09.000+0200},
title = {Optimization Algorithm Synthesis Based on Integral Quadratic Constraints: A Tutorial},
year = 2023
}
