Division of Optimization,
Department of Mathematics,
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 present a procedure which, at minor cost produces an ergodic sequence of Lagrangean subproblem solutions that converges to the primal optimal set, within a dual subgradient scheme for the solution of convex programs. 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 obtained by the basic subgradient scheme.