Accelerating the convergence of subgradient optimisation

Subgradient optimisation is a popular method of finding a good set of multipliers for use in Lagrangean relaxation. Convergence is not necessarily monotonic, and it is generally observed that the lower bound obtained using subgradient optimisation fluctuates. A method of obtaining faster convergence is put forward here, with computational results for a class of generalised assignment problems and for capacitated warehouse location problems.