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

This paper examines the computational complexity certification of the fast gradient method for the solution of the dual of a parametric con- vex 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 subop- timality will be obtained. For its practical importance, the derivation of the smallest lower iteration bound is considered. In order to determine it, we in- vestigate 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.

Published in:
Mathematical Methods of Operations Research
Heidelberg, Springer Heidelberg

Note: The status of this file is: EPFL only

 Record created 2012-10-29, last modified 2019-03-16

Download fulltextPDF
Publisher's version:
Download fulltextPDF
Rate this document:

Rate this document:
(Not yet reviewed)