  


Rescaling Algorithms for Linear Programming Part I: Conic feasibility
Daniel Dadush (dadushcwi.nl) Abstract: We propose simple polynomialtime algorithms for two linear conic feasibility problems. For a matrix $A\in \R^{m\times n}$, the {\em kernel problem} requires a positive vector in the kernel of $A$, and the {\em 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 steps improve natural geometric potentials in the domain and image spaces, respectively. If Goffin's condition measure $\hat \rho_A$ is negative, then the kernel problem is feasible and the worstcase complexity of the kernel algorithm is $O\left((m^3n+mn^2)\log{\hat \rho_A^{1}}\right)$; if $\hat\rho_A>0$, then the image problem is feasible and the image algorithm runs in time $O\left(m^2n^2\log{\hat \rho_A^{1}}\right)$. We also address the degenerate case $\hat\rho_A=0$: we extend our algorithms for finding maximum support nonnegative vectors in the kernel of $A$ and in the image of $A^\top$. We obtain the same running time bounds, with $\hat\rho_A$ replaced by appropriate condition numbers. In case the input matrix $A$ has integer entries and total encoding length $L$, all algorithms are polynomial. Both full support and maximum support kernel algorithms run in time $O\left((m^3n+mn^2)L\right)$, whereas both image algorithms run in time $O\left(m^2n^2L\right)$. The standard linear programming feasibility problem can be easily reduced to either maximum support problems, yielding polynomialtime algorithms for Linear Programming. Keywords: rescaling, linear programming, coordinate descent Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 12/03/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  