THEORETICAL EFFICIENCY OF A SHIFTED-BARRIER-FUNCTION ALGORITHM FOR LINEAR-PROGRAMMING

This paper examines the theoretical efficiency of solving a standard-form linear program by solving a sequence of shifted-barrier problems of the form [GRAPHICS] for a given and fixed shift vector h > 0, and for a sequence of values of epsilon > 0 that converges to zero. The resulting sequence of solutions to the shifted-barrier problems will converge to a solution to the standard-form linear program. The advantage of using the shifted-barrier approach is that a starting feasible solution is unnecessary, and there is not need for a phase-I-phase-II approach to solving the linear program, either directly or through the addition of an artificial variable. Furthermore, the algorithm can be initiated with a "warm start," i.e., an initial guess of a primal solution x approximately that need not be feasible. The number of iterations needed to solve the linear program to a desired level of accuracy will depend on a measure of how close the initial solution x approximately is to being feasible and optimal. The number of iterations will also depend on the judicious choice of the shift vector h. If an approximate center of the dual feasible region is known in advance, then h can be chosen so that the guaranteed fractional decrease in epsilon at each iteration is 1-1/(6-square-root n), which contributes a factor of 6-square-root n to the number of iteractions needed to the problem.