×

Conical partition algorithm for maximizing the sum of dc ratios. (English) Zbl 1090.90186

Summary: The following problem is considered in this paper: \(\max_{x\in d}\{\sum^m_{j=1}g_j(x)|h_j(x)\}\), where \(g_j(x)\geq 0\), and \(h_j(x) > 0\), \(j = 1,\dots,m\), are d.c. (difference of convex) functions over a convex compact set \(D\) in \(R^n\). Specifically, it is reformulated into the problem of maximizing a linear objective function over a feasible region defined by multiple reverse convex functions. Several favorable properties are developed and a branch-and-bound algorithm based on the conical partition and the outer approximation scheme is presented. Preliminary results of numerical experiments are reported on the efficiency of the proposed algorithm.

MSC:

90C32 Fractional programming
90C26 Nonconvex programming, global optimization
65K05 Numerical mathematical programming methods
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benson, H.P. (2001), Using concave envelopes to globally solve the nonlinear sum of ratios problem, Manuscript, Warrington College of Business Administration, University of Florida.
[6] Craven, B.D. (1988), Fractional Programming, Sigma Series in Applied Mathematics 4, Heldermann Verlag. · Zbl 0649.90098
[9] Falk, J.E. and Palocsay, S.W. (1992), Optimizing the sum of linear fractional functions, In: Recent Advances in Global Optimization, Kluwer Academic Publishers, pp. 221-258.
[12] Horst, R. and Pardalos, P.M. (1995), Handbook of Global Optimization, Kluwer Academic Publishers. · Zbl 0805.00009
[13] Horst, R. and Tuy, H. (1993), Global Optimization: Deterministic Approaches, Springer-Verlag. · Zbl 0704.90057
[21] Rockafellar, R.T. and Wets, R.J-R. (1998), Variational Analysis, Springer. · Zbl 0888.49001
[22] Schaible, S. (1973), Fractional programming: transformations, duality and algorithmic aspects, Technical Report 73-79, Department of Operations Research, Stanford University. · Zbl 0307.26010
[24] Schaible, S. (1995), Fractional programming, In: Handbook of Global Optimization, Kluwer Academic Publishers, pp. 495-608. · Zbl 0832.90115
[26] Sekitani, K., Shi, J. and Yamamoto, Y. (1995), General fractional programming: min?max convex?convex quadratic case, In: APORS-Development in Diversity and Harmony, World Scientific, pp. 505-514.
[29] Stancu-Minasian, I.M. (1997), Fractional Programming, Kluwer Academic Publishers. · Zbl 0899.90155
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.