×

Duality results and dual bundle methods based on the dual method of centers for minimax fractional programs. (English) Zbl 1421.90145

Summary: We propose new duality results for generalized fractional programs (GFP) for a wide class of problems, not limited only to the convex case. Our approach does not use Lagrangian duality, but only an equivalent form of the GFP. We present a general approximating scheme, based on the proximal point algorithm, for solving this dual program. We take advantage of the convexity property of the dual, independently of the primal properties, to build implementable bundle methods with the support of the general scheme. However, it is well known that the principal difficulty with the duality is the evaluation of the dual function. To mitigate this difficulty, we propose bundle methods that need only approximate values and approximate subgradients of the objective dual function. We prove the convergence and the rate of convergence of these algorithms. As is the case for dual algorithms, the proposed methods generate a sequence of values that converges from below to the minimal value of the GFP, and a sequence of approximate solutions that converges to a solution of the dual problem. For certain classes of problems, the convergence is at least linear.

MSC:

90C32 Fractional programming
90C25 Convex programming
49K35 Optimality conditions for minimax problems
49M29 Numerical methods involving duality
49M37 Numerical methods based on nonlinear programming
Full Text: DOI

References:

[1] A. Addou and A. Roubi, Proximal-type methods with generalized Bregman functions and applications to generalized fractional programming, Optimization, 59 (2010), pp. 1085-1105, https://doi.org/10.1080/02331930903395857. · Zbl 1208.65080
[2] S. Addoune, K. Boufi, and A. Roubi, Proximal bundle algorithms for nonlinearly constrained convex minimax fractional programs, J. Optim. Theory Appl., 179 (2018), pp. 212-239, https://doi.org/10.1007/s10957-018-1342-1. · Zbl 1409.90197
[3] S. Addoune, M. El Haffari, and A. Roubi, A proximal point algorithm for generalized fractional programs, Optimization, 66 (2017), pp. 1495-1517, https://doi.org/10.1080/02331934.2017.1338698. · Zbl 1412.90147
[4] A. I. Barros, J. B. G. Frenk, S. Schaible, and S. Zhang, A new algorithm for generalized fractional programs, Math. Program., 72 (1996), pp. 147-175, https://doi.org/10.1007/BF02592087. · Zbl 0853.90106
[5] 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), pp. 139-170, https://doi.org/10.1007/BF00138690. · Zbl 0858.90126
[6] C. R. Bector, S. Chandra, and M. K. Bector, Generalized fractional programming duality: A parametric approach, J. Optim. Theory Appl., 60 (1989), pp. 243-260, https://doi.org/10.1007/BF00940006. · Zbl 0632.90077
[7] J. C. Bernard and J. A. Ferland, Convergence of interval-type algorithms for generalized fractional programming, Math. Program., 43 (1989), pp. 349-363, https://doi.org/10.1007/BF01582298. · Zbl 0677.90074
[8] H. Boualam and A. Roubi, Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs, J. Ind. Manag. Optim., 13 (2017), https://doi.org/10.3934/jimo.2018128. · Zbl 1438.90347
[9] H. Boualam and A. Roubi, Proximal bundle methods based on approximate subgradients for solving Lagrangian duals of minimax fractional programs, J. Global Optim. (2019), https://doi.org/10.1007/s10898-019-00757-2. · Zbl 1423.90252
[10] K. Boufi and A. Roubi, Prox-regularization of the dual method of centers for generalized fractional programs, Optim. Methods Softw., 34 (2019), pp. 515-545, https://doi.org/10.1080/10556788.2017.1392520. · Zbl 1411.90317
[11] K. Boufi and A. Roubi, Dual method of centers for solving generalized fractional programs, J. Global Optim., 69 (2017), pp. 387-426, https://doi.org/10.1007/s10898-017-0523-z. · Zbl 1373.90159
[12] R. Correa and C. Lemaréchal, Convergence of some algorithms for convex minimization, Math. Program., 62 (1993), pp. 261-275, https://doi.org/10.1007/BF01585170. · Zbl 0805.90083
[13] J.-P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Math. Program., 52 (1991), pp. 191-207, https://doi.org/10.1007/BF01582887. · Zbl 0748.90067
[14] J.-P. Crouzeix, J. A. Ferland, and H. V. Nguyen, Revisiting Dinkelbach-type algorithms for generalized fractional programs, Opsearch, 45 (2008), pp. 97-110, https://doi.org/10.1007/BF03398807. · Zbl 1178.90322
[15] J.-P. Crouzeix, J. A. Ferland, and S. Schaible, Duality in generalized linear fractional programming, Math. Program., 27 (1983), pp. 342-354, https://doi.org/10.1007/BF02591908. · Zbl 0526.90083
[16] J.-P. Crouzeix, J. A. Ferland, and S. Schaible, An algorithm for generalized fractional programs, J. Optim. Theory Appl., 47 (1985), pp. 35-49, https://doi.org/10.1007/BF00941314. · Zbl 0548.90083
[17] J.-P. Crouzeix, J. A. Ferland, and S. Schaible, A note on an algorithm for generalized fractional programs, J. Optim. Theory Appl., 50 (1986), pp. 183-187, https://doi.org/10.1007/BF00938484. · Zbl 0573.90090
[18] I. Ekeland and R. Temam, Analyse Convexe et Problèmes Variationnels, Gauthier-Villars, Paris, 1974. · Zbl 0281.49001
[19] 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), pp. 985-1004, https://doi.org/10.1051/ro/2017004. · Zbl 1393.90113
[20] M. El Haffari and A. Roubi, Prox-dual regularization algorithm for generalized fractional programs, J. Ind. Manag. Optim., 13 (2017), pp. 1991-2013, https://doi.org/10.3934/jimo.2017028. · Zbl 1373.90160
[21] J. E. Falk, Maximization of signal-to-noise ratio in an optical filter, SIAM J. Appl. Math., 17 (1969), pp. 582-592. · Zbl 0184.43901
[22] K. Fan, Minimax theorems, Proc. Nat. Acad. Sci. USA, 39 (1953), pp. 42-47. · Zbl 0050.06501
[23] J. B. G. Frenk, G. Kassay, and J. Kolumbán, On equivalent results in minimax theory, European J. Oper. Res., 157 (2004), pp. 46-58, https://doi.org/10.1016/j.ejor.2003.08.013. · Zbl 1106.49011
[24] J. B. G. Frenk and S. Schaible, Fractional Programming, ERIM Report Series ERS-2004-074-LIS, 2004; available at https://ssrn.com/abstract=595012.
[25] M. Fukushima, A descent algorithm for nonsmooth convex optimization, Math. Program., 30 (1984), pp. 163-175, https://doi.org/10.1007/BF02591883. · Zbl 0545.90082
[26] M. Gugat, Prox-regularization methods for generalized fractional programming, J. Optim. Theory Appl., 99 (1998), pp. 691-722, https://doi.org/10.1023/A:1021759318653. · Zbl 0973.90078
[27] O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), pp. 403-419, https://doi.org/10.1137/0329022. · Zbl 0737.90047
[28] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Springer, New York, 1993. · Zbl 0795.49001
[29] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms II, Springer, New York, 1993. · Zbl 0795.49001
[30] R. Jagannathan and S. Schaible, Duality in generalized fractional programming via Farkas’ lemma, J. Optim. Theory Appl., 41 (1983), pp. 417-424, https://doi.org/10.1007/BF00935361. · Zbl 0502.90079
[31] G. Kassay, A simple proof of König’s minimax theorems, Acta Math. Hungar., 63 (1994), pp. 371-374. · Zbl 0811.90115
[32] K. C. Kiwiel, An aggregate subgradient method for nonsmooth convex minimization, Math. Program., 27 (1983), pp. 320-341, https://doi.org/10.1007/BF02591907. · Zbl 0525.90074
[33] K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Math. 1133, Springer, Berlin, 1985. · Zbl 0561.90059
[34] K. C. Kiwiel, A method for solving certain quadratic programming problems arising in nonsmooth optimization, IMA J. Numer. Anal., 6 (1986), pp. 137-152, https://doi.org/10.1093/imanum/6.2.137. · Zbl 0603.65041
[35] K. C. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program., 46 (1990), pp. 105-122, https://doi.org/10.1007/BF01585731. · Zbl 0697.90060
[36] C. Lemaréchal, Bundle methods in nonsmooth optimization, in Nonsmooth Optimization, C. Lemaréchal and R. Mifflin, eds., Pergamon Press, Oxford, 1978, pp. 79-102. · Zbl 0398.90088
[37] C. Lemaréchal, Constructing bundle methods for convex optimization, in Fermat Days 85: Mathematics for Optimization, J. B. Hiriart-Urruty, ed., North-Holland, Amsterdam, 1986, pp. 201-240. · Zbl 0606.49008
[38] B.-L. Lin and C.-Z. Cheng, A minimax theorems involving weakly downward functions, Acta Math. Hungar., 87 (2000), pp. 287-293, https://doi.org/10.1023/A:1006721718184. · Zbl 0973.49019
[39] M. Mäkelä, Survey of bundle methods for nonsmooth optimization, Optim. Methods Softw., 17 (2002), pp. 1-29, https://doi.org/10.1080/10556780290027828. · Zbl 1050.90027
[40] B. Martinet, Régularisation d’Inéquations Variationnelles par Approximation Successives, Rev. Fr. Inform. Rech. O., 4 (1970), pp. 154-158. · Zbl 0215.21103
[41] R. Mifflin, An algorithm for constrained optimization with semismooth functions, Math. Oper. Res., 2 (1977), pp. 191-207, https://doi.org/10.1287/moor.2.2.191. · Zbl 0395.90069
[42] R. Mifflin, A modification and extension of Lemaréchal’s algorithm for nonsmooth minimization, Math. Program. Stud., 17 (1982), pp. 77-90. · Zbl 0476.65047
[43] J.-J. Moreau, Proximité et Dualité dans un Espace Hilbertien, Bull. Soc. Math. France, 93 (1965), pp. 273-299. · Zbl 0136.12101
[44] 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), pp. 383-419, https://doi.org/10.1051/ro:1999118. · Zbl 1016.90065
[45] B. T. Polyak, Introduction to Optimization, Transl. Ser. Math. Engrg., Optimization Software, New York, 1987.
[46] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), pp. 877-898, https://doi.org/10.1137/0314056. · Zbl 0358.90053
[47] A. Roubi, Method of centers for generalized fractional programming, J. Optim. Theory Appl., 107 (2000), pp. 123-143, https://doi.org/10.1023/A:1004660917684. · Zbl 0964.90045
[48] A. Roubi, Convergence of prox-regularization methods for generalized fractional programming, RAIRO Oper. Res., 36 (2002), pp. 73-94, https://doi.org/10.1051/ro:2002006. · Zbl 1103.90401
[49] S. Schaible, Fractional programming, in Handbook of Global Optimization, R. Horst and P. M. Pardalos, eds., Kluwer, Dordrecht, 1995, pp. 495-608. · Zbl 0832.90115
[50] H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2 (1992), pp. 121-152, https://doi.org/10.1137/0802008. · Zbl 0761.90090
[51] S. Simons, An upward-downward minimax theorem, Arch. Math. (Basel), 55 (1990), pp. 275-279, https://doi.org/10.1007/BF01191168. · Zbl 0717.49008
[52] S. Simons, Minimax theorems and their proofs, in Minimax and Applications, Nonconvex Optim. Appl. 4, D. Z. Du and P. M. Pardalos, eds., Springer, Boston, MA, 1995, pp. 1-23. · Zbl 0862.49010
[53] M. Sion, On general minimax theorems, Pac. J. Optim., 8 (1958), pp. 171-176, https://doi.org/10.2140/pjm.1958.8.171. · Zbl 0081.11502
[54] A. M. Stancu, Mathematical Programming with Type-I Functions, MatrixRom, Romania, Bucharest, 2013.
[55] I. M. Stancu-Minasian, Fractional Programming: Theory, Methods and Applications, Kluwer Academic, Dordrecht, 1997. · Zbl 0899.90155
[56] I. M. Stancu-Minasian, A sixth bibliography of fractional programming, Optimization, 55 (2006), pp. 405-428, https://doi.org/10.1080/02331930600819613. · Zbl 1137.90300
[57] I. M. Stancu-Minasian, A seventh bibliography of fractional programming, Adv. Model. Optim., 15 (2013), pp. 309-386. · Zbl 1413.90282
[58] I. M. Stancu-Minasian, A eighth bibliography of fractional programming, Optimization, 66 (2017), pp. 439-470, https://doi.org/10.1080/02331934.2016.1276179. · Zbl 1365.90249
[59] 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), pp. 121-138, https://doi.org/10.1007/s10898-007-9270-x. · Zbl 1193.90200
[60] Z. Xu, Duality in generalized nonlinear fractional programming, J. Math. Anal. Appl., 169 (1992), pp. 1-9, https://doi.org/10.1016/0022-247X(92)90099-Y. · Zbl 0764.90081
[61] G. Zalmai, Duality for generalized fractional programs involving \(n\)-set functions, J. Math. Anal. Appl., 149 (1990), pp. 339-350, https://doi.org/10.1016/0022-247X(90)90046-I. · Zbl 0723.90078
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.