A potential-function reduction algorithm for solving a linear program directly from an infeasible ‘warm start’

This paper develops an algorithm for solving a standard-form linear program directly from an infeasible ‘warm start’, i.e., directly from a given infeasible solution that satisfies but , 0 The algorithm is a potential function reduction algorithm, but the potential function is somewhat different than other interior-point method potential functions, and is given by where is a given constant, h is a given strictly positive shift vector used to shift the nonnegativity constaints, and B is a lower bound on the optimal value of the linear program. The duality gap is used both in the leading term as well as in the barrier term to help shift the nonnegativity constraints. The algorithm is shown under suitable conditions to achieve a constant decrease in the pential function and so achieves a constant decrease in the duality gap (and hence also in the infeasibility) in iterations. Under more restrictive assumptions regarding the dual feasible region, this algorithm is modified by the addition of a dual barrier term, and will achieve a constant decrease in the duality gap (and in the infeasibility) in iterations.