Constructing Test Sum-of-Ratios Problems and Their Solution by D.C. Programming Approach

Abstract

This paper addresses the problem of fractional optimization with quadratic data. Such problems are, in general, nonconvex and have numerous local extrema. Motivated by the lack of test collections required for experimental verification of new methods for solving this type of fractional programs, we propose two methods for constructing test examples with quadratic functions in the ratios and known global solutions. The first technique is based on a transformation from separable fractions with affine functions into complicated test instances of sum-of-ratios problem with quadratic functions. Furthermore, we propose the procedures in which a nonconvex quadratic (d.c.) problem is cast as a fractional program. This transformation is valid according to the reduction theorem. Both approaches do not require any complicated operations and solving auxiliary problems, except for elementary
operations with matrices and vectors. Finally, we recall the global search algorithm for the general fractional program developed applying the Strekalovsky’s Global Optimization Theory for d.c. programming and show the results on constructed test problems which turn out to be complicated for searching global minima.