Steepest Edge Algorithms in Linear and Nonlinear Programming

摘要

Several algorithms in linear and nonlinear programming have been developed and analyzed. A worst-case analysis of the steepest edge simplex method showed it to have exponential time-complexity. This algorithm was specialized for solving minimum cost network flow problems and a partial pricing variant was developed. After extensive testing on randomly generated large problems the method was found to be inferior to efficiently coded partial pricing variants of the 'standard' simplex method except for the max flow problem and the problem of finding a feasible flow. On the max flow problem the algorithm was compared with the Edmonds-Karp and Dinic algorithms and found to be superior. In quadratic programming, the use of the steepest edge (face) criterion for dropping constraints was found to be helpful. Dual methods were found to be even more efficient and their use in recursive quadratic programming algorithms for nonlinear programming problems is recommended. A numerically stable ellipsoid algorithm for linear programming was developed and analyzed. At present the main promise that this method holds is as a powerful theoretical tool. Several minimization algorithms for taking advantage of negative curvature were developed as was a curvilinear steplength algorithm which ensures convergence to a positive semidefinite point. (Author)