Lagrangian dual ascent by generalized linear programming

In this paper, generalized linear progamming (GLP) is treated as a generator of feasible directions for the associated Lagrangian dual problem. In particular, we examine the ascent property of dGLP which is defined to be the difference of two successive dual iterates generated by GLP. It is shown that dGLP always ascends the dual function, L, at the points where L is differentiable. At nondifferentiable points, the choice of column entering the master problem is not unique and an arbitrary choice can produce a nonascent direction. However by appropriate choice of entering column(s), dGLP will be an ascent direction. Computational results on random problems indicate that adding line searches along dGLP directions can improve the performance of GLP.