Zero duality gap conditions via abstract convexity. (English) Zbl 1489.90133
Summary: Using tools provided by the theory of abstract convexity, we extend conditions for zero duality gap to the context of non-convex and nonsmooth optimization. Mimicking the classical setting, an abstract convex function is the upper envelope of a family of abstract affine functions (being conventional vertical translations of the abstract linear functions). We establish new conditions for zero duality gap under no topological assumptions on the space of abstract linear functions. In particular, we prove that the zero duality gap property can be fully characterized in terms of an inclusion involving (abstract) \(\varepsilon\)-subdifferentials. This result is new even for the classical convex setting. Endowing the space of abstract linear functions with the topology of pointwise convergence, we extend several fundamental facts of functional/convex analysis. This includes (i) the classical Banach-Alaoglu-Bourbaki theorem (ii) the subdifferential sum rule, and (iii) a constraint qualification for zero duality gap which extends a fact established by J. M. Borwein et al. [J. Nonlinear Convex Anal. 15, No. 1, 167–190 (2014; Zbl 1301.49035)] for the conventional convex case. As an application, we show with a specific example how our results can be exploited to show zero duality for a family of non-convex, non-differentiable problems.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 52A01 | Axiomatic and generalized convexity |
| 47N10 | Applications of operator theory in optimization, convex analysis, mathematical programming, economics |
| 49J53 | Set-valued and variational analysis |
| 49J27 | Existence theories for problems in abstract spaces |
| 49J52 | Nonsmooth analysis |
| 90C30 | Nonlinear programming |
Keywords:
abstract convexity; inf-convolution; Fenchel conjugate; \(\varepsilon\)-subdifferentials sum rule; zero duality gapCitations:
Zbl 1301.49035References:
| [1] | Martínez-Legaz, JE., Quasiconvex duality theory by generalized conjugation methods, Optimization, 19, 1029-4945 (1988) |
| [2] | Burachik, RS; Rubinov, AM., On abstract convexity and set valued analysis, J Nonlinear Convex Anal, 9, 1, 105-123 (2008) · Zbl 1151.47052 |
| [3] | Jeyakumar, J.; Rubinov, AM; Wu, ZY., Generalized Fenchel’s conjugation formulas and duality for abstract convex functions, J Optim Theory Appl, 132, 441-458 (2007) · Zbl 1146.49013 |
| [4] | Rubinov, AM; Uderzo, A., On global optimality conditions via separation functions, J Optim Theory Appl, 109, 345-370 (2001) · Zbl 0983.90049 |
| [5] | Yao, C.; Li, S., Vector topical function, abstract convexity and image space analysis, J Optim Theory Appl, 177, 717-742 (2018) · Zbl 1394.90523 |
| [6] | Ioffe, A., Abstract convexity and non-smooth analysis, Adv Math Econ, 3, 45-61 (2001) · Zbl 1063.49016 |
| [7] | Dutta, J.; Martínez-Legaz, J.; Rubinov, AM., Monotonic analysis over cones: II, Optimization, 53, 529-547 (2004) · Zbl 1153.49308 |
| [8] | Dutta, J.; Martínez-Legaz, J.; Rubinov, AM., Monotonic analysis over cones: I, Optimization, 53, 165-177 (2004) · Zbl 1085.49021 |
| [9] | Rubinov, AM; Dzalilov, Z., Abstract convexity of positively homogeneous functions, J Statist Manage Syst, 5, 1-20 (2002) · Zbl 1079.90590 |
| [10] | Nedić, A.; Ozdaglar, A.; Rubinov, AM., Abstract convexity for nonconvex optimization duality, Optimization, 56, 655-674 (2007) · Zbl 1172.90465 |
| [11] | Shveidel, AP., Abstract convex sets with respect to the class of general min-type functions, Optimization, 52, 571-579 (2003) · Zbl 1085.49025 |
| [12] | Daryaei, M.; Mohebi, H., Abstract convexity of extended real-valued ICR functions, Optimization, 62, 835-855 (2013) · Zbl 1272.26006 |
| [13] | Rubinov, AM., Abstract convexity, global optimization and data classification, OPSEARCH, 38, 3, 247-265 (2001) · Zbl 1278.90320 |
| [14] | Eberhard, AC; Mohebi, H., Maximal abstract monotonicity and generalized Fenchel’s conjugation formulas, Set-Valued Anal, 18, 79-108 (2010) · Zbl 1218.47072 |
| [15] | Mohebi, H.; Samet, M., Abstract convexity of topical functions, J Glob Optim, 58, 365-357 (2014) · Zbl 1297.26022 |
| [16] | Doagooei, AR; Mohebi, H., Monotonic analysis over ordered topological vector spaces: IV, J Glob Optim, 45, 355-369 (2009) · Zbl 1200.26014 |
| [17] | Dutta, J.; Martínez-Legaz, J.; Rubinov, AM., Monotonic analysis over cones: III, Convex Anal, 15, 581-592 (2008) |
| [18] | Rubinov, AM; Wu, ZY., Optimality conditions in global optimization and their applications, Math Program Ser B, 120, 101-123 (2009) · Zbl 1191.90047 |
| [19] | Burachik, RS; Rubinov, AM., Abstract convexity and augmented Lagrangians, SIAM J Optim, 18, 2, 413-436 (2007) · Zbl 1190.90134 |
| [20] | Sattarzadeh, AR; Mohebi, H., Characterizing approximate global minimizers of the difference of two abstract convex functions with applications, Filomat, 33, 8, 2431-2445 (2019) · Zbl 1513.90132 |
| [21] | Wu, ZY., Sufficient global optimality conditions for weakly convex minimization problems, J Global Optim, 39, 3, 427-440 (2007) · Zbl 1149.90154 |
| [22] | López, MA; Rubinov, AM., Stability of semi-infinite inequality systems involving min-type functions, Numer Funct Anal Optim, 26, 1, 81-112 (2005) · Zbl 1072.90044 |
| [23] | Singer, I., Duality in quasi-convex supremization and reverse convex infimization via abstract convex analysis, and applications to approximation, Optimization, 45, 1-4, 255-307 (1999) · Zbl 0941.49020 |
| [24] | Rubinov, AM; Glover, BM., Increasing convex-along-rays functions with applications to global optimization, J Optim Theory Appl, 102, 3, 615-642 (1999) · Zbl 0955.90105 |
| [25] | Rubinov, AM; Andramonov, MY., Minimizing increasing star-shaped functions based on abstract convexity, J Global Optim, 15, 1, 19-39 (1999) · Zbl 0954.90034 |
| [26] | Andramonov, M., A survey of methods of abstract convex programming, J Statist Manage Syst, 5, 1-3, 21-37 (2002) · Zbl 1079.90584 |
| [27] | Crespi, G.; Ginchev, I.; Rocca, M., Convex along lines functions and abstract convexity. i, J Convex Anal, 14 (2007) · Zbl 1132.49007 |
| [28] | Rubinov, AM; Shveidel, A., Radiant and star-shaped functions, Pac J Optim, 3, 1, 193-212 (2012) · Zbl 1134.26004 |
| [29] | Rubinov, AM; Singer, I., Topical and sub-topical functions, downward sets and abstract convexity, Optimization, 50, 5-6, 307-351 (2001) · Zbl 1007.26010 |
| [30] | Syga, M., Minimax theorems for ϕ-convex functions: sufficient and necessary conditions, Optimization, 65, 3, 635-649 (2016) · Zbl 1336.49032 |
| [31] | Syga, M., Minimax theorems for extended real-valued abstract convex-concave functions, J Optim Theory Appl, 176, 306-318 (2018) · Zbl 1401.49009 |
| [32] | Bednarczuk, EM, Syga, M. On Lagrange duality for several classes of nonconvex optimization problems. In: Le Thi HA, Le HM, Pham Dinh T, editors. Optimization of complex systems: theory, models, algorithms and applications. Cham: Springer International Publishing; 2020. p. 175-181. · Zbl 1429.90054 |
| [33] | Gorokhovik, VV; Tykoun, AS., Support points of lower semicontinuous functions with respect to the set of Lipschitz concave functions, Dokl Nats Akad Nauk Belarusi, 63, 6, 647-653 (2019) · Zbl 1524.49026 |
| [34] | Gorokhovik, VV; Tykoun, AS., Abstract convexity of functions with respect to the set of Lipschitz (concave) functions, Proc Steklov Inst Math, 309, 1, S36-S46 (2020) |
| [35] | Bednarczuk, EM, Syga, M. Lagrangian duality for nonconvex optimization problems with abstract convex functions. preprint 2020. arXiv:201109194. · Zbl 1429.90054 |
| [36] | Dolgopolik, MV., Abstract convex approximations of nonsmooth functions, Optimization, 64, 7, 1439-1469 (2015) · Zbl 1337.49021 |
| [37] | Rubinov, AM., Abstract convexity and global optimization (2000), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0985.90074 |
| [38] | Singer, I., Abstract convex analysis (2006), New York: Wiley-Interscience, New York |
| [39] | Grad, SM., Closedness type regularity conditions in convex optimization and beyond, Frontiers Appl Math Statist, 2, 14 (2016) |
| [40] | Borwein, J.; Burachik, RS; Yao, L., Conditions for zero duality gap in convex programming, J Nonlinear Convex Anal, 15, 1, 167-190 (2014) · Zbl 1301.49035 |
| [41] | Brezis, H., Functional analysis, Sobolev spaces and partial differential equations (2011), Springer: New York · Zbl 1220.46002 |
| [42] | Fajardo, MD; Goberna, MA; Rodríguez, MM, Even convexity and optimization: handling strict inequalities (2020), Switzerland: Springer Nature · Zbl 1462.90002 |
| [43] | Martínez-Legaz, JE; Vicente-Pérez, J., The e-support function of an e-convex set and conjugacy for e-convex functions, J Math Anal Appl, 376, 2, 602-612 (2011) · Zbl 1213.26017 |
| [44] | Zălinescu, C., Convex analysis in general vector spaces (2002), River Edge: World Scientific Publishing Co. Inc., River Edge · Zbl 1023.46003 |
| [45] | Strekalovsky, AS., Global optimality conditions and exact penalization, Optim Lett, 13, 3, 597-615 (2019) · Zbl 1432.90126 |
| [46] | Li, G.; Ng, KF., On extension of Fenchel duality and its application, SIAM J Optim, 19, 3, 1489-1509 (2008) · Zbl 1190.90249 |
| [47] | Burachik, RS; Majeed, SN., Strong duality for generalized monotropic programming in infinite dimensions, J Math Anal Appl, 400, 2, 541-557 (2013) · Zbl 1259.49055 |
| [48] | Luc, DT; Volle, M., Duality for extended infinite monotropic optimization problems, Math Program (2020) · Zbl 1478.90125 · doi:10.1007/s10107-020-01557-3 |
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.
