Convergence analysis of primal solutions in dual first-order methods
2013 (English)In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC), IEEE , 2013, 6861-6867 p.Conference paper (Refereed)
This paper studies primal convergence in dual first-order methods for convex optimization. Specifically, we consider Lagrange decomposition of a general class of inequality- And equality-constrained optimization problems with strongly convex, but not necessarily differentiable, objective functions. The corresponding dual problem is solved using a first-order method, and the minimizer of the Lagrangian computed when evaluating the dual function is considered as an approximate primal solution.We derive error bounds for this approximate primal solution in terms of the dual errors. Based on such error bounds, we show that the approximate primal solution converges to the primal optimum at a rate no worse than O(1/pk) if the projected dual gradient method is adopted and O(1/k) if a fast gradient method is utilized, where k is the number of iterations. Finally, via simulation, we compare the convergence behavior of different approximate primal solutions in various dual first-order methods in the literature.
Place, publisher, year, edition, pages
IEEE , 2013. 6861-6867 p.
, IEEE Conference on Decision and Control. Proceedings, ISSN 0743-1546
Constrained optimization, Convex optimization, Error analysis, Gradient methods, Convergence analysis, Convergence behaviors, Equality-constrained optimization, Fast gradient methods, First-order methods, General class, Number of iterations, Objective functions, Lagrange multipliers
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-150876DOI: 10.1109/CDC.2013.6760976ISI: 000352223507113ScopusID: 2-s2.0-84902321784ISBN: 978-146735717-3OAI: oai:DiVA.org:kth-150876DiVA: diva2:745745
52nd IEEE Conference on Decision and Control, CDC 2013, 10 December 2013 through 13 December 2013, Florence, italy
QC 201409112014-09-112014-09-112015-12-08Bibliographically approved