A METHOD FOR THE PARAMETRIC CENTER PROBLEM, WITH A STRICTLY MONOTONE POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING

Given a system of linear inequalities Ax less-than-or-equal-to b + dt and equalities Mx = g + ht, where the right-hand sides are parametrically deformed over the scalar t, the parametric center problem is to trace the parametric family of approximate solutions xBAR(t) to the center problems P(t), where P(t) is the problem: maximize SIGMA-i = 1m ln(b(i) + d(i)t - A(i)x) subject to Ax < b + dt and Mx = g + ht. We present an algorithm for tracing the parametric family of solutions xBAR(t) over some given range. At the kth iterate of the algorithm, the point xBAR(t(k)) is an approximate solution to the center problem P(t(k)) (in an appropriate measure of approximation). The value of t(k) is increased to t(k + 1), and a Newton step is used to generate xBAR(t(k + 1)) which is an approximate solution to the center problem P(t(k + 1)). The sequence of values of t exhibit at least one of the following geometric rates of change: (T(MAX) - t(k + 1)) less-than-or-equal-to (T(MAX) - t(k)) (1 - 1/128m), (t(k + 1) - T(MIN)) greater-than-or-equal-to (t(k) - T(MIN)) (1 + 1/128m), where T(MIN) (T(MAX)) is the maximum (minimum) number t such that Ax less-than-or-equal-to b + dt, Mx = g + ht has a solution. Thus the iterates exhibit either linear growth away from T(MIN) or linear convergence toward T(MAX), with a rate of change of 1/128m, where m is the number of inequality constraints. When applied to the linear programming problem, the algorithm is an O(mL) iteration algorithm for linear programming, that strictly improves the primal objective value at each iteration, and requires no dual feasible solution (or even dual feasibility) to start. After O(mL) iterations, the algorithm either detects primal unboundedness or produces an interior solution that can be rounded to an optimal solution to the linear program.