Surrogate gradient algorithm for Lagrangian relaxation

Surrogate gradient algorithm for Lagrangian relaxation

0.00 Avg rating0 Votes
Article ID: iaor2000516
Country: United States
Volume: 100
Issue: 3
Start Page Number: 699
End Page Number: 712
Publication Date: Mar 1999
Journal: Journal of Optimization Theory and Applications
Authors:
Keywords: programming: integer
Abstract:

The subgradient method is used frequently to optimize dual functions in Lagrangian relaxation for separable integer programming problems. In the method, all subproblems must be solved optimally to obtain a subgradient direction. In this paper, the surrogate subgradient method is developed, where a proper direction can be obtained without solving optimally all the subproblems. In fact, only an approximate optimization of one subproblem is needed to obtain a proper surrogate subgradient direction, and the directions are smooth for problems of large size. The convergence of the algorithm is proved. Compared with methods that take effort to find better directions, this method can obtain good directions with much less effort and provides a new approach that is especially powerful for problems of very large size.

Reviews

Required fields are marked *. Your email address will not be published.