Augmented Lagrangian dual for nonconvex minimax fractional programs and proximal bundle algorithms for its resolution

Hssaine Boualam; Ahmed Roubi

doi:10.3934/jimo.2022100

Article Contents

2023, Volume 19, Issue 5: 3610-3636. Doi: 10.3934/jimo.2022100

This issue Previous Article Stochastic differential game strategies in the presence of reinsurance and dividend payout Next Article A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization

Augmented Lagrangian dual for nonconvex minimax fractional programs and proximal bundle algorithms for its resolution

Hssaine Boualam^1, , and
Ahmed Roubi^2,

1.
Ecole Nationale d'Agriculture, Meknès, Morocco
2.
Hassan First University of Settat, Faculté des Sciences et Techniques, Laboratoire MISI, Morocco

^*Corresponding author: Hssaine Boualam
^*Corresponding author: Hssaine Boualam

Received: March 2021

Revised: February 2022

Early access: June 2022

Published: May 2023

Abstract Full Text(HTML) Figure(8) / Table(1) Related Papers Cited by

Abstract

Based on augmented Lagrangian, we propose in this paper a new dual for inequality constrained nonconvex generalized fractional programs (GFP). We give duality results under quite weak assumptions. We associate with this dual program, parametric dual subproblems and establish duality results with the usual parametric primal ones. By taking advantage of the concavity of the parametric dual functions, we propose proximal bundle-like methods that approximately solve the parametric dual subproblems, to finally solve this dual program. For some problems, these method converge linearly.

Keywords:

Mathematics Subject Classification: Primary: 90C32, 90C47, 90C46, 90C26, 49M29; Secondary: 49M37.

Citation:

Full Text(HTML)

Figure 1. Av. IT and Av. QP for $ c = 0.05 $

Download: Full-size image PowerPoint slide

Figure 2. Av. IT and Av. QP for $ c = 0.1 $

Download: Full-size image PowerPoint slide

Figure 3. Av. IT and Av. QP for $ c = 0.5 $

Download: Full-size image PowerPoint slide

Figure 4. Av. IT and Av. QP for $ c = 0.9 $

Download: Full-size image PowerPoint slide

Figure 5. Av. IT and Av. QP for $ \beta_k = 0.5 $

Download: Full-size image PowerPoint slide

Figure 6. Av. IT and Av. QP for $ \beta_k = 1 $

Download: Full-size image PowerPoint slide

Figure 7. Av. IT and Av. QP for $ \beta_k = 5 $

Download: Full-size image PowerPoint slide

Figure 8. Av. IT and Av. QP for $ \beta_k = 10 $

Download: Full-size image PowerPoint slide

Table 1. Results of Alg2 and Alg3 with $ n = 20 $, $ m = 10 $, $ p = 10 $

			Alg2				Alg3
$ \beta_\bf{k} $		$ c $	0.05	0.1	0.5	0.9	0.05	0.1	0.5	0.9
0.5	Av. IT		13.8	12.6	12.2	8.4	12	12.2	11.2	8.8
	Av. QP		69.2	61.2	66.4	54.4	58.2	62.4	59.6	55.8
	Av. T(s)		10.5	8.7	8.4	6.6	0.4	0.4	0.3	0.3
1	Av. IT		10	11.4	10.6	7.4	9.2	8.6	10.4	7.8
	Av. QP		42.2	50	51	45	38.6	35.4	48.8	46
	Av. T(s)		5.7	6.8	6.6	5.5	0.2	0.2	0.3	0.2
5	Av. IT		15.8	11.6	14.4	15.8	12	10.6	14.4	13.4
	Av. QP		45.2	30	37.4	57.4	32.6	28	38.8	46
	Av. T(s)		5.6	4	4.9	6.3	0.2	0.1	0.3	0.2
10	Av. IT		21.2	21.2	22.2	24	23.8	23.8	21.2	22.2
	Av. QP		36.8	36.8	39.8	54.6	44.8	44.6	37	49.2
	Av. T(s)		4.6	4.5	4.9	6.1	0.3	0.3	0.2	0.3
Opt.Val: $ \bar{\lambda} $			$ -0.3040 $				$ -0.3040 $

| 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]	S. Addoune, K. Boufi and A. Roubi., Proximal bundle algorithms for nonlinearly constrained convex minimax fractional programs, J. Optim. Theory Appl., 179 (2018), 212-239. doi: 10.1007/s10957-018-1342-1.
[3]	S. Addoune, M. El Haffari and A. Roubi, A proximal point algorithm for generalized fractional programs, Optimization, 66 (2017), 1495-1517. doi: 10.1080/02331934.2017.1338698.
[4]	A. Aubry, V. Carotenuto and A. De Maio, New results on generalized fractional programming problems with Toeplitz quadratics, IEEE Signal Process. Lett., 23 (2016), 848-852. doi: 10.1109/LSP.2016.2555880.
[5]	A. Aubry, A. De Maio, Y. Huang and M. Piezzo, Robust design of radar Doppler filters, IEEE Trans. Signal Process, 64 (2016), 5848-5860. doi: 10.1109/TSP.2016.2576423.
[6]	A. Aubry, A. De Maio and M. M. Naghsh, Optimizing radar waveform and Doppler filter bank via generalized fractional programming, IEEE J. Sel. Topics Signal Process, 9 (2015), 1387-1399. doi: 10.1109/JSTSP.2015.2469259.
[7]	A. I. Barros, J. B. G. Frenk, S. Schaible and S. Zhang, A new algorithm for generalized fractional programs, Math. Programming, 72 (1996), 147–175. doi: 10.1007/BF02592087.
[8]	A. I. Barros, J. B. G. Frenk, S. Schaible and S. Zhang, Using duality to solve generalized fractional programming problems, J. Global Optim., 8 (1996), 139-170. doi: 10.1007/BF00138690.
[9]	C. R. Bector, S. Chandra and M. K. Bector, Generalized fractional programming duality: A parametric approach, J. Optim. Theory Appl., 60 (1989), 243-260. doi: 10.1007/BF00940006.
[10]	J. C. Bernard and J. A. Ferland, Convergence of interval-type algorithms for generalized fractional programming, Math. Programming, 43 (1989), 349-363. doi: 10.1007/BF01582298.
[11]	H. Boualam and A. Roubi, Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs, J. Ind. Manag. Optim., 15 (2019), 1897-1920. doi: 10.3934/jimo.2018128.
[12]	H. Boualam and A. Roubi, Proximal bundle methods based on approximate subgradients for solving Lagrangian duals of minimax fractional programs, J. Global Optim., 74 (2019), 255-284. doi: 10.1007/s10898-019-00757-2.
[13]	K. Boufi, M. El Haffari and A. Roubi, Optimality conditions and a method of centers for minimax fractional programs with difference of convex functions, J. Optim. Theory Appl., 187 (2020), 105-132. doi: 10.1007/s10957-020-01738-2.
[14]	K. Boufi and A. Roubi, Dual method of centers for solving generalized fractional programs, J. Global Optim., 69 (2017), 387-426. doi: 10.1007/s10898-017-0523-z.
[15]	K. Boufi and A. Roubi, Duality results and dual bundle methods based on the dual method of centers for minimax fractional programs, SIAM J. Optim., 29 (2019), 1578-1602. doi: 10.1137/18M1199708.
[16]	K. Boufi and A. Roubi, Prox-regularization of the dual method of centers for generalized fractional programs, Optim. Methods Softw., 34 (2019), 515-545. doi: 10.1080/10556788.2017.1392520.
[17]	J.-P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Math. Programming, 52 (1991), 191–207. doi: 10.1007/BF01582887.
[18]	J.-P. Crouzeix, J. A. Ferland and V. H. Nguyen, Revisiting Dinkelbach-type algorithms for generalized fractional programs, Opsearch, 45 (2008), 97-110. doi: 10.1007/BF03398807.
[19]	J.-P. Crouzeix, J. A. Ferland and S. Schaible, An algorithm for generalized fractional programs, J. Optim. Theory Appl., 47 (1985), 35-49. doi: 10.1007/BF00941314.
[20]	J.-P. Crouzeix, J. A. Ferland and S. Schaible, Duality in generalized linear fractional programming, Math. Programming, 27 (1983), 342-354. doi: 10.1007/BF02591908.
[21]	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: 10.1007/BF00938484.
[22]	M. El Haffari and A. Roubi, Convergence of a proximal algorithm for solving the dual of a generalized fractional program, RAIRO Oper. Res., 51 (2017), 985-1004. doi: 10.1051/ro/2017004.
[23]	M. El Haffari and A. Roubi, Prox-dual regularization algorithm for generalized fractional programs, J. Ind. Manag. Optim., 13 (2017), 1991-2013. doi: 10.3934/jimo.2017028.
[24]	J. E. Falk, Maximization of signal-to-noise ratio in an optical filter, SIAM Appl. Math., 17 (1969), 582-592. doi: 10.1137/0117055.
[25]	K. Fan, Minimax theorems, Proc. Nat. Acad. Sci. U.S.A., 39 (1953), 42-47. doi: 10.1073/pnas.39.1.42.
[26]	J. B. G. Frenk, G. Kassay and J. Kolumbán, On equivalent results in minimax theory, European J. Oper. Res., 157 (2004), 46-58. doi: 10.1016/j.ejor.2003.08.013.
[27]	J. B. G. Frenk and S. Schaible, Fractional programming, in Handbook of Generalized Convexity and Generalized Monotonicity, Nonconvex Optim. Appl., 76, Springer, New York, 2005,335—386. doi: 10.1007/0-387-23393-8_8.
[28]	A. Ghazi and A. Roubi, A DC approach for minimax fractional optimization programs with ratios of convex functions, Optim. Methods Softw., (2020). doi: 10.1080/10556788.2020.1818234.
[29]	O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), 403-419. doi: 10.1137/0329022.
[30]	J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. II. Advanced Theory and Bundle Methods, Fundamental Principles of Mathematical Sciences, 306, Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-06409-2.
[31]	R. Jagannathan and S. Schaible, Duality in generalized fractional programming via Farkas' lemma, J. Optim. Theory Appl., 41 (1983), 417-424. doi: 10.1007/BF00935361.
[32]	G. Kassay, A simple proof of König's minimax theorems, Acta Math. Hungar., 63 (1994), 371-374. doi: 10.1007/BF01874462.
[33]	B.-L. Lin and C.-Z. Cheng, A minimax theorems involving weakly downward functions, Acta Math. Hungar., 87 (2000), 287-293. doi: 10.1023/A:1006721718184.
[34]	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. doi: 10.1051/ro:1999118.
[35]	B. Ricceri, On a minimax theorem: An improvement, a new proof and an overview of its applications, Minimax Theory Appl., 2 (2017), 99-152.
[36]	B. Ricceri, A strict minimax inequality criterion and some of its consequences, Positivity, 16 (2012), 455-470. doi: 10.1007/s11117-012-0164-x.
[37]	R. T. Rockafellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control, 12 (1974), 268-285. doi: 10.1137/0312021.
[38]	R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, 28, Princeton University Press, Princeton, NJ, 1970.
[39]	A. Roubi, Convergence of prox-regularization methods for generalized fractional programming, RAIRO Oper. Res., 36 (2002), 73-94. doi: 10.1051/ro:2002006.
[40]	A. Roubi, Method of centers for generalized fractional programming, J. Optim. Theory Appl., 107 (2000), 123-143. doi: 10.1023/A:1004660917684.
[41]	S. Schaible, Fractional programming, in Handbook Global Optimization, Nonconvex Optim. Appl., 2, Kluwer Acad. Publ., Dordrecht, 1995,495–608. doi: 10.1007/978-1-4615-2025-2.
[42]	S. Simons, Minimax theorems and their Proofs, in Minimax and Applications, Nonconvex Optim. Appl., 4, Kluwer Acad. Publ., Dordrecht, 1995, 1–23. doi: 10.1007/978-1-4613-3557-3_1.
[43]	S. Simons, An upward-downward minimax theorem, Arch. Math. (Basel), 55 (1990), 275-279. doi: 10.1007/BF01191168.
[44]	M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176. doi: 10.2140/pjm.1958.8.171.
[45]	A. M. Stancu, Mathematical Programming with Type-I Functions, Matrix, Romania, Bucharest, 2013.
[46]	I. M. Stancu-Minasian, Fractional Programming. Theory, Methods and Applications, Mathematics and its Applications, 409, Kluwer Academic Publishers Group, Dordrecht, 1997. doi: 10.1007/978-94-009-0035-6.
[47]	I. M. Stancu-Minasian, A eighth bibliography of fractional programming, Optimization, 66 (2017), 439-470. doi: 10.1080/02331934.2016.1276179.
[48]	I. M. Stancu-Minasian, A ninth bibliography of fractional programming, Optimization, 68 (2019), 2123-2167. doi: 10.1080/02331934.2019.1632250.
[49]	I. M. Stancu-Minasian, A seventh bibliography of fractional programming, Adv. Model. Optim., 15 (2013), 309–386. Available from: https://camo.ici.ro/journal/vol15/v15b13.pdf.
[50]	I. M. Stancu-Minasian, A sixth bibliography of fractional programming, Optimization, 55 (2006), 405-428. doi: 10.1080/02331930600819613.
[51]	J.-J. Strodiot, J.-P. Crouzeix, J. A. Ferland and V. H. Nguyen, An inexact proximal point method for solving generalized fractional programs, J. Global Optim., 42 (2008), 121-138. doi: 10.1007/s10898-007-9270-x.
[52]	Z. K. Xu, Duality in generalized nonlinear fractional programming, J. Math. Anal. Appl., 169 (1992), 1-9. doi: 10.1016/0022-247X(92)90099-Y.
[53]	G. J. Zalmai, Duality for generalized fractional programs involving $n$-set functions, J. Math. Anal. Appl., 149 (1990), 339-350. doi: 10.1016/0022-247X(90)90046-I.