Control Theory Oriented Analysis and Design of Optimisation Algorithms

Abstract

The thesis focuses on the application of control theory to the design and analysis of optimization algorithms, with a focus on first-order gradient-based methods using constant step sizes. Classical techniques from control theory, including the circle criterion, gain margin optimization, and the internal model principle, are employed to establish global convergence guarantees, identify fundamental performance limits, and develop algorithms that attain these limits.

We begin by developing a gradient-based algorithm for a class of nonconvex functions. The algorithm has a structure similar to the heavy ball, triple momentum, and accelerated gradient methods. The global convergence of the proposed algorithm is established using the circle criterion for a class of cost functions with sector-bounded gradients. The proposed algorithm is designed to have the best possible R-convergence rate among all algorithms whose global convergence can be established using the circle criterion.

The analysis is then extended to online optimization problems. We design an algorithm for solving a class of nonconvex optimization problems with a linearly varying optimal point. The algorithm is represented as a Lur'e-type nonlinear system containing a discrete time double integrator, which ensures tracking with an linearly varying optimal point with zero steady-state error. By using the circle criterion, the global convergence of the algorithm is secured. The algorithm is applied to a time-of-arrival-based localization problem with constant velocity, where it achieves zero steady-state error.

We then design an online optimization algorithm with integral action for quadratic cost functions and linearly varying optimal points. Using results from the optimal gain margin problem, we construct an algorithm that attains the best possible convergence rate among discrete time double integrator methods applied to finite dimensional quadratic problems.

Finally, we address the general case where the optimal point varies according to an $(n-1)$th order polynomial in time. By applying internal model principle, we show that an $n$th order integrator is necessary for exact tracking. Using optimal gain margin results, we construct algorithms that achieve the fundamental convergence rate limit of $\left(\frac{\sqrt{\kappa} - 1 }{\sqrt{\kappa} + 1}\right)^{\frac{1}{n}}$, where $\kappa$ is the condition number of the cost function. This result establishes a fundamental convergence rate bound for all linear first order algorithms exact tracking polynomially varying optimal point.

Overall, the thesis provides control-theoretic interpretations for designing, analyzing, and optimizing first-order algorithms with constant step size. Show more