Affordable Access

Publisher Website

On relaxation methods for systems of linear inequalities

Authors
Journal
European Journal of Operational Research
0377-2217
Publisher
Elsevier
Publication Date
Volume
9
Issue
2
Identifiers
DOI: 10.1016/0377-2217(82)90071-6
Disciplines
  • Computer Science

Abstract

Abstract In their classical papers Agmon and Motzkin and Schoenberg introduced a relaxation method to find a feasible solution for a system of linear inequalities. So far the method was believed to require infinitely many iterations on some problem instances since it could (depending on the dimension of the set of feasible soltions) converge asymptotically to a feasible solution, if one exists. Hence it could not be used to determine infeasibility. Using two lemma's basic to Khachian's polynomially bounded algorithm we can show that the relaxation method is finite in all cases and thus can handle infeasible systems as well. In spite of more refined stopping criteria the worst case behaviour of the relaxation method is not polynomially bounded as examplified by a class of problems constructed here.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Fast finite methods for a system of linear inequal...

on Computers & Mathematics with A... Jan 01, 1985

New contraction methods for linear inequalities

on Linear Algebra and its Applica... Jan 01, 1994

New iterative methods for linear inequalities

on Journal of Optimization Theory... Jan 01, 1992

New methods for linear inequalities

on Linear Algebra and its Applica... Jan 01, 1982
More articles like this..