×

A canonical form for pencils of matrices with applications to asymptotic linear programs. (English) Zbl 0841.15007

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 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.
Reviewer: Y.Kuo (Knoxville)

MSC:

15A22 Matrix pencils
90C05 Linear programming
15A21 Canonical forms, reductions, classification

Citations:

Zbl 0675.90049
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbad, M., Perturbation and Stability Theory for Markov Control Problems, (Ph.D. Dissertation (1991), Dept. of Mathematics and Statistics, Univ. of Maryland at Baltimore County) · Zbl 1069.90106
[2] Abbad, M.; Filar, J. A., Perturbation and stability theory for Markov control problems (1990), Unpublished manuscript
[3] Anstreicher, K. M., Generation of Feasible Descent Directions in Continuous Time Linear Programming, (Ph.D. Dissertation (1983), Stanford Univ.,: Stanford Univ., Stanford, Calif.) · Zbl 0955.90085
[4] Beelen, Th.; Van Dooren, P., An improved algorithm for the computation of Kronecker’s canonical form of a singular pencil, Linear Algebra Appl., 105, 9-66 (1988) · Zbl 0645.65022
[5] T. R. Bielecki and J. A. Filar, Singularly perturbed Markov control problem: Limiting average cost, Ann. Oper. Res.; T. R. Bielecki and J. A. Filar, Singularly perturbed Markov control problem: Limiting average cost, Ann. Oper. Res. · Zbl 0744.90096
[6] Blackwell, D., Dynamic programming, Ann. Math. Statist., 33, 719-726 (1962) · Zbl 0133.12906
[7] Campbell, S. L.; Meyer, C. D.; Rose, N. J., Applications of the Drazin inverse to linear systems of differential equations with singular constant coefficients, SIAM J. Appl. Math., 31, 411-425 (1976) · Zbl 0341.34001
[8] Manage. Sci., 10, 98-108 (1963)
[9] Gantmacher, F. R., (The Theory of Matrices, Vols. I, II (1959), Chelsea: Chelsea New York)
[10] Huang, Y.; Veinott, A. F., Markov branching decision chains with interest-rate-dependent rewards (1990), Unpublished manuscript
[11] Jeroslow, R. G., Asymptotic linear programming, Oper. Res., 9, 2, 276-289 (1973) · Zbl 0257.90029
[12] Kågström, B., Matrix Pencils, (Lecture Notes in Math., 973 (1983), Springer-Verlag: Springer-Verlag New York)
[13] Lamond, B. F., A generalized inverse method for asymptotic linear programming, Math. Programming, 23, 71-86 (1989) · Zbl 0675.90049
[14] Lamond, B. F., An efficient basis update for asymptotic linear programming, Linear Algebra Appl., 184, 83-102 (1989) · Zbl 0796.90039
[15] Luenberger, D. G., Time-invariant descriptor systems, Automatica, 14, 473-480 (1978) · Zbl 0398.93040
[16] Miller, B. L.; Veinott, A. F., Discrete dynamic programming with a small interest rate, Ann. Math. Statist., 40, 366-370 (1969) · Zbl 0175.47302
[17] Rothblum, U. G., Multiplicative Markov Decision Chains, (Ph.D. Dissertation (1974), Dept. of Operations Research, Stanford Univ.,: Dept. of Operations Research, Stanford Univ., Stanford, Calif.) · Zbl 0535.90097
[18] Rothblum, U. G., Normalized Markov decision chains I; sensitive decision optimality, Oper. Res., 23, 785-795 (1975) · Zbl 0318.90023
[19] Schweitzer, P.; Stewart, G. W., The Laurent expansion of pencils that are singular at the origin, Linear Algebra Appl., 183, 237-254 (1993) · Zbl 0813.15008
[20] Stoer, J.; Bulirsch, R., Introduction to Numerical Analysis (1980), Springer-Verlag: Springer-Verlag New York · Zbl 0423.65002
[21] Veinott, A. F., Discrete dynamic programming with sensitive discount optimality criteria, Ann. Math. Statist., 40, 1635-1660 (1969) · Zbl 0183.49102
[22] A.F. Veinott, Jr., Markov decision chains, in Stud. Optim.10; A.F. Veinott, Jr., Markov decision chains, in Stud. Optim.10
[23] Wilkinson, J. H., Note on the practical significance of the Drazin inverse, (Campbell, S. L., Recent Applications of Generalized Inverses (1982), Pitman Advanced Publishing Program: Pitman Advanced Publishing Program Boston) · Zbl 0491.65025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.