On the continuous trajectories for a potential reduction algorithm for linear programming

For a possibly degenerate linear program (A is an real matrix, and ), whose optimal value is 0, a study is made of the limiting behavior of the trajectories of the family of vector fields , for all values of , where X is the diagonal matrix associated with x and P A X is the projection operator onto the null space of AX. A polynomial algorithm based on the directions has been presented by Gonzaga when or . This paper shows that all trajectories of converge to the unique ‘center’ of the optimal face of the given linear program. When this face consists of a unique vertex, it is shown that any trajectory of approaches is vertex along the same direction. When the optimal face consists of more than one point, it shows that there is a threshold value such that: for , ‘most’ of the trajectories of converge to the ‘center’ tangentially to the optimal face and that the direction of approach of a trajectory of depends on the initial condition; for , the trajectories of converge to the ‘center’ along a unique direction (along several directions which depend on the initial condition) forming a positive angle with the optimal face.