IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2408.05665.html
   My bibliography  Save this paper

Change-Point Detection in Time Series Using Mixed Integer Programming

Author

Listed:
  • Artem Prokhorov
  • Peter Radchenko
  • Alexander Semenov
  • Anton Skrobotov

Abstract

We use cutting-edge mixed integer optimization (MIO) methods to develop a framework for detection and estimation of structural breaks in time series regression models. The framework is constructed based on the least squares problem subject to a penalty on the number of breakpoints. We restate the $l_0$-penalized regression problem as a quadratic programming problem with integer- and real-valued arguments and show that MIO is capable of finding provably optimal solutions using a well-known optimization solver. Compared to the popular $l_1$-penalized regression (LASSO) and other classical methods, the MIO framework permits simultaneous estimation of the number and location of structural breaks as well as regression coefficients, while accommodating the option of specifying a given or minimal number of breaks. We derive the asymptotic properties of the estimator and demonstrate its effectiveness through extensive numerical experiments, confirming a more accurate estimation of multiple breaks as compared to popular non-MIO alternatives. Two empirical examples demonstrate usefulness of the framework in applications from business and economic statistics.

Suggested Citation

  • Artem Prokhorov & Peter Radchenko & Alexander Semenov & Anton Skrobotov, 2024. "Change-Point Detection in Time Series Using Mixed Integer Programming," Papers 2408.05665, arXiv.org.
    • Handle: RePEc:arx:papers:2408.05665
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2408.05665
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jushan Bai & Pierre Perron, 1998. "Estimating and Testing Linear Models with Multiple Structural Changes," Econometrica, Econometric Society, vol. 66(1), pages 47-78, January.
    2. Jorda, Oscar, 1999. "Random-Time Aggregation in Partial Adjustment Models," Journal of Business & Economic Statistics, American Statistical Association, vol. 17(3), pages 382-395, July.
    3. Qian, Junhui & Su, Liangjun, 2016. "Shrinkage Estimation Of Regression Models With Multiple Structural Changes," Econometric Theory, Cambridge University Press, vol. 32(6), pages 1376-1433, December.
    4. Ricardo J. Caballero & Eduardo M. R. A. Engel, 1993. "Microeconomic Adjustment Hazards and Aggregate Dynamics," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 108(2), pages 359-383.
    5. Yousef Kaddoura & Joakim Westerlund, 2023. "Estimation of Panel Data Models with Random Interactive Effects and Multiple Structural Breaks when T is Fixed," Journal of Business & Economic Statistics, Taylor & Francis Journals, vol. 41(3), pages 778-790, July.
    6. Steffen Rebennack & Vitaliy Krasko, 2020. "Piecewise Linear Function Fitting via Mixed-Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 507-530, April.
    7. Luc Bauwens & Gary Koop & Dimitris Korobilis & Jeroen V.K. Rombouts, 2015. "The Contribution of Structural Break Models to Forecasting Macroeconomic Series," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 30(4), pages 596-620, June.
    8. Harchaoui, Z. & Lévy-Leduc, C., 2010. "Multiple Change-Point Estimation With a Total Variation Penalty," Journal of the American Statistical Association, American Statistical Association, vol. 105(492), pages 1480-1493.
    9. Garcia, Rene & Perron, Pierre, 1996. "An Analysis of the Real Interest Rate under Regime Shifts," The Review of Economics and Statistics, MIT Press, vol. 78(1), pages 111-125, February.
    10. Luc Bauwens & Gary Koop & Dimitris Korobilis & Jeroen V.K. Rombouts, 2015. "The Contribution of Structural Break Models to Forecasting Macroeconomic Series," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 30(4), pages 596-620, June.
    11. Ngai Hang Chan & Chun Yip Yau & Rong-Mao Zhang, 2014. "Group LASSO for Structural Break Time Series," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 109(506), pages 590-599, June.
    12. Jushan Bai & Pierre Perron, 2003. "Computation and analysis of multiple structural change models," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 18(1), pages 1-22.
    13. Andrés Gómez & Oleg A. Prokopyev, 2021. "A Mixed-Integer Fractional Optimization Approach to Best Subset Selection," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 551-565, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ardia, David & Dufays, Arnaud & Ordás Criado, Carlos, 2023. "Linking Frequentist and Bayesian Change-Point Methods," MPRA Paper 119486, University Library of Munich, Germany.
    2. Karsten Schweikert, 2022. "Oracle Efficient Estimation of Structural Breaks in Cointegrating Regressions," Journal of Time Series Analysis, Wiley Blackwell, vol. 43(1), pages 83-104, January.
    3. Karsten Schweikert, 2020. "Oracle Efficient Estimation of Structural Breaks in Cointegrating Regressions," Papers 2001.07949, arXiv.org, revised Apr 2021.
    4. Alessandro Casini & Pierre Perron, 2018. "Structural Breaks in Time Series," Boston University - Department of Economics - Working Papers Series WP2019-02, Boston University - Department of Economics.
    5. Dufays, Arnaud & Rombouts, Jeroen V.K., 2020. "Relevant parameter changes in structural break models," Journal of Econometrics, Elsevier, vol. 217(1), pages 46-78.
    6. Venkata Jandhyala & Stergios Fotopoulos & Ian MacNeill & Pengyu Liu, 2013. "Inference for single and multiple change-points in time series," Journal of Time Series Analysis, Wiley Blackwell, vol. 34(4), pages 423-446, July.
    7. Muhammad Jaffri Mohd Nasir & Ramzan Nazim Khan & Gopalan Nair & Darfiana Nur, 2024. "Active-set based block coordinate descent algorithm in group LASSO for self-exciting threshold autoregressive model," Statistical Papers, Springer, vol. 65(5), pages 2973-3006, July.
    8. Ma, Chenchen & Tu, Yundong, 2023. "Group fused Lasso for large factor models with multiple structural breaks," Journal of Econometrics, Elsevier, vol. 233(1), pages 132-154.
    9. Czinkota, Thomas, 2012. "Das Halteproblem bei Strukturbrüchen in Finanzmarktzeitreihen [The Halting Problem applied to Structural Breaks in Financial Time Series]," MPRA Paper 37072, University Library of Munich, Germany.
    10. Pierre L. Siklos, 2020. "Looking into the Rear-View Mirror: Lessons from Japan for the Eurozone and the U.S?," IMES Discussion Paper Series 20-E-02, Institute for Monetary and Economic Studies, Bank of Japan.
    11. Rossi, Barbara, 2013. "Advances in Forecasting under Instability," Handbook of Economic Forecasting, in: G. Elliott & C. Granger & A. Timmermann (ed.), Handbook of Economic Forecasting, edition 1, volume 2, chapter 0, pages 1203-1324, Elsevier.
    12. Jesús Clemente & María Dolores Gadea & Antonio Montañés & Marcelo Reyes, 2017. "Structural Breaks, Inflation and Interest Rates: Evidence from the G7 Countries," Econometrics, MDPI, vol. 5(1), pages 1-17, February.
    13. Davis, Richard A. & Hancock, Stacey A. & Yao, Yi-Ching, 2016. "On consistency of minimum description length model selection for piecewise autoregressions," Journal of Econometrics, Elsevier, vol. 194(2), pages 360-368.
    14. Ngai Hang Chan & Chun Yip Yau & Rong-Mao Zhang, 2014. "Group LASSO for Structural Break Time Series," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 109(506), pages 590-599, June.
    15. Jiang, Feiyu & Zhao, Zifeng & Shao, Xiaofeng, 2023. "Time series analysis of COVID-19 infection curve: A change-point perspective," Journal of Econometrics, Elsevier, vol. 232(1), pages 1-17.
    16. Perron, Pierre, 2020. "L'estimation de modèles avec changements structurels multiples," L'Actualité Economique, Société Canadienne de Science Economique, vol. 96(4), pages 789-837, Décembre.
    17. Anwen Yin, 2024. "Predictive model averaging with parameter instability and heteroskedasticity," Bulletin of Economic Research, Wiley Blackwell, vol. 76(2), pages 418-442, April.
    18. Pierre Perron & Yohei Yamamoto, 2016. "On the Usefulness or Lack Thereof of Optimality Criteria for Structural Change Tests," Econometric Reviews, Taylor & Francis Journals, vol. 35(5), pages 782-844, May.
    19. Kevin D. Hoover & Òscar Jordà, 2001. "Measuring systematic monetary policy," Review, Federal Reserve Bank of St. Louis, vol. 83(Jul), pages 113-144.
    20. Hiroshi Yamada & Gawon Yoon, 2016. "Measuring the US NAIRU as a step function," Empirical Economics, Springer, vol. 51(4), pages 1679-1688, December.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2408.05665. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.