Two optimization problems in linear regression with interval data

Abstract

We consider a linear regression model where neither regressors nor the dependent variable is observable; only intervals are available which are assumed to cover the unobservable data points. Our task is to compute tight bounds for the residual errors of minimum-norm estimators of regression parameters with various norms (corresponding to least absolute deviations (LAD), ordinary least squares (OLS), generalized least squares (GLS) and Chebyshev approximation). The computation of the error bounds can be formulated as a pair of max–min and min–min box-constrained optimization problems. We give a detailed complexity-theoretic analysis of them. First, we prove that they are NP-hard in general. Then, further analysis explains the sources of NP-hardness. We investigate three restrictions when the problem is solvable in polynomial time: the case when the parameter space is known apriori to be restricted into a particular orthant, the case when the regression model has a fixed number of regression parameters, and the case when only the dependent variable is observed with errors. We propose a method, called orthant decomposition of the parameter space, which is the main tool for obtaining polynomial-time computability results.

Keywords:

• Linear regression
• interval data
• max–min optimization
• box-constrained optimization
• computational complexity

Acknowledgements

The authors would like to thank Miloš Kopa and Jaromír Antoch (both from Charles University, Prague, Czech Republic).

Notes

No potential conflict of interest was reported by the authors.

1 It is apparent that the positive results of Column II can be strengthened in the following way: for any of the three norms, the value can be computed efficiently when only a fixed number of regression parameters are unrestricted in sign. For example, this holds for the Cobb–Douglas production function , where Y stands for output and stands for the stock of jth production factor. Here it is reasonable to assume that only the parameter is unrestricted in sign, while all coefficients are nonnegative.

Additional information

Funding

The work was supported by the Czech Science Foundation under [grant number P402/13-10660S] (M. Hladík) and [grant number P403/16-00408S] (M. Černý).