New iterative methods for linear inequalities.
Yang, Kai
1990
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.Other Identifiers
(UMI)AAI9116332
Subjects
Mathematics Engineering, Industrial Operations Research
Types
Thesis
Metadata
Show full item recordCollections
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.