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

[2]

D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods,'', Computer Science and Applied Mathematics, (1982).

[3]

D. P. Bertsekas, "Convex Analysis and Optimization,'', With Angelia Nedié and Asuman E. Ozdaglar, (2003).

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

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

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

[7]

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

[8]

J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming,, Mathematical Programming, 52 (1991), 191. 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. 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. doi: 10.1007/BF00941314.

[11]

S.-H. Chu, "Optimal Resources Allocation for a Cognitive Network,", Master's thesis, (2009). doi: 10.1007/s11277-012-0657-8.

[12]

B. D. Craven, "Fractional Programming,'', Sigma Series in Applied Mathematics, 4 (1988).

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

[14]

W. Dinkelbach, On nonlinear fractional programming,, Management Science, 13 (1967), 492. 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 (2005). doi: 10.1007/b101428.

[17]

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

[18]

R. Jagannathan, On projective representations of finite abelian groups,, in, 1122 (1985), 130. doi: 10.1007/BFb0075756.

[19]

J. von Neumann, A model of general economic equilibrium,, The Review of Economic Studies, 13 (1945), 1. 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. doi: 10.1007/BF01586049.

[21]

R. T. Rockafellar, "Convex Analysis,'', Reprint of the 1970 original, (1970).

[22]

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

[23]

S. Schaible, Multi-ratio fractional programming-a survey,, in, 304 (1988), 57. 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, (2004), 493.

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

[26]

M. Sion, On general minimax theorems,, Pacific J. Math., 8 (1958), 171. 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.

[28]

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

[29]

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

[30]

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

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

[32]

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

show all references

References:
[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, (1982).

[3]

D. P. Bertsekas, "Convex Analysis and Optimization,'', With Angelia Nedié and Asuman E. Ozdaglar, (2003).

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

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

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

[7]

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

[8]

J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming,, Mathematical Programming, 52 (1991), 191. 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. 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. doi: 10.1007/BF00941314.

[11]

S.-H. Chu, "Optimal Resources Allocation for a Cognitive Network,", Master's thesis, (2009). doi: 10.1007/s11277-012-0657-8.

[12]

B. D. Craven, "Fractional Programming,'', Sigma Series in Applied Mathematics, 4 (1988).

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

[14]

W. Dinkelbach, On nonlinear fractional programming,, Management Science, 13 (1967), 492. 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 (2005). doi: 10.1007/b101428.

[17]

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

[18]

R. Jagannathan, On projective representations of finite abelian groups,, in, 1122 (1985), 130. doi: 10.1007/BFb0075756.

[19]

J. von Neumann, A model of general economic equilibrium,, The Review of Economic Studies, 13 (1945), 1. 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. doi: 10.1007/BF01586049.

[21]

R. T. Rockafellar, "Convex Analysis,'', Reprint of the 1970 original, (1970).

[22]

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

[23]

S. Schaible, Multi-ratio fractional programming-a survey,, in, 304 (1988), 57. 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, (2004), 493.

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

[26]

M. Sion, On general minimax theorems,, Pacific J. Math., 8 (1958), 171. 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.

[28]

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

[29]

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

[30]

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

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

[32]

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

[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

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (16)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]