Prox-regularization of the dual method of centers for generalized fractional programs. (English) Zbl 1411.90317
Summary: We present in this paper a prox-dual regularization algorithm for solving generalized fractional programming problems. The algorithm combines the dual method of centres for generalized fractional programs and the proximal point algorithm and can handle nondifferentiable convex problems with possibly unbounded feasible constraints set. The proposed procedure generates two sequences of dual and primal values that approximate the optimal value of the considered problem respectively from below and from above at each step. It also generates a sequence of dual solutions that converges to a solution of the dual problem, and a sequence of primal solutions whose every accumulation point is a solution of the primal problem. For a class of problems, including linear fractional programs, the algorithm converges linearly.
MSC:
| 90C30 | Nonlinear programming |
| 90C32 | Fractional programming |
| 49K35 | Optimality conditions for minimax problems |
| 49M29 | Numerical methods involving duality |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
generalized fractional programs; dual method of centres; proximal point algorithm; Lagrange dualityReferences:
| [1] | Barros, A. I.; Frenk, J. B.G.; Schaible, S.; Zhang, S., A new algorithm for generalized fractional programs, Math. Program., 72, 147-175 (1996) · Zbl 0853.90106 |
| [2] | Barros, A. I.; Frenk, J. B.G.; Schaible, S.; Zhang, S., Using duality to solve generalized fractional programming problems, J. Global Optim., 8, 139-170 (1996) · Zbl 0858.90126 · doi:10.1007/BF00138690 |
| [3] | Bector, C. R.; Chandra, S.; Bector, M. K., Generalized fractional programming duality: A parametric approach, J. Optim. Theory Appl., 60, 2, 243-260 (1989) · Zbl 0632.90077 · doi:10.1007/BF00940006 |
| [4] | Boufi, K.; Roubi, A., Dual method of centers for solving generalized fractional programs, To appear in J. Global Optim. · Zbl 1373.90159 · doi:10.1007/s10898-017-0523-z |
| [5] | Buì-Trong-Liêũ; Huard, P., La Méthode des Centres dans un Espace Topologique, Numer. Math., 8, 56-67 (1966) · Zbl 0171.40802 · doi:10.1007/BF02165238 |
| [6] | Crouzeix, J. -P.; Ferland, J. A.; Schaible, S., Duality in generalized linear fractional programming, Math. Program., 27, 342-354 (1983) · Zbl 0526.90083 · doi:10.1007/BF02591908 |
| [7] | Crouzeix, J. P.; Ferland, J. A.; Schaible, S., An algorithm for generalized fractional programs, J. Optim. Theory Appl., 47, 35-49 (1985) · Zbl 0548.90083 · doi:10.1007/BF00941314 |
| [8] | Crouzeix, J. P.; Ferland, J. A.; Schaible, S., A note on an algorithm for generalized fractional programs, J. Optim. Theory Appl., 50, 183-187 (1986) · Zbl 0573.90090 · doi:10.1007/BF00938484 |
| [9] | Dinkelbach, W., On nonlinear fractional programming, Manag. Sci., 13, 2, 492-498 (1967) · Zbl 0152.18402 · doi:10.1287/mnsc.13.7.492 |
| [10] | El Haffari, M.; Roubi, A., Convergence of a proximal algorithm for solving the dual of a generalized fractional program, To appear in RAIRO Oper. Res. · Zbl 1393.90113 · doi:10.1051/ro/2017004 |
| [11] | El Haffari, M.; Roubi, A., Prox-dual regularization algorithm for generalized fractional programs, To appear in J. Ind. Manag. Optim. · Zbl 1373.90160 · doi:10.3934/jimo.2017028 |
| [12] | Evgarov, A.; Andréasson, N.; Patriksson, M., An Introduction to Continuous Optimization: Foundations and Fundamental Algorithms (2006), Studentlitteratur: Studentlitteratur, Lund |
| [13] | Frenk, J.B.G. and Schaible, S., Fractional programming, ERIM Report Series, Reference No. ERS-2004-074-LIS, 2004. |
| [14] | Gugat, M., Prox-regularization methods for generalized fractional programming, J. Optim. Theory Appl., 99, 3, 691-722 (1998) · Zbl 0973.90078 · doi:10.1023/A:1021759318653 |
| [15] | 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 · doi:10.1137/0329022 |
| [16] | Hiriart-Urruty, J-B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms I (1993), Springer-Verlag: Springer-Verlag, Berlin · Zbl 0795.49001 |
| [17] | Huard, P., Programmation Mathématique Convexe, R.I.R.O., 7, 43-59 (1968) · Zbl 0159.48602 · doi:10.1051/m2an/196802R100431 |
| [18] | Jagannathan, R.; Schaible, S., Duality in generalized fractional programming via Farkas lemma, J. Optim. Theory Appl., 41, 3, 417-424 (1983) · Zbl 0502.90079 · doi:10.1007/BF00935361 |
| [19] | Martinet, B., Régularisation d’Inéquations variationnelles par approximation successives, R.I.R.O., 4, 154-158 (1970) · Zbl 0215.21103 · doi:10.1051/m2an/197004R301541 |
| [20] | Moreau, J.-J., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Franc., 93, 273-299 (1965) · Zbl 0136.12101 · doi:10.24033/bsmf.1625 |
| [21] | 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 · doi:10.1051/ro:1999118 |
| [22] | Rockafellar, R. T., Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116 (1976) · Zbl 0402.90076 · doi:10.1287/moor.1.2.97 |
| [23] | Roubi, A., Method of centers for generalized fractional programming, J. Optim. Theory Appl., 107, 1, 123-143 (2000) · Zbl 0964.90045 · doi:10.1023/A:1004660917684 |
| [24] | Roubi, A., Some properties of methods of centers, Comput. Optim. Appl., 19, 319-335 (2001) · Zbl 1009.90083 · doi:10.1023/A:1011264006379 |
| [25] | Roubi, A., Convergence of prox-regularization methods for generalized fractional programming, RAIRO - Oper. Res., 36, 1, 73-94 (2002) · Zbl 1103.90401 · doi:10.1051/ro:2002006 |
| [26] | Schaible, S.; Horst, R.; Pardalos, P. M., Fractional programming · Zbl 0832.90115 |
| [27] | Sion, M., On general minimax theorems, Pacific J. Math., 8, 1, 171-176 (1958) · Zbl 0081.11502 · doi:10.2140/pjm.1958.8.171 |
| [28] | Stancu-Minasian, I. M., A seventh bibliography of fractional programming, Adv. Model. Optim., 15, 2, 309-386 (2013) · Zbl 1413.90282 |
| [29] | Strodiot, J. -J.; Crouzeix, J. -P.; Nguyen, V. H.; Ferland, J. A., An inexact proximal point method for solving generalized fractional programs, J. Global Optim., 42, 1, 121-138 (2008) · Zbl 1193.90200 · doi:10.1007/s10898-007-9270-x |
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.
