Complexity Certification of a Distributed Augmented Lagrangian Method

DOI10.1109/TAC.2017.2747503MaRDI QIDQ4567137zbMATH OpenOpenAlexFDO

Authors Soomin Lee, Nikolaos Chatzipanagiotis, Michael M. Zavlanos

Publication date 27 June 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.11119

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Applications of mathematical programming (90C90)

Abstract: In this paper we present complexity certification results for a distributed Augmented Lagrangian (AL) algorithm used to solve convex optimization problems involving globally coupled linear constraints. Our method relies on the Accelerated Distributed Augmented Lagrangian (ADAL) algorithm, which can handle the coupled linear constraints in a distributed manner based on local estimates of the AL. We show that the theoretical complexity of ADAL to reach an $epsilon$-optimal solution both in terms of suboptimality and infeasibility is $O(frac1epsilon)$ iterations. Moreover, we provide a valid upper bound for the optimal dual multiplier which enables us to explicitly specify these complexity bounds. We also show how to choose the stepsize parameter to minimize the bounds on the convergence rates. Finally, we discuss a motivating example, a model predictive control (MPC) problem, involving a finite number of subsystems which interact with each other via a general network.

Cited in

(2)

• Augmented Lagrangian optimization under fixed-point arithmetic
• Model-based fault isolability and isolation of persistent faults: centralized and distributed implementations

This page was built for publication: Complexity Certification of a Distributed Augmented Lagrangian Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4567137)