The Relaxation Method for Solving Systems of Linear Inequalities

Abstract

The relaxation method for solving systems of inequalities is related both to subgradient optimization and to the relaxation methods used in numerical analysis. The convergence theory depends upon two condition numbers. The first one is used mostly for the study of the rate of geometric convergence. The second is used to define a range of values of the relaxation parameter which guarantees finite convergence. In the case of obtuse polyhedra, finite convergence occurs for any value of the relaxation parameter between one and two. Various relationships between the condition numbers and the concept of obtuseness are established.