An Iterative Method for Solving Linear Inequalities

TitleAn Iterative Method for Solving Linear Inequalities
Publication TypeReports
Year of Publication1995
AuthorsStewart G.W
Date Published1995/02/06/
InstitutionDepartment of Computer Science, University of Maryland, College Park
KeywordsTechnical Report

This paper describes and analyzes a method for finding nontrivialsolutions of the inequality $Ax \geq 0$, where $A$ is an $m \times n$
matrix of rank $n$. The method is based on the observation that a
certain function $f$ has a unique minimum if and only if the
inequality {\it fails to have} a nontrivial solution. Moreover, if
there is a solution, an attempt to minimize $f$ will produce a
sequence that will diverge in a direction that converges to a
solution of the inequality. The technique can also be used to solve
inhomogeneous inequalities and hence linear programming problems,
although no claims are made about competitiveness with existing