4.3.7.2. Multi-directional Search Algorithm

The multi-directional search (MDS) algorithm is a direct search simplex method that is closely related to Nelder-Mead method, in which non-degenerate simplex of dimension n+1 is updated (for an n-dimensional parameter vector) at each step. The volume enclosed by the simplex reduces until it encloses an extremum of the objective function.

A step in the process begins with stored values of the simplex vertices (parameter vectors) and the associated objective function values. The vertex with the best (minimum) value of the objective function is identified, and a set of n search directions is defined by the edges that connect the best vertex to the remaining vertices in the simplex. The length of each edge defines the length of the associated step in that direction. i.e., the new sample points are obtained by "reflecting" each vertex about the best vertex, with the connecting edge defining the reflection plane normal. The new sample points, together with the previous best vertex, form a new simplex that is accepted for the next iteration if at least one of its vertices has a better objective function value than the previous best vertex. If the simplex is not accepted there is a simple set of expansion and/or contraction steps (wherein the search directions are maintained but the step-size is changed) that are performed to find an acceptable new simplex. The process terminates when the simplex nodes, and the corresponding goal function values, become "close enough". More precisely, the two criteria are:  (4.1)

where δ is a user defined parameter, and NES is the number of experiments in one iteration.

One advantage this method has over Nelder-Mead and some other direct search approaches is that it is inherently parallel, because the processing and function evaluations associated with the different search directions are independent and can be performed simultaneously on different processors.

Analyst exposes several parameters for MDS:

• Contraction Scale Factor - Must be between 0 and 1. Default value is 0.5.

• Expansion Scale Factor - Must be greater than 1. Default value is 2.0.

• Reflection Scale Factor - Must be greater than 0. Default value is 2.0.

 V. Torczon, Multi-Directional Search: A Direct Search Algorithm for Parallel Machines , Ph.D. thesis, Rice University, Huston, TX, May, 1989.

 Nelder, J.A. and Mead, R. " A Simplex Method for Function Minimization." Comput. J. 7, 308-313, 1965.

Please send email to awr.support@ni.com if you would like to provide feedback on this article. Please make sure to include the article link in the email.

Legal and Trademark Notice