The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories

Abstract

Karmarkar's projective scaling algorithm for solving linear programming problems associates to each objective function a vector field defined in the interior of the polytope of feasible solutions of the problem. This paper studies the set of trajectories obtained by integrating this vector field, called P-trajectories, as well as a related set of trajectories, called A-trajectories. The /1-trajectories arise from another linear programming algorithm, the affine scaling algorithm. The affine and projective scaling vector fields are each defined for linear programs of a special form, called standard form and canonical form, respectively.