An Improved Algorithm for Linear Inequalities in Pattern Recognition and Switching Theory.

This thesis presents a new iterative algorithm for solving an n by l solution vector w, if one exists, to a set of linear inequalities, A w greater than zero which arises in pattern recognition and switching theory. The algorithm is an extension of the Ho-Kashyap algorithm, utilizing the gradient descent procedure to minimize a criterion function for a solution of the linear inequalities. The criterion function to be minimized is J(Y)=4 Sum(Cosh Yi) (Cosh Yi) where y=A w - b and b is a vector with all positive elements. This criterion function has a larger gradient than previously used and a faster rate of convergence than the Ho-Kashyap algorithm for a certain range of the initial value of b. For problems where a large number of iterations were required for the Ho-Kashyap algorithm, the proposed algorithm reduced the number of iterations by a factor of 20 to 450. The generalization of the proposed algorithm applicable to multi-class pattern classification problems is presented and a convergence proof is given. (RP)