On the mixed integer randomized pattern search algorithm

• Autores: Ebert Brea
• Localización: Revista de la Unión Matemática Argentina, ISSN 0041-6932, ISSN-e 1669-9637, Vol. 60, Nº. 2, 2019, págs. 485-503
• Idioma: inglés
• DOI: 10.33044/revuma.v60n2a14
• Enlaces
  • Texto completo (pdf)
• Resumen

  • We analyze the convergence and performance of a novel direct search algorithm for identifying at least a local minimum of unconstrained mixed integer nonlinear optimization problems. The Mixed Integer Randomized Pattern Search Algorithm (MIRPSA), so-called by the author, is based on a randomized pattern search, which is modified by two main operations for finding at least a local minimum of our problem, namely: moving operation and shrinking operation. The convergence properties of the MIRPSA are here analyzed from a Markov chain viewpoint, which is represented by an infinite countable set of states {d(q)}∞q=0, where each state d(q) is defined by a measure of the qth randomized pattern search Hq, for all q ∈ N. According to the algorithm, when a moving operation is carried out on a qth randomized pattern search Hq, the MIRPSA Markov chain holds its state. Meanwhile, if the MIRPSA carries out a shrinking operation on a qth randomized pattern search Hq, the algorithm will then visit the next (q + 1)th state. Since the MIRPSA Markov chain never goes back to any visited state, we therefore say that the MIRPSA yields a birth and miscarriage Markov chain.

• Referencias bibliográficas
  • C. Audet and J. E. Dennis, Jr. Pattern search algorithms for mixed variable programming. SIAM J. Optim. 11 (2000/01), no. 3, 573–594. MR 1814033.
  • E. Brea. Extensiones del método de Nelder Mead a problemas de variables enteras y enteras mixtas. Technical report, Universidad Central de...
  • C. A. Floudas. Nonlinear and mixed-integer optimization: fundamentals and applications. Oxford University Press, New York, 1995.
  • W. E. Hart. A convergence analysis of unconstrained and bound constrained evolutionary pattern search. Evolutionary Computation 9 (2001),...
  • T. G. Kolda, R. M. Lewis, and V. Torczon. Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev....
  • T. G. Kolda, R. M. Lewis, and V. Torczon. Stationarity results for generating set search for linearly constrained optimization. SIAM J. Optim....
  • J. P. Lawrence. Randomized pattern search. IEEE Trans. Comput. 21 (1972), no. 4, 382–385. https://doi.org/10.1109/TC.1972.5008979.
  • J. P. Lawrence and F. P. Emad. An adaptive randomized pattern search. In Proceedings of the 1972 IEEE Conference on Decision and Control and...
  • K. I. M. McKinnon. Convergence of the Nelder–Mead simplex method to a nonstationary point. SIAM J. Optim. 9 (1998), no. 1, 148–158. MR 1662567.
  • R. H. Myers and D. C. Montgomery. Response Surface Methodology: Process and Product Optimization Using Designed Experiments. 2nd edition....
  • V. Torczon. On the convergence of pattern search algorithms. SIAM J. Optim. 7 (1997), no. 1, 1–25. MR 1430554.