Discrete Midpoint Convexity

Satoko Moriguchi (), Kazuo Murota (), Akihisa Tamura () and Fabio Tardella ()
Additional contact information
Satoko Moriguchi: Department of Economics and Business Administration, Tokyo Metropolitan University, Tokyo 192-0397, Japan;
Kazuo Murota: Department of Economics and Business Administration, Tokyo Metropolitan University, Tokyo 192-0397, Japan;
Akihisa Tamura: Department of Mathematics, Keio University, Yokohama 223-8522, Japan;
Fabio Tardella: Department of Methods and Models for Economics, Territory and Finance, Sapienza University of Rome, Rome 00161, Italy

Mathematics of Operations Research, 2020, vol. 45, issue 1, 99–128

Abstract: For a function defined on the integer lattice, we consider discrete versions of midpoint convexity, which offer a unifying framework for discrete convexity of functions, including integral convexity, L ♮ -convexity, and submodularity. By considering discrete midpoint convexity for all pairs at ℓ ∞ -distance equal to 2 or not smaller than 2, we identify new classes of discrete convex functions, called locally and globally discrete midpoint convex functions . These functions enjoy nice structural properties. They are stable under scaling and addition and satisfy a family of inequalities named parallelogram inequalities . Furthermore, they admit a proximity theorem with the same small proximity bound as that for L ♮ -convex functions. These structural properties allow us to develop an algorithm for the minimization of locally and globally discrete midpoint convex functions based on the proximity-scaling approach and on a novel 2-neighborhood steepest descent algorithm.

Keywords: midpoint convexity; discrete convex function; integral convexity; L ♮ -convexity; proximity theorem; scaling algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2018.0984 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:99-128

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().