On the Continuous Trajectories for a Potential Reduction Algorithm for Linear Programming

For a possibly degenerate linear program min_x{c^Tx; Ax = b, x ≥ 0} (A is an m × n real matrix, b ∈ R^m and c ∈ Rⁿ), whose optimal value is 0, we study the limiting behavior of the trajectories of the family of vector fields

Φ_q(x) ≡ −XP_AX [Xc − q^≡1(c^Tx) 1].

for all values of q ≥ n, where X is the diagonal matrix associated with x and P_AX is the projection operator onto the null space of AX. A polynomial algorithm based on the directions Φ_q(x) has been presented by Gonzaga [6] when q = n or q = n + √n. We show that all trajectories of Φ_q(x) 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 Φ_q(x) approaches this vertex along the same direction. When the optimal face consists of more than one point, we show that there is a threshold value τ > 0 such that: for q > τ, “most” of the trajectories of Φ_q(x) converge to the “center” tangentially to the optimal face and that the direction of approach of a trajectory of Φ_q(x) depends on the initial condition: for q < τ (q = τ), the trajectories of Φ_q(x) 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.