Non-Random Adaptive Grid Method for High-Speed Optimization of Highly Dimensional, Badly Behaving Real Time Functions

Abstract

The majority of optimization methods lose their applicability when solving highly dimensional functions. The required calculation effort usually becomes enormous as dimensions increase, regardless of the elegance of the method. Most methods concern themselves with finding a single optimum that satisfies the required accuracy, but that provides no quantitative measure (i.e., probability of correctness) indicating whether the true optimum is found. Furthermore, there is usually no exact measure of the calculation effort prior to starting the procedure. There is always an unavoidable coupling (i.e., relation) between the accuracy, probability, and calculation effort of an optimization method, but the exact form of this relation is dependent on the procedures followed to reach optimum. Ideally, an optimization method should facilitate the statement of required accuracy, required probability, and the required calculation effort separately and the method should take care of the rest (i.e., total decoupling of the three requirements). Although this ideal case is generally not possible, it is possible to move toward it by finding procedures that reduce the strength of this unwanted coupling. This report derives simple analytical relations between the required accuracy, probability, and calculation effort of a general multidimensional adaptive grid non-gradient guided (NGG) search method where the search points are generated either decisively or randomly. It is then shown that any adaptive method based on reducing the total solution space is heavily penalized. Further, it is analytically illustrated that if the adaptive grid is randomly generated, it is far less successful than the non-random adaptive grid, because the amount of grid adaptation is less decisive at every step, due to the randomness. As with many optimization techniques, the dimensionality problem limits the application of this method to cases where the function evaluation is real time (~milliseconds) and dimensions are lower than say 25, which occurs in conceptual/preliminary design systems such as CAGED (Shahroudi, 1994b). This method is also particularly useful for problems in which the number of optima is known in advance. In this case the required probability can be set to its minimum value, which is required in order to distinguish an absolute optimum from a known (or likely) number of optima. The coupling relations derived in this report will then provide the minimum calculation effort necessary to satisfy accuracy and probability requirements.