zbMATH — the first resource for mathematics

The nonlinear geometry of linear programming. II: Legendre transform coordinates and central trajectories. (English) Zbl 0671.90046
[For part I see the authors, ibid. 314, No.2, 499-526 (1989; Zbl 0671.90045).]
The paper studies a geometric structure underlying two algorithms for solving linear programs: Karmarkar’s projective scaling and the affine scaling algorithm. Both associate to each objective function a vector field, defined on the interior of the feasible solution polytope. By integrating these vector fields one gets sets of trajectories, called P- resp. A-trajectories.
These trajectories are studied using a nonlinear change of coordinates (Legendre transform coordinates), which linearize the A-trajectories; each P-trajectory lies in a plane in Legendre transform coordinates. Both are parts of real algebraic curves. The trajectories through 0 in Legendre transform coordinates are called central trajectories. Power- series expansions for the central A-trajectory are derived and several other characterizations of the central A-trajectory are given.
Reviewer: E.Ederle

90C05 Linear programming
52A40 Inequalities and extremum problems involving convexity in convex geometry
34A34 Nonlinear ordinary differential equations and systems, general theory
Full Text: DOI