American Institute of Mathematical Sciences

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

Augmented Lagrange primal-dual approach for generalized fractional programming problems

Jen-Yen Lin 1, , Hui-Ju Chen 2, and  Ruey-Lin Sheu 2,

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.
Keywords: exponential penalty method., Generalized fractional program, augmented Lagrange method, Dinkelbach-type algorithm.
Mathematics Subject Classification: Primary: 49J35, 49N15, 49M37; Secondary: 49K3.
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]

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
[2]

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
[3]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[4]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[5]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[6]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[7]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[8]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[9]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[10]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[11]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[12]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[13]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[14]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[15]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[16]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[17]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206
[18]

María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088
[19]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[20]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (95)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences