-

 

 

 




Optimization Online





 

COMPUTATIONAL COMPLEXITY OF INEXACT GRADIENT AUGMENTED LAGRANGIAN METHODS: APPLICATION TO CONSTRAINED MPC

Valentin Nedelcu(v.nedelcu***at***acse.pub.ro)
Ion Necoara(ion.necoara***at***acse.pub.ro)
Quoc Tran Dinh(quoc.trandinh***at***esat.kuleuven.be)

Abstract: We study the computational complexity certification of inexact gradient augmented Lagrangian methods for solving convex optimization problems with complicated constraints. We solve the augmented Lagrangian dual problem that arises from the relaxation of complicating constraints with gradient and fast gradient methods based on inexact first order information. Moreover, since the exact solution of the augmented Lagrangian primal problem is hard to compute in practice, we solve this problem up to some given inner accuracy. We derive relations between the inner and the outer accuracy of the primal and dual problems and we give a full convergence rate analysis for both gradient and fast gradient algorithms. We provide estimates on the primal and dual suboptimality and on primal feasibility violation of the generated approximate primal and dual solutions. Our analysis relies on the Lipschitz property of the dual function and on inexact dual gradients. We also discuss implementation aspects of the proposed algorithms on constrained model predictive control problems for embedded linear systems.

Keywords: Gradient and fast gradient methods, iteration-complexity certification, augmented Lagrangian, convex programming, embedded systems, constrained linear model predictive control.

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Applications -- Science and Engineering (Control Applications )

Citation: Technical Report, University Politehnica Bucharest, Spl. Independentei 313, pp. 1-23, October, 2012.

Download: [PDF]

Entry Submitted: 11/02/2012
Entry Accepted: 11/02/2012
Entry Last Modified: 11/02/2012

Modify/Update this entry


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

 

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