Karmarkar as a Classical Method
In this work we demonstrate that the Karmarkar algorithm for linear programs results from the classical approach of first transforming nonnegativity constraints into equality constraints by adding squared-slack variables and then applying the method of successive linear programming (SLP) to the resulting nonlinear program. Three specific formulations of the SLP method immediately present themselves. One gives the Karmarkar algorithm, one gives the algorithm commonly referred to as the affine scaling variant of the Karmarkar algorithm, and one gives the Karmarkar variant suggested independently by Barnes (1986), Cavalier and Soyster (1985), and Vanderbei, Meketon and Freedman (1985). Employing the understanding gained from these equivalences, we make several observations. By replacing the SLP component with an SQP (successive quadratic programming) component we present a new algorithm and demonstrate that it is locally quadratically convergent, and the problem variables that converge to zero do so q-superlinearly. Finally, we give some general comments on the use of squared-slack variables and a historical overview of the use of square-slack variables in linear programming.
Citable link to this pagehttp://hdl.handle.net/1911/101618
MetadataShow full item record
- CAAM Technical Reports