The nonlinear geometry of linear programming. I: Affine and projective scaling trajectories. (English) Zbl 0671.90045

Bayer, D. A.; Lagarias, J. C.

Trans. Am. Math. Soc. 314, No. 2, 499-526 (1989).

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

MSC:

90C05	Linear programming
52A40	Inequalities and extremum problems involving convexity in convex geometry
34A34	Nonlinear ordinary differential equations and systems

Keywords:

Karmarkar’s projective scaling algorithm; vector field; P-trajectories; affine scaling algorithm; A-trajectories

Citations:

Zbl 0671.90046