American Institute of Mathematical Sciences

Advanced
  • Previous Article
    An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem
  • JIMO Home
  • This Issue
  • Next Article
    An integrated inventory model with variable transportation cost, two-stage inspection, and defective items
October  2017, 13(4): 1991-2013. doi: 10.3934/jimo.2017028

Prox-dual regularization algorithm for generalized fractional programs

Mostafa El Haffari 1, and  Ahmed Roubi 1,,

1. 

Laboratoire MISI, Faculté des Sciences et Techniques, Univ. Hassan 1,26000 Settat, Morocco

* Corresponding author:Ahmed Roubi

The authors would like to thank the referees for their valuable comments

Received  September 2015 Revised  February 2017 Published  April 2017

Prox-regularization algorithms for solving generalized fractional programs (GFP) were already considered by several authors. Since the standard dual of a generalized fractional program has not generally the form of GFP, these approaches can not apply directly to the dual problem. In this paper, we propose a primal-dual algorithm for solving convex generalized fractional programs. That is, we use a prox-regularization method to the dual problem that generates a sequence of auxiliary dual problems with unique solutions. So we can avoid the numerical difficulties that can occur if the fractional program does not have a unique solution. Our algorithm is based on Dinkelbach-type algorithms for generalized fractional programming, but uses a regularized parametric auxiliary problem. We establish then the convergence and rate of convergence of this new algorithm.

Keywords: Multi-ratio fractional programs, Dinkelbach-type algorithms, Lagrangian duality, proximal point algorithm.
Mathematics Subject Classification: Primary: 90C32, 49N15, 49M29, 49M37; Secondary: 49K35.
Citation: Mostafa El Haffari, Ahmed Roubi. Prox-dual regularization algorithm for generalized fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1991-2013. doi: 10.3934/jimo.2017028
References:
[1]

A. Addou and A. Roubi, Proximal-type methods with generalized bregman functions and applications to generalized fractional programming, Optimization, 59 (2010), 1085-1105.  doi: 10.1080/02331930903395857.  Google Scholar

[2]

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

[3]

A. I. Barros, J. B. G. Frenk, S. Schaible and S. Zhang, Using duality to solve generalized fractional programming problems, Journal of Global Optimization, 8 (1996), 139-170.  doi: 10.1007/BF00138690.  Google Scholar

[4]

J. C. Bernard and J. A. Ferland, Convergence of interval-type algorithms for generalized fractional programming, Mathematical Programming, 43 (1989), 349-363.  doi: 10.1007/BF01582298.  Google Scholar

[5]

J. V. Burke and M. C. Ferris, Weak sharp minima in mathematical programming, SIAM Journal on Control and Optimization, 31 (1993), 1340-1359.  doi: 10.1137/0331063.  Google Scholar

[6]

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

[7]

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

[8]

J. P. Crouzeix, J. A. Ferland and S. Schaible, A note on an algorithm for generalized fractional programs, Journal of Optimization Theory and Applications, 50 (1986), 183-187.  doi: 10.1007/BF00938484.  Google Scholar

[9]

J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207.  doi: 10.1007/BF01582887.  Google Scholar

[10]

W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498.  doi: 10.1287/mnsc.13.7.492.  Google Scholar

[11]

I. Ekeland and R. Temam, Analyse Convexe et Problémes Variationnels, Gauthier-Villars, Paris, Bruxelles, Montréal, 1976.  Google Scholar

[12]

J. B. G. Frenk and S. Schaible, Fractional Programming, in ERIM Report Series, (Reference No. ERS-2004-074-LIS) (2004). Google Scholar

[13]

M. Gugat, Prox-regularization methods for generalized fractional programming, Journal of Optimization Theory and Applications, 99 (1998), 691-722.  doi: 10.1023/A:1021759318653.  Google Scholar

[14]

O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM Journal on Control and Optimization, 29 (1991), 403-419.   Google Scholar

[15]

J.-Y. Lin, H.-J. Chen and R.-L. Sheu, Augmented lagrange primal-dual approach for generalized fractional programming problems, Journal of Industrial and Management Optimization, 4 (2013), 723-741.   Google Scholar

[16]

A. Nagih and G. Plateau, Problémes fractionnaires: Tour d'horizon sur les applications et méthodes de résolution, RAIRO Oper. Res., 33 (1999), 383-419.   Google Scholar

[17]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N. J., 1970.  Google Scholar

[18]

A. Roubi, Method of centers for generalized fractional programming, Journal of Optimization Theory and Applications, 107 (2000), 123-143.  doi: 10.1023/A:1004660917684.  Google Scholar

[19]

A. Roubi, Convergence of prox-regularization methods for generalized fractional programming, RAIRO Oper. Res., 36 (2002), 73-94.  doi: 10.1051/ro:2002006.  Google Scholar

[20]

S. Schaible, Fractional Programming, in Handbook Global Optimization (eds. R. Horst and P. M. Pardalos), Kluwer, Dordrecht, (1995), 495{608 Google Scholar

[21]

M. Sion, On General minimax theorems, Pacific Journal of Mathematics, 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.  Google Scholar

[22]

J. J. Strodiot, J. P. Crouzeix, J. A. Ferland and V. H. Nguyen, An inexact proximal point method for solving generalized fractional programs, Journal of Global Optimization, 42 (2008), 121-138.  doi: 10.1007/s10898-007-9270-x.  Google Scholar

show all references

The authors would like to thank the referees for their valuable comments

References:
[1]

A. Addou and A. Roubi, Proximal-type methods with generalized bregman functions and applications to generalized fractional programming, Optimization, 59 (2010), 1085-1105.  doi: 10.1080/02331930903395857.  Google Scholar

[2]

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

[3]

A. I. Barros, J. B. G. Frenk, S. Schaible and S. Zhang, Using duality to solve generalized fractional programming problems, Journal of Global Optimization, 8 (1996), 139-170.  doi: 10.1007/BF00138690.  Google Scholar

[4]

J. C. Bernard and J. A. Ferland, Convergence of interval-type algorithms for generalized fractional programming, Mathematical Programming, 43 (1989), 349-363.  doi: 10.1007/BF01582298.  Google Scholar

[5]

J. V. Burke and M. C. Ferris, Weak sharp minima in mathematical programming, SIAM Journal on Control and Optimization, 31 (1993), 1340-1359.  doi: 10.1137/0331063.  Google Scholar

[6]

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

[7]

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

[8]

J. P. Crouzeix, J. A. Ferland and S. Schaible, A note on an algorithm for generalized fractional programs, Journal of Optimization Theory and Applications, 50 (1986), 183-187.  doi: 10.1007/BF00938484.  Google Scholar

[9]

J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207.  doi: 10.1007/BF01582887.  Google Scholar

[10]

W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498.  doi: 10.1287/mnsc.13.7.492.  Google Scholar

[11]

I. Ekeland and R. Temam, Analyse Convexe et Problémes Variationnels, Gauthier-Villars, Paris, Bruxelles, Montréal, 1976.  Google Scholar

[12]

J. B. G. Frenk and S. Schaible, Fractional Programming, in ERIM Report Series, (Reference No. ERS-2004-074-LIS) (2004). Google Scholar

[13]

M. Gugat, Prox-regularization methods for generalized fractional programming, Journal of Optimization Theory and Applications, 99 (1998), 691-722.  doi: 10.1023/A:1021759318653.  Google Scholar

[14]

O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM Journal on Control and Optimization, 29 (1991), 403-419.   Google Scholar

[15]

J.-Y. Lin, H.-J. Chen and R.-L. Sheu, Augmented lagrange primal-dual approach for generalized fractional programming problems, Journal of Industrial and Management Optimization, 4 (2013), 723-741.   Google Scholar

[16]

A. Nagih and G. Plateau, Problémes fractionnaires: Tour d'horizon sur les applications et méthodes de résolution, RAIRO Oper. Res., 33 (1999), 383-419.   Google Scholar

[17]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N. J., 1970.  Google Scholar

[18]

A. Roubi, Method of centers for generalized fractional programming, Journal of Optimization Theory and Applications, 107 (2000), 123-143.  doi: 10.1023/A:1004660917684.  Google Scholar

[19]

A. Roubi, Convergence of prox-regularization methods for generalized fractional programming, RAIRO Oper. Res., 36 (2002), 73-94.  doi: 10.1051/ro:2002006.  Google Scholar

[20]

S. Schaible, Fractional Programming, in Handbook Global Optimization (eds. R. Horst and P. M. Pardalos), Kluwer, Dordrecht, (1995), 495{608 Google Scholar

[21]

M. Sion, On General minimax theorems, Pacific Journal of Mathematics, 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.  Google Scholar

[22]

J. J. Strodiot, J. P. Crouzeix, J. A. Ferland and V. H. Nguyen, An inexact proximal point method for solving generalized fractional programs, Journal of Global Optimization, 42 (2008), 121-138.  doi: 10.1007/s10898-007-9270-x.  Google Scholar

Table 1.  The number of iterations and times with $n=5$, $m=5$, $p=5$
$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 62 143 81 4 27 2 9 763 86 114
T(s) 1.20 2.74 1.58 0.10 0.52 0.06 0.20 14.46 1.66 2.15
1 It 69 2 78 2 24 2 3 2 45 86
T(s) 1.25 0.05 1.47 0.05 0.45 0.06 0.07 0.05 0.85 1.58
10-1 It 69 2 78 2 24 2 2 2 31 80
T(s) 1.27 0.05 1.44 0.05 0.44 0.05 0.05 0.05 0.60 1.45
Alg[3] It 73 2 62 2 24 2 2 2 27 79
T(s) 1.18 0.04 1.09 0.04 0.39 0.05 0.04 0.04 0.46 1.27
Table Options

Download as excel

$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 62 143 81 4 27 2 9 763 86 114
T(s) 1.20 2.74 1.58 0.10 0.52 0.06 0.20 14.46 1.66 2.15
1 It 69 2 78 2 24 2 3 2 45 86
T(s) 1.25 0.05 1.47 0.05 0.45 0.06 0.07 0.05 0.85 1.58
10-1 It 69 2 78 2 24 2 2 2 31 80
T(s) 1.27 0.05 1.44 0.05 0.44 0.05 0.05 0.05 0.60 1.45
Alg[3] It 73 2 62 2 24 2 2 2 27 79
T(s) 1.18 0.04 1.09 0.04 0.39 0.05 0.04 0.04 0.46 1.27
Table 2.  The number of iterations and times with $n=10$, $m=10$, $p=5$
$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 328 165 62 50 21 91 6 13 31 225
T(s) 14.65 7.27 3.06 2.23 0.95 4.18 0.31 0.65 1.37 9.84
1 It 235 175 54 37 20 12 3 5 29 243
T(s) 10.38 7.73 2.47 1.70 0.87 0.57 0.22 0.24 1.26 10.59
10-1 It 232 234 53 37 19 5 3 5 29 244
T(s) 10.28 10.25 2.32 1.73 1.06 0.25 0.15 0.24 1.33 10.66
Alg[3] It 253 246 56 39 20 4 3 5 29 249
T(s) 4.70 4.48 1.01 0.68 0.35 0.09 0.06 0.11 0.51 4.50
Table Options

Download as excel

$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 328 165 62 50 21 91 6 13 31 225
T(s) 14.65 7.27 3.06 2.23 0.95 4.18 0.31 0.65 1.37 9.84
1 It 235 175 54 37 20 12 3 5 29 243
T(s) 10.38 7.73 2.47 1.70 0.87 0.57 0.22 0.24 1.26 10.59
10-1 It 232 234 53 37 19 5 3 5 29 244
T(s) 10.28 10.25 2.32 1.73 1.06 0.25 0.15 0.24 1.33 10.66
Alg[3] It 253 246 56 39 20 4 3 5 29 249
T(s) 4.70 4.48 1.01 0.68 0.35 0.09 0.06 0.11 0.51 4.50
Table 3.  The number of iterations and times with $n=20$, $m=10$, $p=5$
$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 87 26 260 24 151 70 50 11 113 62
T(s) 12.10 3.77 31.17 2.84 17.97 8.06 5.75 1.33 13.68 7.41
1 It 87 22 27 24 102 75 50 8 117 58
T(s) 11.38 2.67 3.40 2.78 12.00 8.83 5.87 0.95 14.14 6.77
10-1 It 87 22 8 24 102 75 50 8 122 58
T(s) 10.52 2.58 0.97 2.85 11.88 8.77 5.88 0.95 14.45 7.12
Alg [3] It 91 22 9 24 121 78 51 8 136 59
T(s) 2.01 0.47 0.23 0.54 2.41 1.68 1.05 0.19 3.09 1.24
Table Options

Download as excel

$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 87 26 260 24 151 70 50 11 113 62
T(s) 12.10 3.77 31.17 2.84 17.97 8.06 5.75 1.33 13.68 7.41
1 It 87 22 27 24 102 75 50 8 117 58
T(s) 11.38 2.67 3.40 2.78 12.00 8.83 5.87 0.95 14.14 6.77
10-1 It 87 22 8 24 102 75 50 8 122 58
T(s) 10.52 2.58 0.97 2.85 11.88 8.77 5.88 0.95 14.45 7.12
Alg [3] It 91 22 9 24 121 78 51 8 136 59
T(s) 2.01 0.47 0.23 0.54 2.41 1.68 1.05 0.19 3.09 1.24
Table 4.  The number of iterations and times with $n=50$, $m=10$, $p=5$
$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 35 50 35 26 78 19 39 91 42 109
T(s) 29.75 56.08 46.26 25.62 189.18 13.00 27.19 62.18 29.15 75.01
1 It 20 50 32 26 65 19 21 92 42 103
T(s) 19.07 44.95 29.71 77.36 155.83 12.93 14.44 62.76 29.08 70.70
10-1 It 20 50 32 26 64 19 21 92 42 103
T(s) 16.57 42.72 31.10 48.07 148.04 13.35 14.42 62.74 29.43 69.84
Alg [3] It 20 51 31 26 65 19 21 95 44 98
T(s) 0.76 2.94 1.18 2.25 2.04 0.59 0.61 3.18 1.41 3.37
Table Options

Download as excel

$\alpha$ Problems
1 2 3 4 5 6 7 8 9 10
10 It 35 50 35 26 78 19 39 91 42 109
T(s) 29.75 56.08 46.26 25.62 189.18 13.00 27.19 62.18 29.15 75.01
1 It 20 50 32 26 65 19 21 92 42 103
T(s) 19.07 44.95 29.71 77.36 155.83 12.93 14.44 62.76 29.08 70.70
10-1 It 20 50 32 26 64 19 21 92 42 103
T(s) 16.57 42.72 31.10 48.07 148.04 13.35 14.42 62.74 29.43 69.84
Alg [3] It 20 51 31 26 65 19 21 95 44 98
T(s) 0.76 2.94 1.18 2.25 2.04 0.59 0.61 3.18 1.41 3.37
[1]

Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1897-1920. doi: 10.3934/jimo.2018128
[2]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791
[3]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743
[4]

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027
[5]

Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381
[6]

Xian-Jun Long, Nan-Jing Huang, Zhi-Bin Liu. Optimality conditions, duality and saddle points for nondifferentiable multiobjective fractional programs. Journal of Industrial & Management Optimization, 2008, 4 (2) : 287-298. doi: 10.3934/jimo.2008.4.287
[7]

Gang Li, Yinghong Xu, Zhenhua Qin. Optimality conditions of fenchel-lagrange duality and farkas-type results for composite dc infinite programs. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021019
[8]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153
[9]

Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial & Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004
[10]

Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021151
[11]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[12]

Xinmin Yang, Jin Yang, Heung Wing Joseph Lee. Strong duality theorem for multiobjective higher order nondifferentiable symmetric dual programs. Journal of Industrial & Management Optimization, 2013, 9 (3) : 525-530. doi: 10.3934/jimo.2013.9.525
[13]

Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9
[14]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[15]

Suxiang He, Yunyun Nie. A class of nonlinear Lagrangian algorithms for minimax problems. Journal of Industrial & Management Optimization, 2013, 9 (1) : 75-97. doi: 10.3934/jimo.2013.9.75
[16]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[17]

Mingfang Ding, Yanqun Liu, John Anthony Gear. An improved targeted climbing algorithm for linear programs. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 399-405. doi: 10.3934/naco.2011.1.399
[18]

Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99
[19]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011
[20]

Tim Hoheisel, Maxime Laborde, Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. Journal of Dynamics & Games, 2020, 7 (1) : 79-96. doi: 10.3934/jdg.2020005

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (186)
  • HTML views (473)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy