A two-point heuristic to calculate the stepsize in subgradient method with application to a network design problem

Abstract

We introduce a heuristic rule for calculating the stepsize in the subgradient method for unconstrained convex nonsmooth optimization which, unlike the classic approach, is based on retaining some information from previous iteration. The rule is inspired by the well known two-point stepsize by Barzilai and Borwein (BB) [6] for smooth optimization and it coincides with (BB) in case the function to be minimised is convex quadratic.Under the use of appropriate safeguards we demonstrate that the method terminates at a point that satisfies an approximate optimality condition.The proposed approach is tested in the framework of Lagrangian relaxation for integer linear programming where the Lagrangian dual requires maximization of a concave and nonsmooth (piecewise affine) function. In particular we focus on the relaxation of the Minimum Spanning Tree problem with Conflicting Edge Pairs (MSTC). Comparison with classic subgradient method is presented. The results on some widely used academic test problems are provided too.

Keywords

• Convex programming
• Subgradient method
• Lagrangian relaxation
• Minimum spanning tree with conflicting edge pairs