A SCALING TECHNIQUE FOR FINDING THE WEIGHTED ANALYTIC CENTER OF A POLYTOPE

Let a bounded full dimensional polytope be defined by the system Ax greater-than-or-equal-to b where A is an m x n matrix. Let a(i) denote the ith row of the matrix A, and define the weighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function -SIGMA(i=1)m w(i) ln(a(i)(T)x - b(i)). The proper selection of weights w(i) can make any desired point in the interior of the polytope become the weighted analytic center. As a result, the weighted analytic center has applications in both linear and general convex programming. For simplicity we assume that the weights are positive integers. If some of the w(i)'s are much larger than others, then Newton's method for minimizing the resulting barrier function is very unstable and can be very slow. Previous methods for finding the weighted analytic center relied upon a rather direct application of Newton's method potentially resulting in very slow global convergence. We present a method for finding the weighted analytic center that is based on the scaling technique of Edmonds and Karp and is an enhancement of Newton's method. The scaling algorithm runs in O(square-root m log W) iterations, where m is the number of constraints defining the polytope and W is the largest weight given on any constraint. Each iteration involves taking a step in the Newton direction and its complexity is dominated by the time needed to solve a system of linear equations.