ADMM in Optimization and Control: Algorithm Specialization, Computational Distribution, and the Value of Structure

The alternating direction method of multipliers (ADMM) is a first-order optimization algorithm for solving convex problems. We study ADMM under a specialization paradigm, which means that we shape the algorithm to customize it to the optimization problem at hand. This specialization paradigm comes as a contrast to using an ‘off-the-shelf’ or general-purpose solver, which follows a ‘one size fits all’ policy. We show that algorithm specialization makes it possible to synthesize a range of desirable algorithm features and characteristics, which promotes ADMM as a powerful and versatile tool in optimization and control. We study specialized ADMM in a variety of forms and for a range of applications. We first consider an optimal bidding strategy for energy reserve markets. In such markets, guarantees for providing grid-balancing power capacity are traded. We devise an ADMM-driven negotiation protocol that coordinates aggregations of market participants to place a joint energy reserve bid. We show that this algorithmic negotiation equally distributes the computational burden to the participants and that it provides further beneficial features, such as low set-up costs and a large participant autonomy. In a second specialized ADMM formulation, we contribute to the area of autonomous coordination and collision avoidance. We present a decentralized ADMM-based navigation protocol for the coordination of moving agents. A challenge arises from the nonconvex collision avoidance constraints, which we handle with successive linearization at each ADMM iteration. A main feature of the resulting algorithm is that it operates from an agent’s point of view, which means that each agent uses a local coordinate system and interacts with its nearest neighbors only. We show that this fully decentralized perspective provides a range of favorable properties to handle the coordination task. Besides tailor-fitting ADMM for specific areas, we also propose an ADMM specialization framework for a general class of model predictive control (MPC) problems. More specifically, we devise a method that uses the structure in the controlled system as an additional source of efficiency for the optimization routine. The algorithm then mimics the structural properties of the system, which leads to an improved performance of the overall procedure. The resulting ADMM formulations are highly parallelizable and particularly suited for embedded implementation. We also present a novel measure for system structure, called the separation tendency. With the separation tendency, we can decide whether a system is sufficiently structured for utilizing our ADMM framework. In the last part of this thesis, we provide a detailed application study for structure-exploiting ADMM. We show how to model and control the power flow in a variable speed drive (VSD). It turns out that the resulting VSD model is a structured system, which makes controlling the power flow in the VSD an excellent example for algorithm specialization