Rescaling algorithms for linear conic feasibility

We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix A ∈ Rm×n, the kernel problem requires a positive vector in the kernel of A, and the image problem requires a positive vector in the image of AT. Both algorithms iterate between simple first-order steps and rescaling steps. These rescalings improve natural geometric potentials. If Goffin's condition measure ρA is negative, then the kernel problem is feasible, and the worst-case complexity of the kernel algorithm is O((m3n + mn2)log|ρA|−1); if ρA > 0, then the image problem is feasible, and the image algorithm runs in time O(m2n2 log ρA−1). We also extend the image algorithm to the oracle setting. We address the degenerate case ρA = 0 by extending our algorithms to find maximum support nonnegative vectors in the kernel of A and in the image of AT. In this case, the running time bounds are expressed in the bit-size model of computation: for an input matrix A with integer entries and total encoding length L, the maximum support kernel algorithm runs in time O((m3n + mn2)L), whereas the maximum support image algorithm runs in time O(m2n2L). The standard linear programming feasibility problem can be easily reduced to either maximum support problems, yielding polynomial-time algorithms for linear programming.

• View at Publisher

Free Full Text ( Final Version , 919kb )