×

Solving linear inequalities in least squares sense. (English) Zbl 0844.65024

The authors describe an algorithm for solving the system of linear inequalities \(Ax\leq b\) in the least squares sense. Assuming the set of observations places upper and lower bounds on linear combinations of the variables, the problem is to find \(x^*\) minimizing \(|(Ax- b)_+|\), where the \(i\)th component of \(v_+\) is the maximum of zero and the \(i\)th component of \(v\).
The only algorithm previously designed for this problem, which necessitates a singular value decomposition of a submatrix of \(A\) at each iteration, is due to S.-P. Han [Tech. Report TR-2141, Univ. of Wisconsin-Madison (1980)]. After presentation of the essential features of Han’s method, this paper describes the current algorithm which makes a minor modification allowing an implementation of the QR algorithm with column pivoting. Comparison of the work entailed with each of the two methods is given.
The paper concludes with a discussion of the new method’s applicability to the linear separability problem.

MSC:

65F10 Iterative numerical methods for linear systems
15A39 Linear inequalities of matrices
90C05 Linear programming
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F30 Other matrix algorithms (MSC2010)
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI