Rescaling Algorithms for Linear Conic Feasibility

Daniel Dadush (), László A. Végh () and Giacomo Zambelli ()
Additional contact information
Daniel Dadush: Centrum Wiskunde & Informatica, 1098 XG Amsterdam, Netherlands;
László A. Végh: Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom
Giacomo Zambelli: Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom

Mathematics of Operations Research, 2020, vol. 45, issue 2, 732-754

Abstract: We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix A ∈ ℝ m × 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 A T . 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 ( ( m 3 n + m n 2 ) l o g | ρ A | − 1 ) ; if ρ A > 0 , then the image problem is feasible, and the image algorithm runs in time O ( m 2 n 2 ⁡ l o g ⁡ ρ 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 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 + m n 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.

Keywords: linear programming; rescaling; condition measure (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2019.1011 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:2:p:732-754

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().