A canonical form for pencils of matrices with applications to asymptotic linear programs (Q1908190)

This paper studies asymptotic pencils of linear programs in which the constraint matrix, right-hand sides and objective function coefficients depend linearly on a parameter, and the author seeks a basis that is optimal for all large enough values of the parameter. The asymptotic linear programming formulation of discounted Markov decision chains has this form, as do many other problems. After an introduction, section 2 gives a new canonical form for a pencil of matrices. It is shown constructively how to reduce a regular pencil of matrices to a canonical form. Section 3 studies the running time of the simplex method using the canonical form. It is shown that the algorithm of this paper finds the \(2m+ 1\) leading terms of the Laurent expansion of the asymptotic solution of \(m\) equations in \(O(m^3)\) time. Section 4 extends \textit{B. F. Lamond's} result [Math. Program., Ser. A 43, No. 1, 71-86 (1989; Zbl 0675.90049)] for comparing two rational functions by showing that all comparisons in the asymptotic simplex method, viz., pricing out nonbasic variables and selecting the entering variable, require only \(2m+ 1\) leading terms of the Laurent expansions of the corresponding quantities. Section 5 provides an estimate for the minimal \(\lambda\)-values to ensure the validity of the asymptotic results.