Mathematical Sciences: Homotopy and Null Space Affine       Rescaling Techniques for Linear Programming
{'Code': '03040100', 'Directorate': {'Abbreviation': 'MPS', 'LongName': 'Direct For Mathematical & Physical Scien'}, 'Division': {'Abbreviation': 'DMS', 'LongName': 'Division Of Mathematical Sciences'}}
{'SignBlockName': 'Michael Steuerwalt'}
Within a unified framework made possible by the homotopy                   principle, this project is to formulate, implement and analyse                  new interior point algorithms for linear programming.  Two                      broad classes of algorithms are distinguished.  The first class                 of algorithms path-follow using Euler predictor and Newton                      corrector steps, and develop nonmonotonic iterates.  Here the                   emphasis is on basic formulation, implementation and analysis.                       The second class of algorithms utilize restarts of the                     homotopy.  They develop monotonic iterates, correspond to                       affine rescaling variants of Karmarkar's projective algorithm,                  and mesh well with the simplex algorithm.  This project will                    develop an explicit null-space affine rescaling approach in                     which search directions are computed inexactly.  An iterative                   method is the primary technique used to solve associated linear                 systems.
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8815513.xml'}