Numerical representations of a universal subspace flow for linear programs
(2008) Communications in Information and Systems — Vol. 8, n° 2, p. 71-84 (2008)
Files
No attached file found for this publication.
Details
- Authors
- 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 imes n$ projection matrices of rank $m$, we view it as the set $STmn$ of all full column rank $n imes 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 $ngg 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.
- Affiliations
Citations
Absil, P.-A. (2008). Numerical representations of a universal subspace flow for linear programs. Communications in Information and Systems, 8(2), 71-84. https://doi.org/10.4310/CIS.2008.v8.n2.a2 (Original work published 2008)