First order optimisation algorithms in uncertain environments: iterate to minimise the uncertain gap between rationality and reality

Thesis

With advances in onboard computing power and inter-processing-unit communication technology, decision-making systems facilitated with online distributed algorithms are becoming increasingly advantageous. However, in this setting uncertainties are prevalent and non-diminishing due to estimation errors and communication asynchrony.        The first part of this thesis focuses on solving convex distributed optimisation problems with local consensus coupling constraints via the alternating direction method of multipliers (ADMM), using an asynchronous methodology allowing for communication delays. We use a bipartite undirected graph to denote the update structure of the processing agents that cooperatively perform the distributed algorithm without a centralised aggregator. We introduce a data server to exchange the asynchronous consensus data among the processing agents. Under technical assumptions involving bounded delays, bounded step sizes, and strong convexities in parts of the local objectives, the running average of local iterates generated by the proposed asynchronous algorithm converges to an optimal solution.
    To solve convex optimisation problems we rely on iterative algorithms, but when the problem contains parameters that need to be estimated from measurements with noise, another iterative process is needed to perform estimation. In the second part of this thesis we devise a modified version of ADMM that performs parameter estimation simultaneously with optimisation. Given convergent parameter estimates, and assuming the objective can be expressed in terms of a multi-parametric quadratic program (mp-QP), we prove convergence of the objective values, dual variables and primal residual. Simulation results show that the rate of convergence tracks that of the estimator up to an upper limit that is characterised by convergence rate of ADMM with no parametric uncertainty.
    The third part of this thesis provides a general framework for analysing the convergence of online decision-making algorithms under uncertainty. These algorithms are formulated as recursive fixed-point iterations characterised by stochastic nonexpansive operators that are parametrised by recursive estimates of uncertain parameters in the presence of noise. Since  nonexpansiveness is preserved under convex combinations, we propose the concept of the stochastic mean operator as the overall averaged operator. Assuming non-i.i.d.\ and finite variance convergence of the estimated parameters, we provide first and second moment convergence theorems of the iterates. Numerical results show the robustness of the iterates when almost all the parameters of the optimisation problem are uncertain. In addition to the obvious improvements in computational efficiency that this approach affords, we also observe an ``advantage over perfectionism'' effect, in which the proposed algorithm outperforms the optimal solutions defined by the most recent estimated parameters.

Authors: Pan, Z

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: distributed optimisation; operator theory; stochastic optimisation; convex optimisation; online MPC; online opmisation
• Subjects: Control theory; Mathematical optimization--Data processing; Distributed algorithms