Milan Hladík and Michal Černý. Two optimization problems in linear regression with interval data. Optim., 66(3):331–349, 2017.
[PDF] [gzipped postscript] [postscript] [HTML]
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.
Theorems 6.3 and 8.2 are incorrect.
@article{HlaCer2017a,
author = "Milan Hlad\'{\i}k and Michal {\v{C}}ern\'{y}",
title = "Two optimization problems in linear regression with interval data",
journal = "Optim.",
fjournal = "Optimization",
volume = "66",
number = "3",
pages = "331-349",
year = "2017",
doi = "10.1080/02331934.2016.1274988",
issn = "0233-1934",
bib2html_dl_html = "http://www.tandfonline.com/doi/full/10.1080/02331934.2016.1274988",
bib2html_errata = "Theorems 6.3 and 8.2 are incorrect.",
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",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44