Towards computational complexity certification for constrained mpc based on lagrange relaxation and the fast gradient method

Solving a convex optimization problem within an a priori certified period of time is a challenging problem. This paper discusses the certification of Nesterov’s fast gradient method for problems with a strictly quadratic objective and a feasible set given as the intersection of a parametrized affine set and a convex set constraint. We derive a lower iteration bound for the solution of the dual problem that is obtained from a partial Lagrange Relaxation and propose a new constant step- size rule that we prove to be optimal under mild assumptions. Finally, the certification procedure is applied to a constrained MPC problem and it is shown that the new step-size rule improves convergence significantly.


Published in:
Proceedings of the IEEE Conference on Decision & Control
Presented at:
IEEE Conference on Decision & Control, Orlando, Florida, December, 2011
Year:
2011
Laboratories:




 Record created 2011-10-24, last modified 2018-01-28


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)