# 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, (1982). Google Scholar [3] D. P. Bertsekas, "Convex Analysis and Optimization,'', With Angelia Nedié and Asuman E. Ozdaglar, (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. 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. 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. 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. 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. 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. 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. doi: 10.1007/BF00941314. Google Scholar [11] S.-H. Chu, "Optimal Resources Allocation for a Cognitive Network,", Master's thesis, (2009). doi: 10.1007/s11277-012-0657-8. Google Scholar [12] B. D. Craven, "Fractional Programming,'', Sigma Series in Applied Mathematics, 4 (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. doi: 10.1007/s10957-008-9499-7. Google Scholar [14] W. Dinkelbach, On nonlinear fractional programming,, Management Science, 13 (1967), 492. 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 (2005). doi: 10.1007/b101428. Google Scholar [17] J. B. Hiriart-Urruty and C. Lemarechal, "Convex Analysis and Minimization Algorithm,'', Springer-Verlag, (1994). Google Scholar [18] R. Jagannathan, On projective representations of finite abelian groups,, in, 1122 (1985), 130. doi: 10.1007/BFb0075756. Google Scholar [19] J. von Neumann, A model of general economic equilibrium,, The Review of Economic Studies, 13 (1945), 1. 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. doi: 10.1007/BF01586049. Google Scholar [21] R. T. Rockafellar, "Convex Analysis,'', Reprint of the 1970 original, (1970). Google Scholar [22] S. Schaible, Fractional programming. I. Duality,, Management Science, 22 (1976), 858. Google Scholar [23] S. Schaible, Multi-ratio fractional programming-a survey,, in, 304 (1988), 57. 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, (2004), 493. 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. doi: 10.1023/B:JOTA.0000037605.19435.63. Google Scholar [26] M. Sion, On general minimax theorems,, Pacific J. Math., 8 (1958), 171. 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. Google Scholar [28] I. M. Stancu-Minasian, A second bibliography of fractional programming: 1977-1981,, Pure Appl. Math. Sci., 17 (1983), 87. Google Scholar [29] I. M. Stancu-Minasian, A third bibliography of fractional programming,, Pure Appl. Math. Sci., 22 (1985), 109. Google Scholar [30] I. M. Stancu-Minasian, A fourth bibliography of fractional programming,, Optimization, 23 (1992), 53. 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, 45 (1999), 343. doi: 10.1080/02331939908844438. Google Scholar [32] I. M. Stancu-Minasian, A sixth bibliography of fractional programming,, Optimization, 55 (2006), 405. 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, (1982). Google Scholar [3] D. P. Bertsekas, "Convex Analysis and Optimization,'', With Angelia Nedié and Asuman E. Ozdaglar, (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. 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. 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. 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. 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. 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. 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. doi: 10.1007/BF00941314. Google Scholar [11] S.-H. Chu, "Optimal Resources Allocation for a Cognitive Network,", Master's thesis, (2009). doi: 10.1007/s11277-012-0657-8. Google Scholar [12] B. D. Craven, "Fractional Programming,'', Sigma Series in Applied Mathematics, 4 (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. doi: 10.1007/s10957-008-9499-7. Google Scholar [14] W. Dinkelbach, On nonlinear fractional programming,, Management Science, 13 (1967), 492. 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 (2005). doi: 10.1007/b101428. Google Scholar [17] J. B. Hiriart-Urruty and C. Lemarechal, "Convex Analysis and Minimization Algorithm,'', Springer-Verlag, (1994). Google Scholar [18] R. Jagannathan, On projective representations of finite abelian groups,, in, 1122 (1985), 130. doi: 10.1007/BFb0075756. Google Scholar [19] J. von Neumann, A model of general economic equilibrium,, The Review of Economic Studies, 13 (1945), 1. 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. doi: 10.1007/BF01586049. Google Scholar [21] R. T. Rockafellar, "Convex Analysis,'', Reprint of the 1970 original, (1970). Google Scholar [22] S. Schaible, Fractional programming. I. Duality,, Management Science, 22 (1976), 858. Google Scholar [23] S. Schaible, Multi-ratio fractional programming-a survey,, in, 304 (1988), 57. 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, (2004), 493. 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. doi: 10.1023/B:JOTA.0000037605.19435.63. Google Scholar [26] M. Sion, On general minimax theorems,, Pacific J. Math., 8 (1958), 171. 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. Google Scholar [28] I. M. Stancu-Minasian, A second bibliography of fractional programming: 1977-1981,, Pure Appl. Math. Sci., 17 (1983), 87. Google Scholar [29] I. M. Stancu-Minasian, A third bibliography of fractional programming,, Pure Appl. Math. Sci., 22 (1985), 109. Google Scholar [30] I. M. Stancu-Minasian, A fourth bibliography of fractional programming,, Optimization, 23 (1992), 53. 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, 45 (1999), 343. doi: 10.1080/02331939908844438. Google Scholar [32] I. M. Stancu-Minasian, A sixth bibliography of fractional programming,, Optimization, 55 (2006), 405. 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] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018136 [12] Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019053 [13] 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 [14] 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 [15] 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 [16] Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895 [17] Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012 [18] Piotr Kokocki. Krasnosel'skii type formula and translation along trajectories method on the scale of fractional spaces. Communications on Pure & Applied Analysis, 2015, 14 (6) : 2315-2334. doi: 10.3934/cpaa.2015.14.2315 [19] Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45 [20] Wei Zhu. A numerical study of a mean curvature denoising model using a novel augmented Lagrangian method. Inverse Problems & Imaging, 2017, 11 (6) : 975-996. doi: 10.3934/ipi.2017045

2018 Impact Factor: 1.025