Theoretical efficiency of a shifted-barrier-function algorithm for linear programming

AbstractThis paper examines the theoretical efficiency of solving a standard-form linear program by solving a sequence of shifted-barrier problems of the form minimizexctx−ε∑j=1nln(xj+εhjs.t. Ax=b, x+εh > 0, for a given and fixed shift vector h > 0, and for a sequence of values of ϵ > 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 no 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̃ 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̃ 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 ϵ at each iteration is 1 − 1⧸(6n), which contributes afactor of 6√n to the number of iterations needed to solve the problem