Some Relaxation Methods for Linear Inequalities.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
Some relaxation methods were studied and show, that for any fixed Epsilon 0, there is a bound on the number of arithmetic operations until a point is found satisfying all problem constraints to within Epsilon 0. This bound is of second order in the number of variables and constraints, for problems with a fixed bound on the distance to a feasible solution if any. Two relaxation methods are also proposed here. One of them finds an interior solution to a finite set of linear inequality constraints, if any exists. The other is designed to find approximate solutions to infinite systems of linear inequalities, and does not require that the most violated constraint be found at each iteration.
- Theoretical Mathematics