Fig. 1: The Grid Search method applied to the White Mountain function: • – evaluation grid, • – centroid, * – optimum.
When it comes down to optimization, Matlab is a great tool. A good review of what is possible with Matlab in terms of optimization can be found here. However, when trying to use optimization routines that can run online in Simulink, at the moment the tools are scarce, especially when dealing with non-linear systems modeled in Simulink. In this post, I will share with you an implementation of the Grid Search optimization routine in Matlab/Simulink. The Grid Search Method from here is an optimization routine that calculates the minimum point of a multi-variable function. This method is based on a grid defined by multiple dimensions. Each dimension has a range of values. Each range is divided into a set of equal-value intervals. The multi-dimensional grid has a centroid which locates the optimum point. The search involves multiple calls. In each call, the method updates the node (point of intersection) with the least function value. This node becomes the new centroid and builds a smaller grid around it. Successive passes end up shrinking the multidimensional grid around the optimum. In Fig. 1, I applied the Grid Search method to the White Mountain function available in Matlab under the name mtWashington.
The White Mountain is a highly non-linear and non-smooth surface with many local minima and maxima. These surfaces are very challenging for gradient-based solvers that can easily get stuck in a local minima or maxima. The Grid Search method is a gradient free approach and from the results we see that successfully finds the global solution with reasonable computational complexity. The Grid Search method uses in general more computational power than other methods, e.g., gradient-based methods, since it requires many function evaluations. However, for some cases when the model is fast, it may be one of the first method to try since it returns the global optimum rather than a local optimum.
With respect to the Simulink implementation, I implemented two versions of the method: with constant bounds and with variable bounds as depicted below.
Fig. 2: Simulink Grid Search implementation with constant and variable bounds, respectively.
The Simulink implementation allows to find the optimum of a unknown function online. This becomes useful in control applications where best operating conditions are desired during the operation of a certain system. I demonstrate below the capabilities of the method through simulation.
Fig. 3: Grid Search method results computed at a sampling rate Ts = 0.5 s.
From Fig. 3, it can be seen that the method successfully finds the three optimum values. Around 600 function evaluations are needed in order to find the optimum with an accuracy of 10e-4. The method can be used online and offline to solve multidimensional problems.
A more detailed description of the method, the source code and example can be downloaded from the links below:
DOWNLOAD REPORT
DOWNLOAD SOURCE CODE AND EXAMPLE
AerDronix 