Skip Navigation

Applied Mathematics Research eXpress (2006) Vol. 2006 : article ID 36581, 24 pages, doi:10.1155/AMRX/2006/36581
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow How to cite this article
Google Scholar
Right arrow Articles by Stefanov, S. M.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Copyright © 2006 Hindawi Publishing Corporation. All rights reserved.

Minimization of a convex linear-fractional separable function subject to a convex inequality constraint or linear inequality constraint and bounds on the variables

Stefan M. Stefanov

Department of Mathematics, South-West University "Neofit Rilski," 2700 Blagoevgrad, Bulgaria E-mail address: stefm{at}aix.swu.bg

We consider the problem of minimizing a convex linear-fractional separable function over a feasible region defined by a convex inequality constraint or linear inequality constraint, and bounds on the variables (box constraints). These problems are interesting from both theoretical and practical points of view because they arise in some mathematical programming problems and in various practical problems. Polynomial algorithms for solving such problems are proposed and their convergence is proved. Some examples and results of numerical experiments are also presented.



References

  1. Almogy Y., Levin O. A class of fractional programming problems. Operations Research (1971) 19:57–67.[Abstract/Free Full Text]
  2. Bajalinov E. B. Linear-Fractional Programming: Theory, Methods, Applications and Software (2003) Dordrecht: Kluwer Academic.
  3. Barros A. I., Frenk J. B. G., Schaible S., Zhang S. A new algorithm for generalized fractional programs. Mathematical Programming, Series A (1996) 72(2):147–175.
  4. Bitran G. R., Hax A. C. Disaggregation and resource allocation using convex knapsack problems with bounded variables. Management Science (1981) 27(4):431–441.[Web of Science]
  5. Bitran G. R., Magnanti T. L. Duality and sensitivity analysis for fractional programs. Operations Research (1976) 24(4):675–699.[Medline]
  6. Cambini A., Martein L., Schaible S. On maximizing a sum of ratios. Journal of Information & Optimization Sciences (1989) 10(1):65–79.
  7. Craven B. D. Fractional Programming. In: Sigma Series in Applied Mathematics (1988) 4. Berlin: Heldermann. 145.
  8. Crouzeix J.-P., Ferland J. A. Algorithms for generalized fractional programming. Mathematical Programming, Series B (1991) 52(2):191–207.[CrossRef]
  9. Crouzeix J.-P., Ferland J. A., Schaible S. Duality in generalized linear fractional programming. Mathematical Programming (1983) 27(3):342–354.[CrossRef][Web of Science]
  10. Crouzeix J.-P., Ferland J. A., Schaible S. An algorithm for generalized fractional programs. Journal of Optimization Theory and Applications (1985) 47(1):35–49.[CrossRef][Web of Science]
  11. Dussault J.-P., Ferland J. A., Lemaire B. Convex quadratic programming with one constraint and bounded variables. Mathematical Programming (1986) 36(1):90–104.[CrossRef][Web of Science]
  12. Falk J. E., Palocsay S. W. Optimizing the sum of linear fractional functions. In: Princeton Ser. Comput. Sci. (1992) Recent Advances in Global Optimization, 1991: Princeton, NJ. New Jersey: Princeton University Press. 221–258.
  13. Goedhart M. H., Spronk J. Financial planning with fractional goals. European Journal of Operational Research (1995) 82(1):111–123.[CrossRef][Web of Science]
  14. Helgason R., Kennington J., Lall H. A polynomially bounded algorithm for a singly constrained quadratic program. Mathematical Programming (1980) 18(3):338–343.[CrossRef][Web of Science]
  15. Ishii H., Ibaraki T., Mine H. Fractional knapsack problems. Mathematical Programming (1977) 13(3):255–271.[CrossRef][Web of Science]
  16. Jagannathan R., Schaible S. Duality in generalized fractional programming via Farkas' lemma. Journal of Optimization Theory and Applications (1983) 41(3):417–424.[CrossRef][Web of Science]
  17. Jo C. L., Kim D. S., Lee G. M. Duality for multiobjective fractional programming involving n-set functions. Optimization (1994) 29(3):205–213.[CrossRef]
  18. Katoh N., Ibaraki T., Mine H. A polynomial time algorithm for the resource allocation problem with a convex objective function. Journal of the Operational Research Society (1979) 30(5):449–455.[CrossRef]
  19. Konno H., Yajima Y. Minimizing and maximizing the product of linear fractional functions. In: Princeton Ser. Comput. Sci. (1992) Recent Advances in Global Optimization, 1991: Princeton, NJ. New Jersey: Princeton University Press. 259–273.
  20. Kornbluth J. S. H., Steuer R. E. Multiple objective linear fractional programming. Management Science (1981) 27(9):1024–1039.[Web of Science]
  21. Luss H., Gupta S. K. Allocation of effort resources among competing activities. Operations Research (1975) 23(2):360–366.[Abstract/Free Full Text]
  22. Martos B. Hyperbolic programming. Naval Research Logistics Quarterly (1964) 11:135–155.[CrossRef][Web of Science]
  23. Mukherjee R. N. Generalized convex duality for multiobjective fractional programs. Journal of Mathematical Analysis and Applications (1991) 162(2):309–316.[CrossRef][Web of Science]
  24. Nemirovskii A. On polynomiality of the method of analytic centers for fractional problems. Mathematical Programming, Series A (1996) 73(2):175–198.
  25. Nemirovskii A. The long-step method of analytic centers for fractional problems. Mathematical Programming, Series B (1997) 77(2):191–224.
  26. Nesterov Yu. E., Nemirovskii A. An interior-point method for generalized linear-fractional programming. Mathematical Programming, Series B (1995) 69(1):177–204.
  27. Nykowski I., Zolkiewski Z. A compromise procedure for the multiple objective linear fractional programming problem. European Journal of Operational Research (1985) 19(1):91–97.[CrossRef][Web of Science]
  28. Saad O. M. An algorithm for solving the integer linear fractional programs. Journal of Information & Optimization Sciences (1993) 14(1):87–93.
  29. Schaible S. Duality in fractional programming: a unified approach. Operations Research (1976) 24(3):452–461.[Abstract/Free Full Text]
  30. Schaible S. Fractional programming: applications and algorithms. European Journal of Operational Research (1981) 7(2):111–120.[CrossRef][Web of Science]
  31. Scott C. H., Jefferson T. R. Fractional programming duality via geometric programming duality. Journal of the Australian Mathematical Society, Series B (1979/1980) 21(4):398–401.
  32. Scott C. H., Jefferson T. R. Convex dual for quadratic concave fractional programs. Journal of Optimization Theory and Applications (1996) 91(1):115–122.[CrossRef][Web of Science]
  33. Sniedovich M. Fractional programming revisited. European Journal of Operational Research (1988) 33(3):334–341.[CrossRef][Web of Science]
  34. Stancu-Minasian I. M. Fractional Programming. Theory, Methods and Applications. In: Mathematics and Its Applications (1997) 409. Dordrecht: Kluwer Academic. viii+418.
  35. Stefanov S. M. On the implementation of stochastic quasigradient methods to some facility location problems. Yugoslav Journal of Operations Research (2000) 10(2):235–256.
  36. Stefanov S. M. Convex separable minimization subject to bounded variables. Computational Optimization and Applications (2001) 18(1):27–48.[CrossRef][Web of Science]
  37. Stefanov S. M. Separable Programming. Theory and Methods. In: Applied Optimization (2001) 53. Dordrecht: Kluwer Academic. xx+314.
  38. Stefanov S. M. Convex quadratic minimization subject to a linear constraint and box constraints. Applied Mathematics Research eXpress (2004) 2004(1):17–42.[Abstract/Free Full Text]
  39. Zipkin P. H. Simple ranking methods for allocation of one resource. Management Science (1980) 26(1):34–43.[Web of Science]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow How to cite this article
Google Scholar
Right arrow Articles by Stefanov, S. M.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?