A canonical form for pencils of matrices with applications to asymptotic linear programs
type: Item
instance of: scholarly article
title: A canonical form for pencils of matrices with applications to asymptotic linear programs
zbMATH Open document ID: 0841.15007
DOI: 10.1016/0024-3795(95)00090-9
author: Ying Huang
published in: Linear Algebra and its Applications
publication date: 1996-07-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 15A22
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 15A21
zbMATH DE Number: 847495
zbMATH Keywords: asymptotic pencils
zbMATH Keywords: linear programs
zbMATH Keywords: asymptotic linear programming
zbMATH Keywords: Markov decision chains
zbMATH Keywords: canonical form
zbMATH Keywords: regular pencil of matrices
zbMATH Keywords: asymptotic simplex method
reviewed by: Yueh-er Kuo
MaRDI profile type: Publication
full work available at URL: 0024-3795(95)00090-9
OpenAlex ID: W2047700711
cites work: Hierarchical algorithms for discounted and weighted Markov decision processes
cites work: Linear Programming in O([n3/ln n]L) Operations
cites work: An improved algorithm for the computation of Kronecker's canonical form of a singular pencil
cites work: Singulary perturbed Markov control problem: Limiting average cost
cites work: Discrete Dynamic Programming
cites work: Applications of the Drazin Inverse to Linear Systems of Differential Equations with Singular Constant Coefficients
cites work: Q3254327
cites work: There Cannot be any Algorithm for Integer Programming with Quadratic Constraints
cites work: Matrix pencils. Proceedings of a Conference Held at Pite Havsbad, Sweden, March 22-24, 1982
cites work: A generalized inverse method for asymptotic linear programming
cites work: An efficient basis update for asymptotic linear programming
cites work: Time-invariant descriptor systems
cites work: Discrete Dynamic Programming with a Small Interest Rate
cites work: Multiplicative Markov Decision Chains
cites work: Normalized Markov Decision Chains I; Sensitive Discount Optimality
cites work: The Laurent expansion of pencils that are singular at the origin
cites work: Q3857636
cites work: Discrete Dynamic Programming with Sensitive Discount Optimality Criteria
cites work: Q3953090
Recommended article: Q4805047
Recommended article: A generalized inverse method for asymptotic linear programming
Recommended article: An efficient basis update for asymptotic linear programming
Recommended article: An asymptotic simplex method for singularly perturbed linear programs
Recommended article: Q3750518
Recommended article: Q3082571
Recommended article: Q3328267
Recommended article: Influence of fluid therapy on the haemostatic system of intensive care patients
Recommended article: Q3976779
Recommended article: Q3484647
description: scientific article; zbMATH DE number 847495