A new algorithm for generalized fractional programs

A. I. Barros, J. B.G. Frenk, S. Schaible, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

63 Scopus citations

Abstract

A new dual problem for convex generalized fractional programs with no duality gap is presented and it is shown how this dual problem can be efficiently solved using a parametric approach. The resulting algorithm can be seen as "dual" to the Dinkelbach-type algorithm for generalized fractional programs since it approximates the optimal objective value of the dual (primal) problem from below. Convergence results for this algorithm are derived and an easy condition to achieve superlinear convergence is also established. Moreover, under some additional assumptions the algorithm also recovers at the same time an optimal solution of the primal problem. We also consider a variant of this new algorithm, based on scaling the "dual" parametric function. The numerical results, in case of quadratic-linear ratios and linear constraints, show that the performance of the new algorithm and its scaled version is superior to that of the Dinkelbach-type algorithms. From the computational results it also appears that contrary to the primal approach, the "dual" approach is less influenced by scaling.

Original languageEnglish (US)
Pages (from-to)147-175
Number of pages29
JournalMathematical Programming, Series B
Volume72
Issue number2
DOIs
StatePublished - Feb 1996
Externally publishedYes

Bibliographical note

Funding Information:
* Corresponding author. ’ This research was carried out at the Econometric Institute, Erasmus University, Rotterdam, lands and was supported by J.N.I.C.T. (Portugal) under contract BD/707/90-RM.

Keywords

  • Dinkelbach-type algorithms
  • Duality
  • Fractional programming
  • Generalized fractional programming
  • Karush-Kuhn-Tucker conditions
  • Quasi-convexity

Fingerprint

Dive into the research topics of 'A new algorithm for generalized fractional programs'. Together they form a unique fingerprint.

Cite this