Scalable and data-driven approaches to convex programming

Thesis

Mathematical optimisation plays a crucial role in providing efficient solutions to modern engineering applications. Despite enormous advances in the past decades, some of these applications involve solving optimisation problems that may not be computationally tractable or that call for new theoretical advancements. Hence, obtaining robust and scalable methods and developing new analytic tools to optimisation problems is of paramount importance. This thesis addresses some of the main challenges when solving optimisation programs, namely, scalability, the presence of integer decision variables and the presence of uncertainty.

Scalability throughout this thesis is achieved by means of distributed computation. Technological advancements that lead to the increase of computational devices per capita have attracted research on the development of algorithms that can exploit such a distributed and unstructured computational power to solve large-scale optimisation problems. In this context, multi-agent optimisation has emerged, as it enables distributed computation by allowing devices (or agents) to communicate over a network. This thesis proposes an algorithmic scheme based on subgradient averaging to perform multi-agent optimisation.

Some optimisation problems are computationally intractable due to the presence of integer variables. Optimising over integers is, in general, hard due to the lack of polynomial-time algorithms to obtain an optimal solution. In fact, some well-known NP-hard problems can be cast as optimisation programs involving integer decision variables. In this thesis we investigate the so-called actuator placement problem and show that a particular instance of this problem, despite being an integer program can be solved exactly by means of a convex relaxation. We also link such a relaxation to the multi-agent optimisation framework explored previously, showing how distributed schemes can be leveraged to obtain the optimal solution.

Other challenging optimisation problems arise with the presence of uncertain constraints. Indeed, even the well-studied class of linear optimisation problems may require theoretical and algorithmic advancements under this type of constraints. Uncertain constraints represent our lack of knowledge about the underlying phenomena and appear in several applications, including the optimal power flow problem under renewable energy generation, robotics, and transportation applications. Motivated by this fact, the last part of this thesis focuses on a randomised approximation to chance-constrained optimisation problems. We show a new theoretical bound on the probability of constraint violation that can improve the conservatism with respect to the state-of-the-art.

Authors: Romao, L

• DOI: 10.5287/ora-a49jxxgdb
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: uncertain optimization; actuator placement; scenario approach theory; optimization; distributed optimization
• Subjects: Multiagent systems; Uncertain optimization; Mathematical optimization; Distributed algorithms