Technical Note—The Nested Ball Principle for the Relaxation Method

Publisher Website
Google Scholar
Abstract
In this note, we consider finding a feasible solution to a set of linear inequalities. As is known, there is a ball that can be determined a priori from the problem data knowing the property that it contains a feasible solution if there is one. The relaxation method for solving the problem determines a sequence of shrinking balls that contain a feasible solution if there is one. We show here that if one of the smaller balls is nested inside the first ball, then there is no feasible solution to the problem. This principle is proved to be superior to the existing stopping criterion. We also show that the principle cannot be extended to the Russian method for linear programming.

This publication has 0 references indexed in Scilit: