Article Contents
Article Contents

# Augmented Lagrange primal-dual approach for generalized fractional programming problems

• 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.

 Citation:

•  [1] M. Avriel, E. Diewert, S. Schaible and I. Zang, "Generalized Concavity,'' Society for Industrial and Applied Mathematics, 2010. [2] D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods,'' Computer Science and Applied Mathematics, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1982. [3] D. P. Bertsekas, "Convex Analysis and Optimization,'' With Angelia Nedié and Asuman E. Ozdaglar, Athena Scientific, Belmont, MA, 2003. [4] 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. [5] 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. [6] 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. [7] A. Charnes and W. W. Cooper, Programming with linear fractional functionals, Naval Research Logistics Quarterly, 9 (1962), 181-186.doi: 10.1002/nav.3800090303. [8] J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207.doi: 10.1007/BF01582887. [9] 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. [10] 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. [11] 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. [12] B. D. Craven, "Fractional Programming,'' Sigma Series in Applied Mathematics, 4, Heldermann Verlag, Berlin, 1988. [13] 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. [14] W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498.doi: 10.1287/mnsc.13.7.492. [15] C. A. Floudas and P. M. Pardalos, eds., "Encyclopedia of Optimization,'' Second edition, Springer, 2009. [16] 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. [17] J. B. Hiriart-Urruty and C. Lemarechal, "Convex Analysis and Minimization Algorithm,'' Springer-Verlag, Berlin, 1994. [18] 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. [19] J. von Neumann, A model of general economic equilibrium, The Review of Economic Studies, 13 (1945), 1-9.doi: 10.2307/2296111. [20] 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. [21] R. T. Rockafellar, "Convex Analysis,'' Reprint of the 1970 original, Princeton Landmarks in Mathematics, Princeton Paperbacks, Princeton University Press, Princeton, NJ, 1997. [22] S. Schaible, Fractional programming. I. Duality, Management Science, 22 (1976), 858-867. [23] 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. [24] 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. [25] 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. [26] M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176.doi: 10.2140/pjm.1958.8.171. [27] I. M. Stancu-Minasian, Bibliography of fractional programming, 1960-1976, Pure Appl. Math. Sci., 13 (1981), 35-69. [28] I. M. Stancu-Minasian, A second bibliography of fractional programming: 1977-1981, Pure Appl. Math. Sci., 17 (1983), 87-102. [29] I. M. Stancu-Minasian, A third bibliography of fractional programming, Pure Appl. Math. Sci., 22 (1985), 109-122. [30] I. M. Stancu-Minasian, A fourth bibliography of fractional programming, Optimization, 23 (1992), 53-71.doi: 10.1080/02331939208843744. [31] 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. [32] I. M. Stancu-Minasian, A sixth bibliography of fractional programming, Optimization, 55 (2006), 405-428.doi: 10.1080/02331930600819613.