Support Area Level Set Algorithm For Global Optimization

There are a great number of optimization problems in the fields such as science, engineering, management, economics, and military affairs. Many practical problems in science and engineering can also be formulated as the optimization problems essentially. However, these problems can't be solved effectively by the traditional certainty optimization methods. So seeking effective methods for global optimization has been the mainstream in the field of mathematical programming in recent over twenty years, and it is a hot topic in the research of global optimization. Methods for global optimization have been concerned a lot by many researchers, and they have proposed some methods, especially stochastic optimization methods. Since these methods are straight forward, easy to be understood, stable and without many requirements for object functions.Based on a class of level set algorithms, this paper innovatively proposes a new algorithm—Support Area Level Set Algorithm (SALSA), for global optimization. Regarding the difficulties in making the level set algorithms practical, this method has a set of good solutions for them.In order to clearly illustrate this method, a class of level set methods for global optimization have been concluded and analyzed in the paper. Some main methods have been listed, for example, the integral global optimization by Q. Zheng, the global optimization with discrete mean value-level set by L.S. Zhang, etc. These methods usually need to compute calculus on level set, however obtaining level set is also hard problem. Recent years, many researchers have made some efforts in this field, and proposed several methods in order to substitute level set. Some of them have a great performance to some extend, such as closed box, variable measure grid, etc.The main idea of them is utilizing a substitute formal region to approximate informal distribution of actual level set of thus objective function. Thus, it is hard to improve the performance in its approximation. In this paper, deriving from a distinct ideal, we proposed a novel solution, Support Area Level Set Algorithm (SALSA), which is incorporated with a class of famous statistical learning methods --- Support Vector Machine (SVM). By the use of it, we can successfully convert the level set estimation, which is hard and sometimes is intractable, to a sort of the single class pattern recognition problem. In detail, a set of training samples have been collected by stochastically sampling methods. The element of training set is such sample points of which the objective function values is lower than current level value. In other words, training set is consisted by the stochastic sampling points locating in the level set. Then, we will get a binary discriminate function through training SVM by treating this training set as a single class. Furthermore, this binary discriminate function will lead us to an effective approximation for the actual level set.Since, the process of training SVM is equivalent to find a solution for quadratic programming with linear constrains, and the number of its variables or the size of problem is equal to the size of training set. Hence, our method successfully reduces the complex problems of the informal level set estimation to a quadratic programming problem, and it just requires little computation.However, directly utilizing discriminate function for judging whether or not the sampling points locate in the current level set has following two defects: first, due to the support area's clear boundary, it quite possible to miss some global optima, when support area can't sufficiently cover the actual level set; second, the judgments made by discriminate function still need lots of computational resources.According to the analysis, this paper proposes a new sampling strategy, which is different from others'works, by adopting support vectors (SVs) from estimated support area. This strategy has following advantages: first of all, it combines the fruits of support area for estimating actual level set, and can effectively focus the sampling points in support area in order to improve the proportion of effective sampling points. Meanwhile, this strategy can adaptively adjust according to some specific informal level set's distribution. The next, the allowance of sampling points outside support area largely reduces the possibility of missing global optima.Moreover, this paper also introduces some available stochastic sampling strategies. Unlike them, we proposed a novel method which largely improves the proportion of effective sampling points. However, our sampling strategy can't effective cope with some specific distributions of level set. A modified algorithm have been proposed and successfully solving this problem.After listing some of classic level set algorithms for solving constrained global optimization problem, we successfully extends SALSA to global optimization with constrains through importing the discontinuous punish functions. In its practical implementation, the punish functions convert constrained problems to unconstrained problems, thus SALSA can also be effective in this case.Lots of examples and analysis have been provided to prove our algorithm's efficiency.