Paper ID sheet UCL-INMA-2008.030


Numerical representations of a universal subspace flow for linear programs

P.-A. Absil
In 1991, Sonnevend, Stoer, and Zhao [Math.\ Programming 52 (1991) 527--553] have shown that the central paths of strictly feasible instances of linear programs generate curves on the Grassmannian that satisfy a universal ordinary differential equation. Instead of viewing the Grassmannian $\mathrm{Gr}(m,n)$ as the set of all $n\times n$ projection matrices of rank $m$, we view it as the set $\mathbb{R}_*^{m\times n}$ of all full column rank $n\times m$ matrices, quotiented by the right action of the general linear group $\mathrm{GL}(m)$. We propose a class of flows in $\mathbb{R}_*^{m\times n}$ that project to the flow on the Grassmannian. This approach requires much less storage space when $n\gg m$ (i.e., there are many more constraints than variables in the dual formulation). One of the flows in $\mathbb{R}_*^{m\times n}$, that leaves invariant the set of orthonormal matrices, turns out to be a particular version of a matrix differential equation known as Oja's flow. We also point out that the flow in the set of projection matrices admits a double bracket expression.
Key words
Linear programming; Grassmannian; Grassmann manifold; Stiefel manifold; ordinary differential equation; Oja's flow; double bracket flow
Communications in Information and Systems, Special Issue Dedicated to the 70th Birthday of Roger W. Brockett: Part I, Volume 8, Number 2, pp. 71-84, 2008.