×

An approach to fractional programming via d.c. constraints problem: local search. (English) Zbl 1392.90112

Kochetov, Yury (ed.) et al., Discrete optimization and operations research. 9th international conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44913-5/pbk; 978-3-319-44914-2/ebook). Lecture Notes in Computer Science 9869, 404-417 (2016).
Summary: We consider the problem of optimizing the sum of several rational functions via reduction to a problem with d.c. constraints. We propose a method of finding a local solution to the fractional program which can be subsequently used in the global search method based on the global optimality conditions for a problem with nonconvex (d.c.) constraints as it was shown earlier. According to the theory, we construct explicit representations of the constraints in the form of differences of two convex functions and perform a local search method that takes into account the structure of the problem in question. This algorithm was verified on a set of low-dimensional test problems taken from literature as well as on randomly generated problems with up to 200 variables and 200 terms in the sum.
For the entire collection see [Zbl 1346.90008].

MSC:

90C32 Fractional programming
90C26 Nonconvex programming, global optimization
Full Text: DOI