Max-Weight Revisited: Sequences of Non-Convex Optimisations Solving Convex Optimisations

2014/06/03 by Víctor Valls, Valls, Víctor, Douglas J. Leith +1
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #cs.IT #math.IT #math.OC

paper · pdf · doi:10.48550/arxiv.1406.0899

convex optimisation, max-weight scheduling, backpressure, subgradient methods

arxiv created 2015/08/26 · arxiv updated 2015/08/27

Abstract

We investigate the connections between max-weight approaches and dual subgradient methods for convex optimisation. We find that strong connections exist and we establish a clean, unifying theoretical framework that includes both max-weight and dual subgradient approaches as special cases. Our analysis uses only elementary methods, and is not asymptotic in nature. It also allows us to establish an explicit and direct connection between discrete queue occupancies and Lagrange multipliers.

Related

• Descent With Approximate Multipliers is Enough: Generalising Max-Weight
• Primal-dual subgradient method for constrained convex optimization problems
• Primal-dual subgradient methods for minimizing uniformly convex functions
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization