2013 · 24 citations · 19 references
Natural SciencesComputer ScienceDistributed SystemsOptimizationParallel AlgorithmsConvex OptimizationDistributed AlgorithmsDistributed ComputingGradient-based OptimizationOptimal ControlQuadratic ProgrammingConstraintsConvex Quadratic ProgrammingCurvatureDistributed Convex OptimizationDistributed OptimizationLagrangian DualityLagrangian Relaxation
We propose a distributed algorithm for strictly convex quadratic programming (QP) problems with a generic coupling topology. The coupling constraints are dualized via Lagrangian relaxation. This allows for a distributed evaluation of the non-smooth dual function and its derivatives. We propose to use both the gradient and the curvature information within a non-smooth variant of Newton's method to find the optimal dual variables. Our novel approach is designed such that the large Newton system never needs to be formed. Instead, we employ an iterative method to solve the Newton system in a distributed manner. The effectiveness of the method is demonstrated on an academic optimal control problem. A comparison with state-of-the-art first order dual methods is given.
19
A nonsmooth version of Newton's method
Liqun Qi, Jie Sun · Mathematical Programming · 1993 · 1.5K citations