Prox-dual regularization algorithm for generalized fractional programs

Mostafa El Haffari; Ahmed Roubi

doi:10.3934/jimo.2017028

Article Contents

2017, Volume 13, Issue 4: 1991-2013. Doi: 10.3934/jimo.2017028

This issue Previous Article An integrated inventory model with variable transportation cost, two-stage inspection, and defective items Next Article An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem

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
* Corresponding author:Ahmed Roubi

Received: August 31, 2015

Revised: January 31, 2017

Published: November 2017

Abstract Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C32, 49N15, 49M29, 49M37; Secondary: 49K35.

Citation:

Full Text(HTML)

Table 1. The number of iterations and times with $n=5$, $m=5$, $p=5$

$\alpha$	Problems
$\alpha$		1	2	3	4	5	6	7	8	9	10
10	It	62	143	81	4	27	2	9	763	86	114
10	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
1	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
10^-1	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
Alg[3]	T(s)	1.18	0.04	1.09	0.04	0.39	0.05	0.04	0.04	0.46	1.27

| Show Table

DownLoad: CSV

Table 2. The number of iterations and times with $n=10$, $m=10$, $p=5$

$\alpha$	Problems
$\alpha$		1	2	3	4	5	6	7	8	9	10
10	It	328	165	62	50	21	91	6	13	31	225
10	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
1	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
10^-1	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
Alg[3]	T(s)	4.70	4.48	1.01	0.68	0.35	0.09	0.06	0.11	0.51	4.50

| Show Table

DownLoad: CSV

Table 3. The number of iterations and times with $n=20$, $m=10$, $p=5$

$\alpha$	Problems
$\alpha$		1	2	3	4	5	6	7	8	9	10
10	It	87	26	260	24	151	70	50	11	113	62
10	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
1	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
10^-1	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
Alg [3]	T(s)	2.01	0.47	0.23	0.54	2.41	1.68	1.05	0.19	3.09	1.24

| Show Table

DownLoad: CSV

Table 4. The number of iterations and times with $n=50$, $m=10$, $p=5$

$\alpha$	Problems
$\alpha$		1	2	3	4	5	6	7	8	9	10
10	It	35	50	35	26	78	19	39	91	42	109
10	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
1	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
10^-1	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
Alg [3]	T(s)	0.76	2.94	1.18	2.25	2.04	0.59	0.61	3.18	1.41	3.37

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[9]	J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207. doi: 10.1007/BF01582887.
[10]	W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498. doi: 10.1287/mnsc.13.7.492.
[11]	I. Ekeland and R. Temam, Analyse Convexe et Problémes Variationnels, Gauthier-Villars, Paris, Bruxelles, Montréal, 1976.
[12]	J. B. G. Frenk and S. Schaible, Fractional Programming, in ERIM Report Series, (Reference No. ERS-2004-074-LIS) (2004).
[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.
[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.
[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.
[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.
[17]	R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N. J., 1970.
[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.
[19]	A. Roubi, Convergence of prox-regularization methods for generalized fractional programming, RAIRO Oper. Res., 36 (2002), 73-94. doi: 10.1051/ro:2002006.
[20]	S. Schaible, Fractional Programming, in Handbook Global Optimization (eds. R. Horst and P. M. Pardalos), Kluwer, Dordrecht, (1995), 495{608
[21]	M. Sion, On General minimax theorems, Pacific Journal of Mathematics, 8 (1958), 171-176. doi: 10.2140/pjm.1958.8.171.
[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.