# American Institute of Mathematical Sciences

October  2013, 9(4): 723-741. doi: 10.3934/jimo.2013.9.723

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

 1 Department of Applied Mathematics, No.300 Syuefu Rd., Chiayi City 60004, Taiwan 2 Department of Mathematics, No.1, University Road, Tainan City 701, Taiwan, Taiwan

Received  August 2011 Revised  March 2013 Published  August 2013

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.
Citation: Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
##### References:
 [1] M. Avriel, E. Diewert, S. Schaible and I. Zang, "Generalized Concavity,'' Society for Industrial and Applied Mathematics, 2010. Google Scholar [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.  Google Scholar [3] D. P. Bertsekas, "Convex Analysis and Optimization,'' With Angelia Nedié and Asuman E. Ozdaglar, Athena Scientific, Belmont, MA, 2003.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [8] J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207. doi: 10.1007/BF01582887.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [12] B. D. Craven, "Fractional Programming,'' Sigma Series in Applied Mathematics, 4, Heldermann Verlag, Berlin, 1988.  Google Scholar [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.  Google Scholar [14] W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498. doi: 10.1287/mnsc.13.7.492.  Google Scholar [15] C. A. Floudas and P. M. Pardalos, eds., "Encyclopedia of Optimization,'' Second edition, Springer, 2009. Google Scholar [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.  Google Scholar [17] J. B. Hiriart-Urruty and C. Lemarechal, "Convex Analysis and Minimization Algorithm,'' Springer-Verlag, Berlin, 1994. Google Scholar [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.  Google Scholar [19] J. von Neumann, A model of general economic equilibrium, The Review of Economic Studies, 13 (1945), 1-9. doi: 10.2307/2296111.  Google Scholar [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.  Google Scholar [21] R. T. Rockafellar, "Convex Analysis,'' Reprint of the 1970 original, Princeton Landmarks in Mathematics, Princeton Paperbacks, Princeton University Press, Princeton, NJ, 1997.  Google Scholar [22] S. Schaible, Fractional programming. I. Duality, Management Science, 22 (1976), 858-867.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [26] M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176. doi: 10.2140/pjm.1958.8.171.  Google Scholar [27] I. M. Stancu-Minasian, Bibliography of fractional programming, 1960-1976, Pure Appl. Math. Sci., 13 (1981), 35-69.  Google Scholar [28] I. M. Stancu-Minasian, A second bibliography of fractional programming: 1977-1981, Pure Appl. Math. Sci., 17 (1983), 87-102.  Google Scholar [29] I. M. Stancu-Minasian, A third bibliography of fractional programming, Pure Appl. Math. Sci., 22 (1985), 109-122.  Google Scholar [30] I. M. Stancu-Minasian, A fourth bibliography of fractional programming, Optimization, 23 (1992), 53-71. doi: 10.1080/02331939208843744.  Google Scholar [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.  Google Scholar [32] I. M. Stancu-Minasian, A sixth bibliography of fractional programming, Optimization, 55 (2006), 405-428. doi: 10.1080/02331930600819613.  Google Scholar

show all references

##### References:
 [1] M. Avriel, E. Diewert, S. Schaible and I. Zang, "Generalized Concavity,'' Society for Industrial and Applied Mathematics, 2010. Google Scholar [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.  Google Scholar [3] D. P. Bertsekas, "Convex Analysis and Optimization,'' With Angelia Nedié and Asuman E. Ozdaglar, Athena Scientific, Belmont, MA, 2003.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [8] J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207. doi: 10.1007/BF01582887.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [12] B. D. Craven, "Fractional Programming,'' Sigma Series in Applied Mathematics, 4, Heldermann Verlag, Berlin, 1988.  Google Scholar [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.  Google Scholar [14] W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498. doi: 10.1287/mnsc.13.7.492.  Google Scholar [15] C. A. Floudas and P. M. Pardalos, eds., "Encyclopedia of Optimization,'' Second edition, Springer, 2009. Google Scholar [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.  Google Scholar [17] J. B. Hiriart-Urruty and C. Lemarechal, "Convex Analysis and Minimization Algorithm,'' Springer-Verlag, Berlin, 1994. Google Scholar [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.  Google Scholar [19] J. von Neumann, A model of general economic equilibrium, The Review of Economic Studies, 13 (1945), 1-9. doi: 10.2307/2296111.  Google Scholar [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.  Google Scholar [21] R. T. Rockafellar, "Convex Analysis,'' Reprint of the 1970 original, Princeton Landmarks in Mathematics, Princeton Paperbacks, Princeton University Press, Princeton, NJ, 1997.  Google Scholar [22] S. Schaible, Fractional programming. I. Duality, Management Science, 22 (1976), 858-867.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [26] M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176. doi: 10.2140/pjm.1958.8.171.  Google Scholar [27] I. M. Stancu-Minasian, Bibliography of fractional programming, 1960-1976, Pure Appl. Math. Sci., 13 (1981), 35-69.  Google Scholar [28] I. M. Stancu-Minasian, A second bibliography of fractional programming: 1977-1981, Pure Appl. Math. Sci., 17 (1983), 87-102.  Google Scholar [29] I. M. Stancu-Minasian, A third bibliography of fractional programming, Pure Appl. Math. Sci., 22 (1985), 109-122.  Google Scholar [30] I. M. Stancu-Minasian, A fourth bibliography of fractional programming, Optimization, 23 (1992), 53-71. doi: 10.1080/02331939208843744.  Google Scholar [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.  Google Scholar [32] I. M. Stancu-Minasian, A sixth bibliography of fractional programming, Optimization, 55 (2006), 405-428. doi: 10.1080/02331930600819613.  Google Scholar
 [1] Fang Chen, Ning Gao, Yao- Lin Jiang. On product-type generalized block AOR method for augmented linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 797-809. doi: 10.3934/naco.2012.2.797 [2] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51 [3] Jie Zhang, Shuang Lin, Li-Wei Zhang. A log-exponential regularization method for a mathematical program with general vertical complementarity constraints. Journal of Industrial & Management Optimization, 2013, 9 (3) : 561-577. doi: 10.3934/jimo.2013.9.561 [4] Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial & Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733 [5] Jian Hao, Zhilin Li, Sharon R. Lubkin. An augmented immersed interface method for moving structures with mass. Discrete & Continuous Dynamical Systems - B, 2012, 17 (4) : 1175-1184. doi: 10.3934/dcdsb.2012.17.1175 [6] S. Kanagawa, K. Inoue, A. Arimoto, Y. Saisho. Mean square approximation of multi dimensional reflecting fractional Brownian motion via penalty method. Conference Publications, 2005, 2005 (Special) : 463-475. doi: 10.3934/proc.2005.2005.463 [7] Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184 [8] Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196 [9] Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381 [10] Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391 [11] Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053 [12] Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136 [13] Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237 [14] Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems & Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409 [15] Fatemeh Bazikar, Saeed Ketabchi, Hossein Moosaei. Smooth augmented Lagrangian method for twin bounded support vector machine. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021027 [16] Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 [17] Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018 [18] Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1019-1030. doi: 10.3934/jimo.2014.10.1019 [19] Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705 [20] Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241

2020 Impact Factor: 1.801