Sepehr Moalemi

This thesis considers the stability of first-order optimization algorithms, such as gradient descent (GD) and its accelerated variants, using control theory. The control interpretation of such algorithms consists of casting them as a Lur'e problem, where the algorithm is represented as the interconnection of a linear controller in negative feedback with the gradient. Consequently, standard input-output theory, in particular, the Passivity Theorem, can be used to analyze the input-output stability of the interconnection. This passivity-based approach is particularly useful, as it is robust to model uncertainties, such as gradient uncertainty that does not violate passivity. Moreover, the stability of optimization algorithms with varying hyperparameters can be analyzed through the lens of passivity-based gain-scheduling techniques. The novel contributions of this thesis come in two parts.First, it is shown that GD, Polyak's heavy ball (HB), Nesterov's accelerated gradient (NAG), and triple momentum (TM) methods can each be represented as a passive controller in negative feedback with the gradient to be minimized. As such, for a class of functions with sector-bounded gradient, the Passivity Theorem can be used to guarantee the input-output stability as well as the global convergence of these algorithms. Furthermore, compared with existing results, this approach provides a tighter upper bound on the largest allowable step size by guaranteeing the input-output stability of the GD controller.Second, this thesis introduces the gain-scheduling of discrete-time quadratic supply rate (QSR)-dissipative subsystems. The scheduling functions considered here take the form of matrices, generalizing the scalar scheduling functions used in the literature. Furthermore, this thesis extends existing gain-scheduling results to include a broader class of QSR-dissipative systems. Notably, given that passivity is a special case of QSR-dissipativity, it is shown that the matrix-scheduling of passive subsystems results in an overall passive system. As such, the proposed gain-scheduling architecture, in tandem with the passive GD, HB, NAG, and TM controllers, can be used to represent varying hyperparameters and propose new variations of these algorithms.

This paper presents a discrete-time passivity-based analysis of the gradient descent method for a class of functions with sector-bounded gradients. Using a loop transformation, it is shown that the gradient descent method can be interpreted as a passive controller in negative feedback with a very strictly passive system. The passivity theorem is then used to guarantee input-output stability, as well as the global convergence, of the gradient descent method. Furthermore, provided that the lower and upper sector bounds are not equal, the input-output stability of the gradient descent method is guaranteed using the weak passivity theorem for a larger choice of step size. Finally, to demonstrate the utility of this passivity-based analysis, a new variation of the gradient descent method with variable step size is proposed by gain-scheduling the input and output of the gradient.

This paper considers gain-scheduling of QSR-dissipative subsystems using scheduling matrices. The corresponding QSR-dissipative properties of the overall matrix-gain-scheduled system, which depends on the QSR properties of the subsystems scheduled, are explicitly derived. The use of scheduling matrices is a generalization of the scalar scheduling signals used in the literature, and allows for greater design freedom when scheduling systems, such as in the case of gain-scheduled control. Furthermore, this work extends the existing gain-scheduling results to a broader class of QSR-dissipative systems. The matrix-scheduling of important special cases, such as passive, input strictly passive, output strictly passive, finite L2 gain, very strictly passive, and conic systems are presented. The proposed gain-scheduling architecture is used in the context of controlling a planar three-link robot subject to model uncertainty. A novel control synthesis technique is used to design QSR-dissipative subcontrollers that are gain-scheduled using scheduling matrices. Numerical simulation results highlight the greater design freedom of scheduling matrices, leading to improved performance.

This paper considers gain-scheduling of very strictly passive (VSP) subcontrollers using scheduling matrices. The use of scheduling matrices, over scalar scheduling signals, realizes greater design freedom, which in turn can improve closed-loop performance. The form and properties of the scheduling matrices such that the overall gain-scheduled controller is VSP are explicitly discussed. The proposed gain-scheduled VSP controller is used to control a rigid two-link robot subject to model uncertainty where robust input-output stability is assured via the passivity theorem. Numerical simulation results highlight the greater design freedom, resulting in improved performance, when scheduling matrices are used over scalar scheduled signals.

In this presentation, the stability of popular first-order optimization algorithms is examined through the lens of passivity. The passivity theorem ensures input-output stability of a passive plant connected in a negative feedback loop with a very strictly passive (VSP) system. Combining existing work on control interpretation of first-order optimization algorithms with loop transformation techniques, it is shown that gradient descent (GD) can be rendered passive, while the more recent triple momentum (TM) method is input strictly passive (ISP). It is shown that the sector boundedness of the gradient of an L-smooth, m-strongly convex function renders it being VSP. Therefore, the passivity theorem can ensure input-output stability of GD when the gradient is L-smooth, m-strongly convex.