Ergodic, Primal Convergence in Dual Subgradient Schemes 
for Convex Programming 

Torbjörn Larsson, Michael Patriksson, and Ann-Brith Strömberg 
Division of Optimization
Department of Mathematics
Linköping Institute of Technology
S-581 83 Linköping
Sweden

ABSTRACT:

Lagrangean dualization and subgradient optimization techniques are
frequently used within the field of computational optimization for
finding approximate solutions to large, structured optimization
problems.  The dual subgradient scheme does not automatically produce
primal feasible solutions; there is an abundance of techniques for
computing such solutions (via penalty functions, tangential
approximation schemes, or the solution of auxiliary primal programs),
all of which require a fair amount of computational effort.

We consider a subgradient optimization scheme applied to a Lagrangean
dual formulation of a convex program, and construct, at minor cost, an
ergodic sequence of subproblem solutions which converges to the primal
solution set.  Numerical experiments performed on a traffic
equilibrium assignment problem under road pricing show that the
computation of the ergodic sequence results in a considerable
improvement in the quality of the primal solutions obtained, compared
to those generated in the basic subgradient scheme.

KEY WORDS: Convex Programming, Lagrangean Duality, Lagrangean
Relaxation, Subgradient Optimization, Ergodic Convergence, Primal
Convergence, Traffic Equilibrium Assignment, Road Pricing