CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Primal convergence from dual subgradient methods for convex optimization

Emil Gustavsson (Institutionen för matematiska vetenskaper, matematik) ; Michael Patriksson (Institutionen för matematiska vetenskaper, matematik) ; Ann-Brith Strömberg (Institutionen för matematiska vetenskaper, matematik)
Mathematical Programming (0025-5610). Vol. 150 (2015), 2, p. 365-390.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: Convex programming, Ergodic convergence, Lagrangian duality, Nonlinear multicommodity flow problem, Primal recovery, Subgradient optimization



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2014-11-04. Senast ändrad 2015-04-20.
CPL Pubid: 205239

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Transport
Optimeringslära, systemteori

Chalmers infrastruktur