An Algorithm for the Optimal Solution of Linear Inequalities and its Application to Pattern Recognition

1 December 1973

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-22 (12) , 1065-1075
https://doi.org/10.1109/t-c.1973.223652

Abstract

An algorithm for the optimal solution of consistent and inconsistent linear inequalities is presented, where the optimality criterion is the maximization of the number of satisfied constraints. The algorithm is developed as a nonenumerative search procedure based on two new theorems established in this paper. It is shown that the number of iterative steps before termination is strictly less than that required by an exhaustive search. Experimental results with various types of data establish the computational tractability of the procedure under nontrivial conditions.

Keywords

This publication has 10 references indexed in Scilit:

What is a Convex Set?
The American Mathematical Monthly, 1971
Convex Analysis
Published by Walter de Gruyter GmbH ,1970
Solution of Linear Inequalities
IEEE Transactions on Computers, 1970
Adaptive Linear Classifier by Linear Programming
IEEE Transactions on Systems Science and Cybernetics, 1970
Comment on "Pattern Classification Design by Linear Programming"
IEEE Transactions on Computers, 1969
Pattern Classifier Design by Linear Programming
IEEE Transactions on Computers, 1968
On pattern classification algorithms introduction and survey
Proceedings of the IEEE, 1968
A Class of Iterative Procedures for Linear Inequalities
SIAM Journal on Control, 1966
An Algorithm for Linear Inequalities and its Applications
IEEE Transactions on Electronic Computers, 1965
Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition
IEEE Transactions on Electronic Computers, 1965