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

From MaRDI portal
scientific article
Language Label Description Also known as
English
A canonical form for pencils of matrices with applications to asymptotic linear programs
scientific article

    Statements

    A canonical form for pencils of matrices with applications to asymptotic linear programs (English)
    0 references
    0 references
    29 July 1996
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    asymptotic pencils
    0 references
    linear programs
    0 references
    asymptotic linear programming
    0 references
    Markov decision chains
    0 references
    canonical form
    0 references
    regular pencil of matrices
    0 references
    asymptotic simplex method
    0 references
    0 references
    0 references