zbMATH — the first resource for mathematics

The nonlinear geometry of linear programming. I: Affine and projective scaling trajectories. (English) Zbl 0671.90045
Karmarkar’s projective scaling algorithm for solving linear programming problems uses a vector field, which depends on the objective function and is defined on all points inside the feasible solution polytope. The paper studies the trajectories obtained by integrating this vector field, called P-trajectories, and a related set of trajectories (A- trajectories), which underlies the affine scaling algorithm. After presenting elementary facts about these structures an algebraic relation between P-trajectories and certain A-trajectories is presented. This result implies that the projective scaling algorithm can be regarded as a special case of the affine scaling algorithm.
[For part II see the authors, ibid. 314, No.2, 527-581 (1989; Zbl 0671.90046).]
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