Rescaling Algorithms for Linear Conic Feasibility

• 成果类型: Article
• 署名作者: Dadush, Daniel; Vegh, Laszlo A.; Zambelli, Giacomo
• 署名单位: University of London; London School Economics & Political Science
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.1011
• 发表日期: 2020
• 页码: 732-754
• 关键词: chubanovs method; perceptron; projection; point; relaxation; systems; numbers

摘要

We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix A is an element of R-mxn, the kernel problem requires a positive vector in the kernel of A, and the image problem requires a positive vector in the image of A(T). Both algorithms iterate between simple first-order steps and resealing steps. These rescalings improve natural geometric potentials. If Goffin's condition measure rho(A) is negative, then the kernel problem is feasible, and the worst-case complexity of the kernel algorithm is O((m(3)n + mn(2))log vertical bar rho(A)vertical bar(-1)); if rho(A) > 0, then the image problem is feasible, and the image algorithm runs in time O(m(2)n(2) log rho(-1)(A)). We also extend the image algorithm to the oracle setting. We address the degenerate case rho(A)= 0 by extending our algorithms to find maximum support nonnegative vectors in the kernel of A and in the image of A(T). 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((m(3)n + mn(2))L), whereas the maximum support image algorithm runs in time O(m(2)n(2)L). The standard linear programming feasibility problem can be easily reduced to either maximum support problems, yielding polynomial-time algorithms for linear programming.