Less is More: Simplified Nelder-Mead Method for Large Unconstrained Optimization

  • Kayo Gonçalves Silva Federal University of Rio Grande do Norte
  • Daniel Aloise Ecole Polytechnique de Montreal
  • Samuel Xavier-de-Souza Federal University of Rio Grande do Norte
  • Nenad Mladenovic Serbian Academy of Sciences and Arts

Abstract

Nelder-Mead method (NM) for solving continuous non-linear optimization problem is probably the most cited and used method in the optimization literature and also in practical applications. It belongs to the direct search methods, i.e., they do not use the first and the second order derivatives. The popularity of NM is based on its simplicity. In this paper we propose even more simple algorithm for larger instances that follows NM idea. We call it Simplified NM (SNM): instead of generating all $n+1$ simplex points in $R^n$, we perform search using just $q+1$ vertices, where $q$ is usually much smaller than $n$. Obtained results usually cannot be better than after performing calculations in $n+1$ points as in NM. However, the significant speed-up allow us to run many times SNM from different starting solutions, usually getting better results than those obtained by NM, within the same cpu time. Computational analysis is performed on 10 classical convex and non-convex instances, where the number of variables $n$ can be arbitrarily large. Results obtained show that SNM is more effective than original NM, confirming that LIMA works in solving continuous optimization problem.
Published
Jun 5, 2018
How to Cite
SILVA, Kayo Gonçalves et al. Less is More: Simplified Nelder-Mead Method for Large Unconstrained Optimization. Yugoslav Journal of Operations Research, [S.l.], v. 28, n. 2, p. 153-169, june 2018. ISSN 2334-6043. Available at: <http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/609>. Date accessed: 14 oct. 2019.
Section
Articles