A combinatorial approach to piecewise linear time series analysis

Marcelo C. Medeiros, Alvaro Veiga, Mauricio G.C. Resende

Research output: Contribution to journalArticlepeer-review


Over recent years, several nonlinear time series models have been proposed in the literature. One model that has found a large number of successful applications is the threshold autoregressive model (TAR). The TAR model is a piecewise linear process whose central idea is to change the parameters of a linear autoregressive model according to the value of an observable variable, called the threshold variable. If this variable is a lagged value of the time series, the model is called a self-exciting threshold autoregressive (SETAR) model. In this article, we propose a heuristic to estimate a more general SETAR model, where the thresholds are multivariate. We formulate the task of finding multivariate thresholds as a combinatorial optimization problem. We develop an algorithm based on a greedy randomized adaptive search procedure (GRASP) to solve the problem. GRASP is an iterative randomized sampling technique that has been shown to quickly produce good quality solutions for a wide variety of optimization problems. The proposed model performs well on both simulated and real data.

Original languageEnglish (US)
Pages (from-to)236-258
Number of pages23
JournalJournal of Computational and Graphical Statistics
Issue number1
StatePublished - 2002
Externally publishedYes


  • Combinatorial optimization
  • Nonlinear time series analysis
  • Piecewise linear models
  • Search heuristic

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A combinatorial approach to piecewise linear time series analysis'. Together they form a unique fingerprint.

Cite this