2015/06/17 by Ion Necoara, Necoara, Ion, Andrei Pătraşcu +3
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.1506.05328
openalex publication_date 2015/06/17 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
In this chapter we derive computational complexity certifications of first\norder inexact dual methods for solving general smooth constrained convex\nproblems which can arise in real-time applications, such as model predictive\ncontrol. When it is difficult to project on the primal constraint set described\nby a collection of general convex functions, we use the Lagrangian relaxation\nto handle the complicated constraints and then, we apply dual (fast) gradient\nalgorithms based on inexact dual gradient information for solving the\ncorresponding dual problem. The iteration complexity analysis is based on two\ntypes of approximate primal solutions: the primal last iterate and an average\nof primal iterates. We provide sublinear computational complexity estimates on\nthe primal suboptimality and constraint (feasibility) violation of the\ngenerated approximate primal solutions. In the final part of the chapter, we\npresent an open-source quadratic optimization solver, referred to as DuQuad,\nfor convex quadratic programs and for evaluation of its behaviour. The solver\ncontains the C-language implementations of the analyzed algorithms.\n