Boundedness theorems for the relaxation method

• 成果类型: Article
• 署名作者: Amaldi, E; Hauser, R
• 署名单位: Polytechnic University of Milan; University of Oxford
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0164
• 发表日期: 2005
• 页码: 939-955
• 关键词: systems

摘要

A classical theorem by Block and Levin (Block, H. D., S. A. Levin. 1970. On the boundedness of an iterative procedure for solving a system of linear inequalities. Proc. Amer Math. Soc. 26 229-235) states that certain variants of the relaxation method for solving systems of linear inequalities generate bounded sequences of intermediate solutions, even when applied to infeasible systems. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying the bound as a function of the input data.