publication . Part of book or chapter of book . 2016

rescaled coordinate descent methods for linear programming

Dadush, Daniel; Végh, László A.; Zambelli, Giacomo;
Open Access
  • Published: 25 May 2016
  • Publisher: Springer International Publishing
  • Country: United Kingdom
Abstract
We propose two simple polynomial-time algorithms to find a positive solution to Ax=0Ax=0 . Both algorithms iterate between coordinate descent steps similar to von Neumann’s algorithm, and rescaling steps. In both cases, either the updating step leads to a substantial decrease in the norm, or we can infer that the condition measure is small and rescale in order to improve the geometry. We also show how the algorithms can be extended to find a solution of maximum support for the system Ax=0Ax=0 , x≥0x≥0 . This is an extended abstract. The missing proofs will be provided in the full version.
Subjects
free text keywords: Linear programming, Coordinate descent, Mathematics, Mathematical proof, Strong duality, Von Neumann architecture, symbols.namesake, symbols, Mathematical optimization, Dual cone and polar cone, QA Mathematics
Download fromView all 2 versions
http://eprints.lse.ac.uk/84479...
Part of book or chapter of book
Provider: UnpayWall
LSE Research Online
Part of book or chapter of book . 2016
http://link.springer.com/conte...
Part of book or chapter of book
Provider: Crossref
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Part of book or chapter of book . 2016

rescaled coordinate descent methods for linear programming

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