To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

Primal convergence from d… - University of Gothenburg, Sweden Till startsida
Sitemap
To content Read more about how we use cookies on gu.se

Primal convergence from dual subgradient methods for convex optimization

Journal article
Authors Emil Gustavsson
Michael Patriksson
Ann-Brith Strömberg
Published in Mathematical Programming
Volume 150
Issue 2
Pages 365-390
ISSN 0025-5610
Publication year 2015
Published at Department of Mathematical Sciences, Mathematics
Pages 365-390
Language en
Links dx.doi.org/10.1007/s10107-014-0772-...
Keywords Convex programming, Ergodic convergence, Lagrangian duality, Nonlinear multicommodity flow problem, Primal recovery, Subgradient optimization
Subject categories Optimization, systems theory

Abstract

When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favorably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach unless the Lagrangian dual function is differentiable at an optimal solution. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which is shown to converge to an optimal primal solution when the convexity weights are appropriately chosen. We generalize previous convergence results from linear to convex optimization and present a new set of rules for constructing the convexity weights that define the ergodic sequence of primal solutions. In contrast to previously proposed rules, they exploit more information from later subproblem solutions than from earlier ones. We evaluate the proposed rules on a set of nonlinear multicommodity flow problems and demonstrate that they clearly outperform the ones previously proposed.

Page Manager: Webmaster|Last update: 9/11/2012
Share:

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?