Bundle-type subgradient method for lagrangean relaxation procedure

Abstract

In this paper, we suggest the bundle-type subgradient method to update the multipliers in the Lagrangean relaxation procedure. The Lagrangean multipliers usually have been updated through the subgradient method. Although the subgradient method is very simple and generates a sequence which eventually converges to an optimal solution, many researchers have experienced erratic behavior of the subgradient method due to its slow convergence. The slow convergence of the subgradient method is due to its Markov nature. The bundle-type subgradient method uses some of the subgradients generated by the algorithm at the previous iterations. The bundle-type subgradient method generates a point which is strictly closer and forms a acuter angle to the solution set than that generated by the subgradient method. We extend the Poljak``s sufficient condition to the bundle-type subgradient method. The direction generated by the bundle-type subgradient method at each iteration is a positive linear combination of subgradients obtained by the algorithm at the previous iterations. We give the sufficient conditions of the coefficients for the algorithm to converge to an optimal solution. Finally, computational results are given and future research directions are discussed.