Uncertainty quantification for optimisation, with applications to discrete problems and their convex relaxations
File(s)
Author(s)
McMeel, Conor William
Type
Thesis
Abstract
In an applied setting, we must accept a degree of uncertainty while solving optimisation problems. Due to this uncertainty, we may obtain a different optimum from our optimisation algorithm depending on the uncertain state. In this thesis, we seek to examine and quantify this effect. We separately examine problems from discrete and continuous optimisation. On the discrete side, we look at submodular functions, a well-studied class of discrete functions which include cut and coverage functions. Here, we examine how sensitive the optimum is to a small change in the input set for different maximisation algorithms. On the continuous side, we look at gradient descent and subgradient descent, where we propose efficient methods to learn the optimum for all states of uncertainty. These methods consider the optimum as a function of the uncertain state, and then use chaos expansions of this function along a truncated basis. We provide theoretical analysis of our methods, as well as experimental verification.
Version
Open Access
Date Issued
2024-01
Date Awarded
2024-11
Copyright Statement
Creative Commons Attribution NonCommercial Licence
License URL
Advisor
Parpas, Panos
Sponsor
Engineering and Physical Sciences Research Council
Grant Number
HiPEDS
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)