20200501
Rescaling algorithms for linear conic feasibility
Publication
Publication
Mathematics of Operations Research , Volume 45  Issue 2 p. 732 754
We propose simple polynomialtime 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 ﬁrstorder steps and rescaling steps. These rescalings improve natural geometric potentials. If Gofﬁn's condition measure ρA is negative, then the kernel problem is feasible, and the worstcase 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 ﬁnd 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 bitsize 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 polynomialtime algorithms for linear programming.
Additional Metadata  

Condition measure, Linear programming, Rescaling  
doi.org/10.1287/moor.2019.1011  
Mathematics of Operations Research  
Organisation  Centrum Wiskunde & Informatica, Amsterdam, The Netherlands 
Dadush, D.N, Végh, L.A, & Zambelli, G. (2020). Rescaling algorithms for linear conic feasibility. Mathematics of Operations Research, 45(2), 732–754. doi:10.1287/moor.2019.1011
