Article Contents
Article Contents

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

• *Corresponding author: Hssaine Boualam
• 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.

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

 Citation:

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

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

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

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

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

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

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

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

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$
•  [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.

Figures(8)

Tables(1)