On Coordinated Primal-Dual Interior-Point Methods for Multi-Agent Optimization

This paper presents a coordinated primal-dual interior point (PDIP) method for solving structured convex linear and quadratic programs (LP-QP) in a distributed man- ner. The considered class of problems represents a multi-agent setting, where the aggregated cost is to be minimized while respecting coupling constraints as well as local constraints of the agents. Unlike fully distributed methods, a central agent is utilized, which coordinates the Newton steps taken within the interior-point algorithm. In practical PDIP implementations, predictor-corrector variants are widely used, due to their very fast convergence. We show that in the coordinated case, a naive implementation of a PDIP with predictor-corrector scheme introduces extra communication steps between local and central agents. We propose a decentralized predictor-corrector scheme that uses a non-uniform perturbation on the complementary slackness condition, which is able to reduce the number of communication steps while preserving fast convergence of the original methods. We analyse the general framework of PDIP methods with non-uniform perturbations and provide convergence and complexity results, that directly apply to the proposed coordinated PDIP with decentralized predictor- corrector scheme.