You are working with the text-only light edition of "H.Lohninger: Teach/Me Data Analysis, Springer-Verlag, Berlin-New York-Tokyo, 1999. ISBN 3-540-14743-8". Click here for further information.

Optimization Methods
Brute Force Approach

One approach in optimization is straightforward and requires considerable computation power: brute force methods which try to calculate all possible solutions and decide afterwards which one is the best. These methods are feasible only for small problems (in terms of the dimensionality of the phase space), since the number of possible states of the system increases exponentially with the number of dimensions. In the case of continuous predictor variables, the number of states are infinite. Despite these drawbacks, brute force methods do have a few benefits: they are simple to implement, and in the case of discrete systems, all possible states are checked.

As a consequence, brute force methods are often seen as reference methods for calculating the number of states, or the number of calculations necessary to find the optimum with a probability of 100%. Hence, it can be used for the estimation of the effort to solve a problem.

The implementation of brute force algorithms is rather simple. In fact, one only has to try out all possible states of a system. If this is not possible, because the system is described by continuous variables, one has to try all possibilities according to a certain definition of precision for each continuous variable.

Example:

Consider a system which is controlled by 3 continuous predictor variables: x1 to x3: if x1, and x3 need a resolution of 200 intervals, and x2 has to be discretized using 1,000 steps, the resulting number of calculations in a brute force approach will be 200 times 1,000 times 200 = 40,000,000.


Last Update: 2006-Jšn-17