The volume algorithm revisited: Relation with bundle methods

The volume algorithm revisited: Relation with bundle methods

0.00 Avg rating0 Votes
Article ID: iaor20032524
Country: Germany
Volume: 94
Issue: 1
Start Page Number: 41
End Page Number: 69
Publication Date: Jan 2002
Journal: Mathematical Programming
Authors: , ,
Keywords: bundle methods
Abstract:

We revise the Volume Algorithm (VA) for linear programming and relate it to bundle methods. When first introduced, VA was presented as a subgradient-like method for solving the original problem in its dual form. In a way similar to the serious/null steps philosophy of bundle methods, VA produces green, yellow or red steps. In order to give convergence results, we introduce in NA a precise measure for the improvement needed to declare a green or serious step. This addition yields a revised formulation (RVA) that is halfway between VA and a specific bundle method, that we call BVA. We analyze the convergence properties of both RVA and BVA. Finally, we compare the performance of the modified algorithms versus VA on a set of Rectilinear Steiner problems of various sizes and increasing complexity, derived from real world very large scale integration design instances.

Reviews

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