Advanced Search
Article Contents
Article Contents

Augmented Lagrange primal-dual approach for generalized fractional programming problems

Abstract Related Papers Cited by
  • In this paper, we propose a primal-dual approach for solving the generalized fractional programming problem. The outer iteration of the algorithm is a variant of interval-type Dinkelbach algorithm, while the augmented Lagrange method is adopted for solving the inner min-max subproblems. This is indeed a very unique feature of the paper because almost all Dinkelbach-type algorithms in the literature addressed only the outer iteration, while leaving the issue of how to practically solve a sequence of min-max subproblems untouched. The augmented Lagrange method attaches a set of artificial variables as well as their corresponding Lagrange multipliers to the min-max subproblem. As a result, both the primal and the dual information is available for updating the iterate points and the min-max subproblem is then reduced to a sequence of minimization problems. Numerical experiments show that the primal-dual approach can achieve a better precision in fewer iterations.
    Mathematics Subject Classification: Primary: 49J35, 49N15, 49M37; Secondary: 49K35.


    \begin{equation} \\ \end{equation}
  • [1]

    M. Avriel, E. Diewert, S. Schaible and I. Zang, "Generalized Concavity,'' Society for Industrial and Applied Mathematics, 2010.


    D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods,'' Computer Science and Applied Mathematics, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1982.


    D. P. Bertsekas, "Convex Analysis and Optimization,'' With Angelia Nedié and Asuman E. Ozdaglar, Athena Scientific, Belmont, MA, 2003.


    J. C. Bernard and J. A. Ferland, Convergence of interval-type algorithms for generalized fractional programming, Math. Programming, 43 (1989), 349-363.doi: 10.1007/BF01582298.


    A. I. Barros, J. B. G. Frenk, S. Schaible and S. Zhang, A new algorithm for generalized fractional programs, Mathematical Programming, 72 (1996), 147-175.doi: 10.1007/BF02592087.


    I. Barrodale, M. J. D. Powell and F. D. K. Roberts, The differential correction algorithm for rational $l_{\infty}$-approximation, SIAM J. Numer. Anal., 9 (1972), 493-504.doi: 10.1137/0709044.


    A. Charnes and W. W. Cooper, Programming with linear fractional functionals, Naval Research Logistics Quarterly, 9 (1962), 181-186.doi: 10.1002/nav.3800090303.


    J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207.doi: 10.1007/BF01582887.


    J. P. Crouzeix, J. A. Ferland and S. Schaible, Duality in generalized linear fractional programming, Mathematical Programming, 27 (1983), 342-354.doi: 10.1007/BF02591908.


    J. P. Crouzeix, J. A. Ferland and S. Schaible, An algorithm for generalized fractional programs, Journal of Optimization Theory and Applications, 47 (1985), 35-49.doi: 10.1007/BF00941314.


    S.-H. Chu, "Optimal Resources Allocation for a Cognitive Network," Master's thesis, National Cheng Kung University, Taiwan, ROC, 2009.doi: 10.1007/s11277-012-0657-8.


    B. D. Craven, "Fractional Programming,'' Sigma Series in Applied Mathematics, 4, Heldermann Verlag, Berlin, 1988.


    H. J. Chen, S. Schaible and R. L. Sheu, Generic algorithm for generalized fractional programming, J. Optim. Theory Appl., 141 (2009), 93-105.doi: 10.1007/s10957-008-9499-7.


    W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498.doi: 10.1287/mnsc.13.7.492.


    C. A. Floudas and P. M. Pardalos, eds., "Encyclopedia of Optimization,'' Second edition, Springer, 2009.


    N. Hadjisavvas, S. Komlósi and S. Schaible, eds., "Handbook of generalized convexity and generalized monotonicity,'' Nonconvex Optimization and its Applications, 76, Springer-Verlag, New York, 2005.doi: 10.1007/b101428.


    J. B. Hiriart-Urruty and C. Lemarechal, "Convex Analysis and Minimization Algorithm,'' Springer-Verlag, Berlin, 1994.


    R. Jagannathan, On projective representations of finite abelian groups, in "Number Theory" (Ootacamund, 1984), Lecture Notes in Math., 1122, Springer, Berlin, (1985), 130-139.doi: 10.1007/BFb0075756.


    J. von Neumann, A model of general economic equilibrium, The Review of Economic Studies, 13 (1945), 1-9.doi: 10.2307/2296111.


    E. Polak, J. E. Higgins and D. Q. Mayne, A barrier function method for minimax problems, Math. Program., 54 (1992), 155-176.doi: 10.1007/BF01586049.


    R. T. Rockafellar, "Convex Analysis,'' Reprint of the 1970 original, Princeton Landmarks in Mathematics, Princeton Paperbacks, Princeton University Press, Princeton, NJ, 1997.


    S. Schaible, Fractional programming. I. Duality, Management Science, 22 (1976), 858-867.


    S. Schaible, Multi-ratio fractional programming-a survey, in "Optimization, Parallel Processing and Applications'' (Oberwolfach, 1987 and Karlsruhe, 1987), Lecture Notes in Econom. and Math. Systems, 304, Springer, Berlin, (1988), 57-66.doi: 10.1007/978-3-642-46631-1_7.


    S. Schaible and J. Shi, Recent developments in fractional programming: Single-ratio and max-min case, in "Nonlinear Analysis and Convex Analysis," Yokohama Publ., Yokohama, (2004), 493-506.


    R.-L. Sheu and J.-Y. Lin, Solving continuous min-max problems by an iterative entropic regularization method, J. Optim. Theory Appl., 121 (2004), 597-612.doi: 10.1023/B:JOTA.0000037605.19435.63.


    M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176.doi: 10.2140/pjm.1958.8.171.


    I. M. Stancu-Minasian, Bibliography of fractional programming, 1960-1976, Pure Appl. Math. Sci., 13 (1981), 35-69.


    I. M. Stancu-Minasian, A second bibliography of fractional programming: 1977-1981, Pure Appl. Math. Sci., 17 (1983), 87-102.


    I. M. Stancu-Minasian, A third bibliography of fractional programming, Pure Appl. Math. Sci., 22 (1985), 109-122.


    I. M. Stancu-Minasian, A fourth bibliography of fractional programming, Optimization, 23 (1992), 53-71.doi: 10.1080/02331939208843744.


    I. M. Stancu-Minasian, A fifth bibliography of fractional programming, Dedicated to the memory of Professor Karl-Heinz Elster, Optimization, 45 (1999), 343-367.doi: 10.1080/02331939908844438.


    I. M. Stancu-Minasian, A sixth bibliography of fractional programming, Optimization, 55 (2006), 405-428.doi: 10.1080/02331930600819613.

  • 加载中

Article Metrics

HTML views() PDF downloads(146) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint