Paper ID sheet
- TITLE: Numerical representations of a universal subspace flow for linear programs
- AUTHORS: P.-A. Absil
- ABSTRACT:
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 $\Grassmn$ as the set of all $n\times n$ projection
matrices of rank $m$, we view it as the set $\STmn$ of all full column
rank $n\times m$ matrices, quotiented by the right action of the
general linear group $\GL(m)$. We propose a class of flows in $\STmn$
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 $\STmn$, 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.
- STATUS:
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.
[Home]