Spectral projected subgradient with a momentum term for the Lagrangean dual approach
The Lagrangean dual problem, with a non-differentiable convex objective function, is usually solved by using the subgradient method, whose convergence is guaranteed if the optimal value of the dual objective function is known. In practice, this optimal value is approximated by a previously computed bound. In this work, we combine the subgradient method with a different choice of steplength, based on the recently developed spectral projected gradient method, that does not require either exact or approximated estimates of the optimal value. We also add a momentum term to the subgradient direction that accelerates the convergence process towards global solutions. To illustrate the behavior of our new algorithm we solve Lagrangean dual problems associated with integer programming problems. In particular, we present and discuss encouraging numerical results for set covering problems and generalized assignment problems.
90c10 90c25