Some Relaxation Methods for Linear Inequalities.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1975
- Accession Number
- ADA014637
Entities
People
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University