Discrete 2-convex functions
Tóm tắt
We focus on a new class of integrally convex functions which we call discrete 2-convex functions. Discrete 2-convexity generalizes known classes of integrally convex functions such as the well-established M-/M
$${}^\natural $$
-convex and L-/L
$${}^\natural $$
-convex functions by Murota et al., the recently investigated globally/locally discrete midpoint convex functions by Moriguchi, Murota, Tamura, and Tardella, the directed discrete midpoint convex functions by Tamura and Tsurumi, and BS
$${}^*$$
-convex and UJ-convex functions by one of the authors. We provide a unifying view of all these functions within the class of integrally convex functions having discrete 2-convexity. We also introduce a new subclass of discrete 2-convex functions, called signed discrete 2-convex functions and we consider signed discrete 2-convex functions with a locally hereditary orientation property. We show that parallelogram inequalities, scalability, and proximity hold for such signed discrete 2-convex functions, which include globally/locally discrete midpoint convex functions and directed discrete midpoint convex functions. Hence, our results extend similar results recently established by Moriguchi, Murota, Tamura, and Tardella and by Tamura and Tsurumi.
Tài liệu tham khảo
Beckenbach, E.F.: Convex functions. Bulletin American Mathematical Society 54, 439–460 (1948)
Dress, A.W., Wenzel, W.: Valuated matroids: A new look at the greedy algorithm. Appl. Math. Lett. 3, 33–35 (1990)
Dress, A.W., Wenzel, W.: Valuated matroids. Adv. Math. 93, 214–250 (1992)
Favati, P., Tardella, F.: Convexity in nonlinear integer programming. Ricerca Operativa 53, 3–44 (1990)
Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier (2005)
Fujishige, S.: Bisubmodular polyhedra, simplicial divisions, and discrete convexity. Discret.eOptim. 12, 115–120 (2014)
Fujishige, S.: Greedy systems of linear inequalities and lexicographically optimal solutions. RAIRO Operations Research 53, 1929–1935 (2019)
Fujishige, S., Murota, K.: Notes on L-/M-convex functions and the separation theorems. Math. Program. 88, 129–146 (2000)
Jensen, J.L.W.V.: Om konvekse Funktioner og Uligheder imellem Middelværdier. Math. Scand.16B, 49–68 (1905). Also: Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math.30, 175–193 (1906)
Lovász, L.: Submodular functions and convexity. In: A. Bachem, M. Grötschel, B. Korte, (ed.) Mathematical Programming-The State of the Art, pp. 235–257. Springer, Berlin (1983)
Moriguchi, S., Murota, K., Tamura, A., Tardella, F.: Scaling, proximity, and optimization of integrally convex functions. Math. Program. Ser. A 175, 119–154 (2019)
Moriguchi, S., Murota, K., Tamura, A., Tardella, F.: Discrete midpoint convexity. Math. Oper. Res. 45, 99–128 (2020)
Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)
Murota, K.: Discrete convex analysis: A tool for economics and game theory. Journal of Mechanism and Institution Design 1, 151–273 (2016)
Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95–105 (1999)
Shioura, A., Tamura, A.: Gross substitutes condition and discrete concavity for multi-unit valuations: a survey. Journal of the Operations Research Society of Japan 58, 61–103 (2015)
Tamura, A., Tsurumi, K.: Directed discrete midpoint convexity. Jpn. J. Ind. Appl. Math. 38, 1–37 (2021)
Thomson, B.: Symmetric Properties of Real Functions. Marcel Dekker, New York (1994)