New iterative methods for linear inequalities.

Abstract

In this study we consider the problem of finding a feasible solution $\rm\bar x \in \IR\sp{n}$ to a system of linear inequalities: Ax $\le$ b, where $\rm A \in \IR\sp{m\times n}$ and $\rm b\in \IR\sp{m}.$. Linear inequality problems have many applications in linear programming, image reconstruction, learning theory and so forth. In this dissertation new iterative methods for solving linear inequalities have been developed. Convergence of these algorithms are established and computational results are reported. The first class of these new iterative methods are called 'surrogate constraint methods' since at each iteration, a group of violated constraints is identified and a 'surrogate constraint' is derived from them. Three kinds of surrogate constraint methods have been developed. The first surrogate constraint method is called 'the basic surrogate constraint method', at each iteration of this method all violated constraints are identified and a surrogate constraint is derived by taking a nonnegative combination of them. Then the next point is some point in the line segment joining the current point and its reflection in the hyperplane corresponding to the surrogate constraint. The second surrogate constraint method is called 'the sequential surrogate constraint method', in this method the linear inequality system is partitioned into a number of subsystems, and then surrogate constraint can be derived in each subsystem. These subsystems are solved successively by surrogate constraint method in cyclic order. The third surrogate constraint method is called 'the parallel surrogate constraint method'. In this method surrogate constraints are derived in all the subsystems simultaneously and operations are carried out with current point on each subsystems in a parallel manner. One important application of linear inequality problem, the image reconstruction problem is described in detail and its relationship with linear inequality systems is rigorously established. The extensions of surrogate constraint methods to linear equations and interval linear inequalities are presented. Another new iterative method is developed to find the least squares solution of linear inequality systems. This new algorithm is a revised version of S. P. Han's method which belongs to the class of modified Newton's method. In each iteration of this method, a search direction is found by solving the least squares solution of a linear equation system which consists of a subset of weighted constraints in the original linear inequality system, then the new point is obtained by performing a line search in the search direction from the current point. These new methods have been tested. The computational results are very encouraging.