A generalized inverse method for asymptotic linear programming

DOI10.1007/BF01582279MaRDI QIDQ1122475zbMATH OpenOpenAlexFDO

Authors Bernard F. Lamond

Publication date 1989

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01582279

zbMATH Keywords

asymptotic linear programmingDrazin generalized inverseexpansionsLaurent expansion

Mathematics Subject Classification ID

Series expansions (e.g., Taylor, Lidstone series, but not Fourier series) (41A58) Direct numerical methods for linear systems and matrix inversion (65F05) Linear programming (90C05)

Review text

The paper describes an efficient method for computing the solution x(t) of the system of equations \((A+tB)x=b\). It is shown that \textit{J. H. Wilkinson's} factorization [Recent applications of generalized inverses, Res. Notes Math. 66, 82-99 (1982; Zbl 0491.65025)] provides the Laurent expansion of x(t) for the case when both A and B are singular. The series expansion is justified for the following reason: Given a linear programming problem with the constraints \((A+tB)x=b\), one needs to evaluate only a finite number of terms in the series expansions in order to compare the objective function values for two different basic feasible solutions. The author finally claims that the results of the paper show that the arithmetic complexity of asymptotic linear programming [\textit{R. G. Jeroslow}, Oper. Res. 21, 1128-1141 (1973; Zbl 0283.90030)] is much smaller than was previously known.

Recommendations

• An efficient basis update for asymptotic linear programming
• Linear time algorithms for linear programming
• An asymptotic simplex method for singularly perturbed linear programs
• A method of solving the general problem of linear programming
• Linear Programming in O([n3/ln n]L) Operations

Cites work

• An Efficient Factorization for the Group Inverse
• Applications of the Drazin Inverse to Linear Systems of Differential Equations with Singular Constant Coefficients
• Asymptotic Linear Programming
• Discrete Dynamic Programming
• Discrete Dynamic Programming with Sensitive Discount Optimality Criteria
• Generalized Inverses in Discrete Time Markov Decision Processes
• scientific article; zbMATH DE number 3928750 (Why is no real title available?)
• scientific article; zbMATH DE number 3772856 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Pseudo-Inverses in Associative Rings and Semigroups
• Resolvent expansions of matrices and applications

Cited in

(10)

• A further study on inverse linear programming problems
• The asymptotic optimal partition and extensions of the nonsubstitution theorem
• An asymptotic simplex method for singularly perturbed linear programs
• A canonical form for pencils of matrices with applications to asymptotic linear programs
• An efficient basis update for asymptotic linear programming
• Markov branching decision chains with interest-rate-dependent rewards
• Applications of generalized inverses to interval linear programs in hilbert spaces
• Inversion of an analytic operator function through Fredholm quotients and its application
• Laurent expansion of the inverse of perturbed, singular matrices
• Inexact linear programming with generalized technological matrix sets

This page was built for publication: A generalized inverse method for asymptotic linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122475)