An Iterative Method for Solving Linear Inequalities

Thumbnail Image

Files

CS-TR-1833.ps (164.16 KB)
No. of downloads: 254
CS-TR-1833.pdf (177.51 KB)
No. of downloads: 1030

Publication or External Link

Date

1995-02-06

Advisor

Citation

DRUM DOI

Abstract

This paper describes and analyzes a method for finding nontrivial solutions 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 methods.

Notes

Rights