A method of Euclidean centers for linear programming

In this paper the authors describe a new algorithm for solving a linear programming problem of the form: max c ^Tx s.t. where and . The first phase of the algorithm involves finding the Euclidean center and radius of the maximal inscribed hypersphere contained in the polytope defined by . The authors develop a method of steepest ascent which locates this center by maximizing a piecewise linear function. The computation of the direction of steepest ascent involves the solution of a simple quadratic program. The starting point is arbitrary. The second phase of the algorithm is concerned with maximization of the objective function over the feasible region. A simplex that encloses the feasible region is determined by the maximal hypersphere determined in the first phase. If the optimum of the objective function over this simplex is feasible, the algorithm terminates and the solution is bound. If not, a new maximal hypersphere problem is solved in the next iteration. A proof of finite convergence of the algorithm is given. The computational efficiency of the algorithm and various enhancements to the algorithm are tabulated for randomly generated problems. Also, the computational efficiency of the algorithm is compared to that of the simplex method, and shown to be especially promising for problems with many redundant constraints.