A General-Purpose Multi-Dimensional Convex Landscape Generator

Wenwen Liu, Shiu Yin Yuen (), Kwok Wai Chung and Chi Wan Sung
Additional contact information
Wenwen Liu: Department of Electrical Engineering, City University of Hong Kong, Hong Kong, China
Shiu Yin Yuen: Department of Electrical Engineering, City University of Hong Kong, Hong Kong, China
Kwok Wai Chung: Department of Mathematics, City University of Hong Kong, Hong Kong, China
Chi Wan Sung: Department of Electrical Engineering, City University of Hong Kong, Hong Kong, China

Mathematics, 2022, vol. 10, issue 21, 1-14

Abstract: 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 multi-dimensional 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 ( M d 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 ( M d ) . 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.

Keywords: convex function; convex hull; continuous black-box optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/21/3974/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/21/3974/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:21:p:3974-:d:953875

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().