Revista de la
Unión Matemática Argentina
On the mixed integer randomized pattern search algorithm
Ebert Brea
Volume 60, no. 2 (2019), pp. 485–503

Download PDF


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}^{\infty}$, where each state $d(q)$ is defined by a measure of the $q$th randomized pattern search $\mathcal{H}_{q}$, for all $q\in\mathbb{N}$. According to the algorithm, when a moving operation is carried out on a $q$th randomized pattern search $\mathcal{H}_{q}$, the MIRPSA Markov chain holds its state. Meanwhile, if the MIRPSA carries out a shrinking operation on a $q$th randomized pattern search $\mathcal{H}_{q}$, 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.