SURROGATE METHODS FOR LINEAR INEQUALITIES AND LINEAR PROGRAMMING PROBLEMS.

Title: SURROGATE METHODS FOR LINEAR INEQUALITIES AND LINEAR PROGRAMMING PROBLEMS.
Identifier: AAI8401905
identifier: 8401905
Creator: OKO, SELINA OMAGHA.
Contributor: Donald Goldfarb | M. A n s h e l
Date: 1983
Language: English
Publisher: City University of New York.
Subject: Computer Science
Abstract: We consider the problem of finding a point which satisfies a given system of linear inequalities. We present 4 algorithms for solving this problem. All are iterative schemes, and are based upon the orthogonal projection of an infeasible point onto the manifold of the bounding hyperplanes of some of the given constraints. The choice of the constraints and the actual projection are accomplished through the use of 'surrogate' constraints or hyperplanes. Proof of convergence for one of the algorithms that closely resembles a method due to Agmon is given. A general proof is done by means of a monotonic decreasing sequence of continuous functions of the iterates. The algorithms are all adapted to handle equations without replacing them with pairs of inequalities and they can also be used to solve linear programming problems. Three of the algorithms are faster than Agmon's and all 4 can detect inconsistency. The results of computational tests carried out on a variety of problems are reported. Implementations for large sparse matrices are also given.
Type: dissertation
Source: PQT Legacy CUNY.xlsx
degree: Ph.D.
Program: Computer Science

Media: SURROGATE METHODS FOR LINEAR INEQUALITIES AND LINEAR PROGRAMMING PROBLEMS.