An efficient basis update for asymptotic linear programming (Q2365695)

An asymptotic linear program is defined as follows: maximise \(c(t)x\) subject to \(A(t)x= b(t)\), \(x\geq 0\), where the entries \(c(t)\), \(A(t)\) and \(b(t)\) are rational functions of the time parameter \(t\). It is assumed that \(A(t)= G+ tH\), for some fixed matrices \(G\) and \(H\), and that \(c(t)= c\) and \(b(t)= b\), independently of \(t\), for some fixed vectors \(c\) and \(b\). If \(B(t)\) is a basis matrix of \(A(t)\), it is assumed that there exists at least one value \(d\) of \(t\) for which \(B(d)\) is non-singular, in which case there exists a positive value \(T\) of \(t\) such that \(B(t)\) is non-singular for \(t\geq T\). If \(B(t)\) takes the form \(A+ tB\) (with the columns of \(A\) (resp. \(B\)) being columns of \(G\) (resp. \(H\))), it is assumed that the index of \((A,B)\) (defined in the paper) is one. Then there are two non-singular matrices \(U\) and \(V\) such that \[ UAV=\left({A_{11}\atop 0}{0\atop A_{22}}\right)\quad\text{and}\quad UBV=\left({B_{11}\atop 0}{0\atop 0}\right)\tag{1} \] and, for \(t\) large enough, \[ \begin{aligned} V^{-1}(A+ tB)^{- 1} U^{-1} & =\left({0\atop 0}{0\atop A^{-1}_{22}}\right)+ t^{- 1}\left({B^{-1}_{11}\atop 0}{0\atop 0}\right)\\ & - t^{- 2}\left({D_{11} B^{-1}_{11}\atop 0}{0\atop 0}\right)+ t^{- 3}\left({D^ 2_{11} B^{-1}_{11}\atop 0}{0\atop 0}\right)\cdots\end{aligned} \] where \(D_{11}= B^{-1}_{11} A_{11}\). These results can be used to provide a Laurent series for the reduced prices, relative to basis matrix \(B(t)\), and to determine the usual linear programming basic variable/non-basic variable exchanges. The paper is then essentially concerned with an updating procedure for (1), when, given the specified basic variable/non-basic variable interchange, \(A\) (resp. \(B\)) is replaced by \(A+ \alpha w\) (resp. \(B+ \beta w\)) for specified row vector \(w\) and column vector \(\alpha\) and \(\beta\). A procedure involving two phases, I and II, is described, and the number of flops (addition and multiplication operations) is given. Supporting lemmas are given, and special attention is given to infinite horizon stationary uni-chain Markov decision processes, as a special case.