Sufficient Conditions for the Significance of the Coefficients of Linear Models and the Polynomial-Time Complexity of Their Determination from Data with Interval Uncertainty.

Erokhin, V. I.; Kadochnikov, A. P.; Sotnikov, S. V.

Interval systems of linear algebraic equations (ISLAE) are considered as a tool for constructing linear models based on data with interval uncertainty. Sufficient conditions for the boundedness and convexity of the admissible domain of ISLAE and its belonging to only one orthant of the -dimensional space are proposed that are verifiable in polynomial time by methods of computational linear algebra. In this case, the admissible domain of ISLAE turns out to be a convex bounded polyhedron that lies entirely in some orthant. These properties of the admissible domain of ISLAE allow one, first, to find solutions to the corresponding ISLAE in polynomial time by linear programming methods (while the search for solutions to ISLAE of a general form is an NP-hard problem). Second, the coefficients of the linear model obtained by solving the corresponding ISLAE have an analog of the property of significance of the coefficient of the linear model, since the coefficients of the linear model do not change their sign within the admissible domain of ISLAE. The statement and proof of the corresponding theorem and an illustrative numerical example are presented.

ALGEBRAIC equations; NP-hard problems; LINEAR algebra; LINEAR programming; LINEAR equations

Automation & Remote Control, 2022, Vol 83, Issue 12, p1886

0005-1179

Academic Journal

10.1134/S00051179220120037