Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems
Ion Necoara (ion.necoaraacse.pub.ro)
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.
Entry Submitted: 10/03/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|