A NEW FINITE CONTINUATION ALGORITHM FOR LINEAR-PROGRAMMING

We describe a new finite continuation algorithm for linear programming . The dual of the linear programming problem with unit lower and upper bounds is formulated as an l(1) minimization problem augmented with t he addition of a linear term. This nondifferentiable problem is approx imated by a smooth problem. It is shown that the minimizers of the smo oth problem define a family of piecewise-linear paths as a function of a smoothing parameter. Based on this property, a finite algorithm tha t, traces these paths to arrive at an optimal solution of the linear p rogram is developed. The smooth problems are solved by a Newton-type a lgorithm. Preliminary numerical results indicate that the new algorith m is promising.