Complexity certifications of first-order inexact Lagrangian methods for general convex programming: application to real-time MPC.

*(English)*Zbl 1334.49091
Olaru, Sorin (ed.) et al., Developments in model-based optimization and control. Distributed control and industrial applications. Based on two workshops on optimisation-based control and estimation at CentraleSupélec, France, November 2013 and November 2014. Cham: Springer (ISBN 978-3-319-26685-5/pbk; 978-3-319-26687-9/ebook). Lecture Notes in Control and Information Sciences 464, 3-26 (2015).

Summary: In this chapter, we derive the computational complexity certifications of first-order inexact dual methods for solving general smooth constrained convex problems which can arise in real-time applications, such as model predictive control. When it is difficult to project on the primal constraint set described by a collection of general convex functions, we use the Lagrangian relaxation to handle the complicated constraints and then, we apply dual (fast) gradient algorithms based on inexact dual gradient information for solving the corresponding dual problem. The iteration complexity analysis is based on two types of approximate primal solutions: the primal last iterate and an average of primal iterates. We provide sublinear computational complexity estimates on the primal suboptimality and constraint (feasibility) violation of the generated approximate primal solutions. In the final part of the chapter, we present an open-source quadratic optimization solver, referred to as DuQuad, for convex quadratic programs and for evaluation of its behavior. The solver contains the C-language implementations of the analyzed algorithms.

For the entire collection see [Zbl 1337.49003].

For the entire collection see [Zbl 1337.49003].

##### MSC:

49M29 | Numerical methods involving duality |

90C60 | Abstract computational complexity for mathematical programming problems |

90C25 | Convex programming |

68Q25 | Analysis of algorithms and problem complexity |

##### Keywords:

convex problems; Lagrange duality; inexact dual first-order methods; iteration complexity; model predictive control
PDF
BibTeX
XML
Cite

\textit{I. Necoara} et al., Lect. Notes Control Inf. Sci. 464, 3--26 (2015; Zbl 1334.49091)

Full Text:
DOI

**OpenURL**

##### References:

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.