A proximal point algorithm for generalized fractional programs. (English) Zbl 1412.90147
Summary: In this paper, the problem of solving generalized fractional programs will be addressed. This problem has been extensively studied and several algorithms have been proposed. In this work, we propose an algorithm that combines the proximal point method with a continuous min-max formulation of discrete generalized fractional programs. The proposed method can handle non-differentiable convex problems with possibly unbounded feasible constraints set, and solves at each iteration a convex program with unique dual solution. It generates two sequences that approximate the optimal value of the considered problem from below and from above at each step. For a class of functions, including the linear case, the convergence rate is at least linear.
MSC:
| 90C32 | Fractional programming |
Keywords:
multi-ratio fractional programs; Dinkelbach-type algorithms; Lagrange duality; proximal point algorithmReferences:
| [1] | Schaible, S.; Horst, R.; Pardalos, PM, Handbook global optimization, Fractional programming, 495-608, (1995), Kluwer, Dordrecht · Zbl 0832.90115 |
| [2] | Nagih, A.; Plateau, G., Problèmes fractionnaires: tour d’horizon sur LES applications et méthodes de résolution, RAIRO – Oper Res, 33, 4, 383-419, (1999) · Zbl 1016.90065 |
| [3] | Frenk, JBG; Schaible, S., Fractional programming, (2004) |
| [4] | Crouzeix, JP; Ferland, JA; Schaible, S., An algorithm for generalized fractional programs, J Optim Theory Appl, 47, 35-49, (1985) · Zbl 0548.90083 |
| [5] | Crouzeix, JP; Ferland, JA; Schaible, S., A note on an algorithm for generalized fractional programs, J Optim Theory Appl, 50, 183-187, (1986) · Zbl 0573.90090 |
| [6] | Crouzeix, JP; Ferland, JA, Algorithms for generalized fractional programming, Math Program, 52, 191-207, (1991) · Zbl 0748.90067 |
| [7] | Crouzeix, JP; Ferland, JA; Schaible, S., Duality in generalized linear fractional programming, Math Program, 27, 342-354, (1983) · Zbl 0526.90083 |
| [8] | Bernard, JC; Ferland, JA, Convergence of interval-type algorithms for generalized fractional programming, Math Program, 43, 349-363, (1989) · Zbl 0677.90074 |
| [9] | Barros, AI; Frenk, JBG; Schaible, S., A new algorithm for generalized fractional programs, Math Program, 72, 147-175, (1996) · Zbl 0853.90106 |
| [10] | Barros, AI; Frenk, JBG; Schaible, S., Using duality to solve generalized fractional programming problems, J Global Optim, 8, 139-170, (1996) · Zbl 0858.90126 |
| [11] | Gugat, M., Prox-regularization methods for generalized fractional programming, J Optim Theory Appl, 99, 3, 691-722, (1998) · Zbl 0973.90078 |
| [12] | Roubi, A., Method of centers for generalized fractional programming, J Optim Theory Appl, 107, 1, 123-143, (2000) · Zbl 0964.90045 |
| [13] | Roubi, A., Convergence of prox-regularization methods for generalized fractional programming, RAIRO Oper Res, 36, 1, 73-94, (2002) · Zbl 1103.90401 |
| [14] | Addou, A.; Roubi, A., Proximal-type methods with generalized Bregman functions and applications to generalized fractional programming, Optimization, 59, 7, 1085-1105, (2010) · Zbl 1208.65080 |
| [15] | Lin, J-Y; Chen, H-J; Sheu, R-L, Augmented Lagrange primal-dual approach for generalized fractional programming problems, J Ind Manage Optim, 4, 9, 723-741, (2013) · Zbl 1276.49024 |
| [16] | Strodiot, JJ; Crouzeix, JP; Nguyen, VH, An inexact proximal point method for solving generalized fractional programs, J Global Optim, 42, 1, 121-138, (2008) · Zbl 1193.90200 |
| [17] | Dinkelbach, W., On nonlinear fractional programming, Manage Sci, 13, 2, 492-498, (1967) · Zbl 0152.18402 |
| [18] | Güler, O., On the convergence of the proximal point algorithm for convex minimization, SIAM J Control Optim, 29, 2, 403-419, (1991) · Zbl 0737.90047 |
| [19] | Sion, M., On general minimax theorems, Pac J Math, 8, 1, 171-176, (1958) · Zbl 0081.11502 |
| [20] | Evgarov, A.; Andréasson, N.; Patriksson, M., An introduction to continuous optimization: foundations and fundamental algorithms, (2006), Studentlitteratur |
| [21] | Ekeland, I.; Temam, R., Analyse convexe et problèmes variationnels, (1974), Gauthier-Villars, Paris, Bruxelles, Montréal · Zbl 0281.49001 |
| [22] | Rockafellar, RT, Convex analysis, (1971), Princeton University Press, Princeton (NJ) |
| [23] | Burke, JV; Ferris, MC, Weak sharp minima in mathematical programming, SIAM J Control Optim, 31, 5, 1340-1359, (1993) · Zbl 0791.90040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
