An algorithm for finding the shortest element of a polyhedral set with application to lagrangian duality |
| |
Authors: | Mokhtar S Bazaraa Jamie J Goode Ronald L Rardin |
| |
Institution: | 1. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332 U.S.A.;2. School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332 U.S.A. |
| |
Abstract: | An algorithm is developed which finds the point in a compact polyhedral set with smallest Euclidean norm. At each iteration the algorithm requires knowledge of only those vertices of the set which are adjacent to a current reference vertex. This feature is shown to permit the adoption of the technique to find iteratively the shortest subgradient (i.e. the direction of steepest ascent) of the lagrangian dual function for large scale linear programs. Procedures are presented for finding the direction of steepest ascent in both the equality constraint and the inequality constraint cases of lagrangian duality. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |