Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Certification Aspects of the Fast Gradient Method for Solving the Dual of Parametric Convex Programs


S. Richter, C. Jones, M. Morari

Mathematical Methods of Operations Research, vol. 77, no. 3, pp. 305-321

This paper examines the computational complexity certification of the fast gradient method for the solution of the dual of a parametric convex program. To this end, a lower iteration bound is derived such that for all parameters from a compact set a solution with a specified level of suboptimality will be obtained. For its practical importance, the derivation of the smallest lower iteration bound is considered. In order to determine it, we investigate both the computation of the worst case minimal Euclidean distance between an initial iterate and a Lagrange multiplier and the issue of finding the largest step size for the fast gradient method. In addition, we argue that optimal preconditioning of the dual problem cannot be proven to decrease the smallest lower iteration bound. The findings of this paper are of importance in embedded optimization, for instance, in model predictive control.


Type of Publication:


M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { RicJon:2013:IFA_3921,
    author={S. Richter and C. Jones and M. Morari},
    title={{Certification Aspects of the Fast Gradient Method for
	  Solving the Dual of Parametric Convex Programs}},
    journal={Mathematical Methods of Operations Research},
Permanent link