Rescaling algorithms for linear conic feasibility

DOI10.1287/MOOR.2019.1011MaRDI QIDQ5119854zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Dadush, Giacomo Zambelli, László A. Végh

Publication date 1 September 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06427, https://ir.cwi.nl/pub/30224

zbMATH Keywords

condition measurelinear programmingrescaling

Mathematics Subject Classification ID

Linear programming (90C05)

Abstract: We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix $Ainmathbb{R}^{mimesn}$, 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^{o}p$. Both algorithms iterate between simple first order steps and rescaling steps. These rescalings improve natural geometric potentials. If Goffin's condition measure $h{o}_A$ is negative, then the kernel problem is feasible and the worst-case complexity of the kernel algorithm is $Oleft((m^{3}n+m{n}^2)log|h{o}_A{|}^{-1}ight)$; if $h{o}_A>0$, then the image problem is feasible and the image algorithm runs in time $Oleft(m^2{n}^{2}logh{o}_A^{-1}ight)$. We also extend the image algorithm to the oracle setting. We address the degenerate case $h{o}_A=0$ by extending our algorithms to find maximum support nonnegative vectors in the kernel of $A$ and in the image of $A^{o}p$. 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 $Oleft((m^{3}n+m{n}^2)Light)$, while the maximum support image algorithm runs in time $Oleft(m^2{n}^{2}Light)$. The standard linear programming feasibility problem can be easily reduced to either maximum support problems, yielding polynomial-time algorithms for Linear Programming.

Recommendations

• Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems
• Solving conic systems via projection and rescaling
• A polynomial projection algorithm for linear feasibility problems
• Rescaled coordinate descent methods for linear programming
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem

Cites work

• A deterministic rescaled perceptron algorithm
• A polynomial projection algorithm for linear feasibility problems
• A polynomial projection-type algorithm for linear programming
• A simple polynomial-time rescaling algorithm for solving linear programs
• A smooth perceptron algorithm
• A strongly polynomial algorithm for linear systems having a binary solution
• An efficient rescaled perceptron algorithm for conic systems
• An improved deterministic rescaling for linear programming algorithms
• Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
• Condition numbers for polyhedra with real number data
• Finding the nearest point in A polytope
• Geometric rescaling algorithms for submodular function minimization
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 3189712 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On Chubanov's Method for Linear Programming
• On Chubanov's method for solving a homogeneous inequality system
• On the von Neumann and Frank-Wolfe algorithms with away steps
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
• Rescaled coordinate descent methods for linear programming
• Smooth minimization of non-smooth functions
• Solving conic systems via projection and rescaling
• The Duality Between the Perceptron Algorithm and the von Neumann Algorithm
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Solving Systems of Linear Inequalities
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming

Cited in

(15)

• On linear programming and matrix scaling over the algebraic numbers
• Solving conic systems via projection and rescaling
• A simple method for convex optimization in the oracle model
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• An efficient rescaled perceptron algorithm for conic systems
• Rescaled coordinate descent methods for linear programming
• A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem
• Geometric rescaling algorithms for submodular function minimization
• Computational performance of a projection and rescaling algorithm
• Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems
• Implementation of a projection and rescaling algorithm for second-order conic feasibility problems
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• Minimizing convex functions with rational minimizers
• A simple method for convex optimization in the oracle model
• The colourful feasibility problem

This page was built for publication: Rescaling algorithms for linear conic feasibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5119854)