Convergence of a proximal algorithm for solving the dual of a generalized fractional program
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 4, pp. 985-1004.

We propose to use the proximal point algorithm to regularize a “dual” problem of generalized fractional programs (GFP). The proposed technique leads to a new dual algorithm that generates a sequence which converges from below to the minimal value of the considered problem. At each step, the proposed algorithm solves approximately an auxiliary problem with a unique dual solution whose every cluster point gives a solution to the dual problem. In the exact minimization case, the sequence of dual solutions converges to an optimal dual solution. For a class of functions, including the linear case, the convergence of the dual values is at least linear.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017004
Classification : 90C30, 90C32, 49K35, 49M29, 49M37
Mots clés : Multi-ratio fractional programs, Dinkelbach-type algorithms, Lagrange duality, proximal point algorithm
El Haffari, Mostafa 1 ; Roubi, Ahmed 1

1 Faculté des Sciences et Techniques, Settat, Morocco.
@article{RO_2017__51_4_985_0,
     author = {El Haffari, Mostafa and Roubi, Ahmed},
     title = {Convergence of a proximal algorithm for solving the dual of a generalized fractional program},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {985--1004},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {4},
     year = {2017},
     doi = {10.1051/ro/2017004},
     mrnumber = {3783931},
     zbl = {1393.90113},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2017004/}
}
TY  - JOUR
AU  - El Haffari, Mostafa
AU  - Roubi, Ahmed
TI  - Convergence of a proximal algorithm for solving the dual of a generalized fractional program
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 985
EP  - 1004
VL  - 51
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2017004/
DO  - 10.1051/ro/2017004
LA  - en
ID  - RO_2017__51_4_985_0
ER  - 
%0 Journal Article
%A El Haffari, Mostafa
%A Roubi, Ahmed
%T Convergence of a proximal algorithm for solving the dual of a generalized fractional program
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 985-1004
%V 51
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2017004/
%R 10.1051/ro/2017004
%G en
%F RO_2017__51_4_985_0
El Haffari, Mostafa; Roubi, Ahmed. Convergence of a proximal algorithm for solving the dual of a generalized fractional program. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 4, pp. 985-1004. doi : 10.1051/ro/2017004. http://www.numdam.org/articles/10.1051/ro/2017004/

A. Addou and A. Roubi, Proximal-Type Methods with Generalized Bregman Functions and Applications to Generalized Fractional Programming. Optimization 59 (2010) 1085–1105. | DOI | MR | Zbl

A.I. Barros, J.B.G. Frenk, S. Schaible and S. Zhang, A New Algorithm for Generalized Fractional Programs. Math. Program. 72 (1996) 147–175. | DOI | MR | Zbl

A.I. Barros, J.B.G. Frenk, S. Schaible and S. Zhang, Using Duality to Solve Generalized Fractional Programming Problems. J. Glob. Optim. 8 (1996) 139–170. | DOI | MR | Zbl

J.C. Bernard and J.A. Ferland, Convergence of Interval-Type Algorithms for Generalized Fractional Programming. Math. Program. 43 (1989) 349–363. | DOI | MR | Zbl

M.C. Burke, and J.V. Ferris, Weak Sharp Minima in Mathematical Programming. SIAM J. Control Optim. 31 (1993) 1340–1359. | DOI | MR | Zbl

R. Correa and C. Lemaréchal, Convergence of Some Algorithms for Convex Minimization. Math. Program. 62 (1993) 261–275. | DOI | MR | Zbl

J.P. Crouzeix and J.A. Ferland, Algorithms for Generalized Fractional Programming. Math. Program. 52 (1991) 191–207. | DOI | MR | Zbl

J.P. Crouzeix, J.A. Ferland and S. Schaible, Duality in Generalized Linear Fractional Programming. Math. Program. 27 (1983) 342–354. | DOI | MR | Zbl

J.P. Crouzeix, J.A. Ferland and S. Schaible, An Algorithm for Generalized Fractional Programs. J. Optim. Theory Appl. 47 (1985) 35–49. | DOI | MR | Zbl

J.P. Crouzeix, J.A. Ferland and S. Schaible, A Note on an Algorithm for Generalized Fractional Programs. J. Optim. Theory Appl. 50 (1986) 183–187. | DOI | MR | Zbl

W. Dinkelbach, On Nonlinear Fractional Programming. Manag. Sci. 13 (1967) 492–498. | DOI | MR | Zbl

I. Ekeland and R. Temam, Analyse Convexe et Problèmes Variationnels. Gauthier-Villars, Paris, Bruxelles, Montréal (1974). | MR | Zbl

M. Gugat, Prox-Regularization Methods for Generalized Fractional Programming. J. Optim. Theory Appl. 99 (1998) 691–722. | DOI | MR | Zbl

O. Güler, On the Convergence of the Proximal Point Algorithm for Convex Minimization. SIAM J. Control Optim. 29 (1991) 403–419. | DOI | MR | Zbl

J-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms II. Springer-Verlag (1993). | MR | Zbl

J.-Y. Lin, H.-J. Chen and R.-L. Sheu, Augmented Lagrange Primal-Dual Approach for Generalized Fractional Programming Problems. Ind. Manag. Optim. 4 (2013) 723–741. | DOI | MR | Zbl

R.T. Rockafellar, Convex Analysis. Princeton University Press, Princeton, N.J. (1971). | MR | Zbl

A. Roubi, Method of Centers for Generalized Fractional Programming. J. Optim. Theory Appl. 107 (2000) 123–143. | DOI | MR | Zbl

A. Roubi, Convergence of Prox-Regularization Methods for Generalized Fractional Programming. RAIRO: OR 36 (2002) 73–94. | DOI | Numdam | MR | Zbl

M. Sion, On General Minimax Theorems. Pacific J. Math. 8 (1958) 171–176. | DOI | MR | Zbl

J.J. Strodiot, J.P. Crouzeix, V.H. Nguyen and J.A. Ferland, An Inexact Proximal Point Method for Solving Generalized Fractional Programs. J. Glob. Optim. 42 (2008) 121–138. | DOI | MR | Zbl

Cité par Sources :