Optimization Online


Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems

Ion Necoara (ion.necoara***at***acse.pub.ro)
Valentin Nedelcu (vali_nedelcu2006***at***yahoo.com)

Abstract: In this paper we propose two dual decomposition methods based on inexact dual gradient information for solving large-scale smooth convex optimization problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first order methods based on approximate gradients and we prove sublinear rate of convergence for these methods. We also provide for the first time estimates on the primal feasibility violation and primal and dual suboptimality of the generated approximate primal and dual solutions. Moreover, we solve approximatively the inner problems with a parallel coordinate descent algorithm and we show that it has linear convergence rate. Our analysis relies on the Lipschitz property of the dual function and inexact dual gradients. Further, we apply these methods to distributed model predictive control for network systems. By tightening the complicating constraints we are also able to ensure the primal feasibility of the approximate solutions generated by the proposed algorithms. We obtain a distributed control strategy that has the following features: state and input constraints are satisfied, stability of the plant is guaranteed, whilst the number of iterations for the suboptimal solution can be precisely determined.

Keywords: dual decomposition, inexact dual gradient algorithms, parallel coordinate descent algorithm, rate of convergence, estimates on suboptimality and infeasibility, distributed model predictive control.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Infinite Dimensional Optimization (Distributed Control )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Technical Report, nr 155, University Politehnica Bucharest, Automation and Systems Engineering Department, June, 2012.

Download: [PDF]

Entry Submitted: 10/03/2012
Entry Accepted: 10/03/2012
Entry Last Modified: 02/12/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society