A Method for the Parametric Center Problem, with a Strictly Monotone Polynomial-Time Algorithm for Linear Programming

Given a system of linear inequalities Ax ≤ 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 x̄(t) to the center problems P(t), where P(t) is the problem: maximize ∑_i=1^m ln(b_i + d_it − A_ix) subject to Ax < b + dt and Mx = g + ht. We present an algorithm for tracing the parametric family of solutions x̄(t) over some given range. At the kth iterate of the algorithm, the point x̄(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 x̄(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}) ≤ (T_MAX − t^k)(1 − 1/(128m))

(t^{k+ 1} − T_MIN) ≥ (t^k − T_MIN)(1 + 1/(128m))

where T_MIN (T_MAX) is the maximum (minimum) number t such that Ax ≤ 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.