Journal
MATHEMATICS
Volume 10, Issue 21, Pages -Publisher
MDPI
DOI: 10.3390/math10213974
Keywords
convex function; convex hull; continuous black-box optimization
Categories
Ask authors/readers for more resources
In this paper, a new method for generating multidimensional convex landscapes is proposed using insights from computational geometry. The proposed generator is generic and does not prefer any specific analytical function.
Heuristic and evolutionary algorithms are proposed to solve challenging real-world optimization problems. In the evolutionary community, many benchmark problems for empirical evaluations of algorithms have been proposed. One of the most important classes of test problems is the class of convex functions, particularly the d-dimensional sphere function. However, the convex function type is somewhat limited. In principle, one can select a set of convex basis functions and use operations that preserve convexity to generate a family of convex functions. This method will inevitably introduce bias in favor of the basis functions. In this paper, the problem is solved by employing insights from computational geometry, which gives the first-ever general-purpose multidimensional convex landscape generator. The new proposed generator has the advantage of being generic, which means that it has no bias toward a specific analytical function. A set of N random d-dimensional points is generated for the construction of a d-dimensional convex hull. The upper part of the convex hull is removed by considering the normal of the polygons. The remaining part defines a convex function. It is shown that the complexity of constructing the function is O(Md-3), where M is the number of polygons of the convex function. For the method to work as a benchmark function, queries of an arbitrary (d - 1) dimensional input are generated, and the generator has to return the value of the convex function. The complexity of answering the query is O(Md). The convexity of the function from the generator is verified with a nonconvex ratio test. The performance of the generator is also evaluated using the Broyden-Fletcher-Goldfarb-Shanno (BFGS) gradient descent algorithm. The source code of the generator is available.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available