A Direct Local Search Method and its Application to a Markovian Model

  • Zhivko Taushanov University of Lausanne
  • André Berchtold University of Lausanne
Keywords: Hidden Mixture Transition Distribution (HMTD) model, optimization, heuristic, hill-climbing method, longitudinal data


While the hidden mixture transition distribution (HMTD) model is a powerful framework for the description, analysis, and classification of longitudinal sequences of continuous data, it is notoriously difficult to estimate because of the complexity of its solution space. In this paper, we explore how a new heuristic specifically developed for the HMTD performs compared to different standard optimization algorithms. This specific heuristic can be classified as a hill-climbing method, and different variants are proposed, including a jittering procedure to escape local maxima and measures to speed up the convergence.Different popular approaches are used for comparison, including PSO, SA, GA, NM, L-BFGS-B, and DE. The same HMTD model was optimized on different datasets and the results were compared in terms of both fit to the data and estimated parameters. Even if the complexity of the problem implies that no one algorithm can be considered as an overall best, our heuristic performed well in all situations, leading to useful solutions in terms of both fit and interpretability.


Bendtsen, C. (2012) pso: Particle swarm optimization. R package version 1.0.3. Available on https://cran.r-project.org/web/packages/pso/index.html.

Berchtold A. (2001) Estimation in the mixture transition distribution Model. Journal of Time Series Analysis 22(4): 379-397.

Berchtold, A. (2003) Mixture transition distribution (MTD) modeling of heteroscedastic time series. Computational statistics and data analysis 41(3): 399-411.

Berchtold, A. and Raftery, A. (2002) The mixture transition distribution model for high-order Markov chains and non-Gaussian time series. Statistical Science 17(3): 328-356.

Bolano D. and Berchtold A. (2016) General framework and model building in the class of Hidden Mixture Transition Distribution models. Computational Statistics and Data

Analysis 93: 131-145.

Byrd, R. H., Lu, P., Nocedal, J. and Zhu, C. (1995) A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing 16(5): 1190-1208.

Cerny, V. (1985) Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications 45:41-51.

Elbeltagi, E., Hegazy, T. and Grierson, D. (2005) Comparison among five evolutionary- based optimization algorithms. Advanced Engineering Informatics 19: 43-53.

Fang, L., Chen, P. and Liu S. (2007) Particle swarm optimization with simulated an- nealing for TSP. Proceedings of the 6th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases (AIKED 07).

Holland, J. H. (1992) Genetic algorithms. Scientific American, 267(1): 66-72.

Kennedy, J. and Eberhart, R. (1995) Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks IV: 1942-1948.

Kirkpatrick, S., Gelatt Jr, C. D. and Vecchi, M. P. (1983) Optimization by simulated annealing. Science 220: 671-680.

Matsumoto, M. and Nishimura, T. (1998) Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation 8(1): 3-30.

Mercer, R.E. and Sampson, J.R. (1978) Adaptive search using a reproductive metaplan. Kybernetes 7(3): 215-228.

Mullen, K., Ardia, D., Gil, D., Windover, D. and Cline, J. (2011) DEoptim: an R package for global optimization by differential evolution. Journal of Statistical Software 40(6): 1-26.

Nelder, J.A. and Mead, R. (1965) A simplex method for function minimization. Computer Journal 7: 308-313.

Premalatha, K. and Natarajan, A.M. (2009) Hybrid PSO and GA for global maximization. International Journal of Open Problems in Computer Science and Mathematics 2(4): 597-608.

Pukkala, T. and Kurttila, M. (2005) Examining the performance of six heuristic optimisation techniques in different forest planning problems. Silva Fennica 39(1):67-80.

R Core Team (2015) R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. URL: https://www.R-project.org/.

Rabiner, L. (1989) A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 77(2): 257-286.

Raftery, A. (1985) A model for high-order Markov chains. Journal of the Royal Statistical Society, series B 47(3): 528-539.

Ryden, T. (2008) EM versus Markov chain Monte Carlo for estimation of hidden Markov models: a computational perspective. Bayesian Analysis 3(4): 659-688.

Scott, S. (2002) Bayesian methods for hidden Markov models. Journal of the American Statistical Association 97: 337-351.

Scrucca, L. (2013) GA: A package for genetic algorithms in R. Journal of Statistical Software 53(4).

Shi, Y. and Eberhart, R.C. (1998) A modifed particle swarm optimizer. Proceedings of IEEE International Conference on Evolutionary Computation 69-73.

Singer, S. and Nelder, J. (2009) Nelder-Mead algorithm. Scholarpedia 4(7): 2928.

Srinivas, M. and Patnaik, L. (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on System, Man and Cybernetics 24(4):656-667.

Storn, R. and Price, K. (1997) Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11: 341-359.

Xiang, Y., Gubian, S., Suomela, B. and Hoeng J. (2013) Generalized simulated annealing for global optimization: the GenSA package. The R Journal 5(1).

How to Cite
Taushanov, Z., & Berchtold, A. (2017). A Direct Local Search Method and its Application to a Markovian Model. Statistics, Optimization & Information Computing, 5(1), 19-34. https://doi.org/10.19139/soic.v5i1.253
Research Articles