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-(sic)-convexity, and submodularity. By considering discrete midpoint convexity for all pairs at l(infinity)-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-(sic)-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.

Discrete Midpoint Convexity / Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - 45:1(2020), pp. 99-128. [10.1287/moor.2018.0984]

Discrete Midpoint Convexity

Tardella, Fabio
2020

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-(sic)-convexity, and submodularity. By considering discrete midpoint convexity for all pairs at l(infinity)-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-(sic)-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.
2020
midpoint convexity; discrete convex function; integral convexity; L-(sic)-convexity; proximity theorem; scaling algorithm
01 Pubblicazione su rivista::01a Articolo in rivista
Discrete Midpoint Convexity / Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - 45:1(2020), pp. 99-128. [10.1287/moor.2018.0984]
File allegati a questo prodotto
File Dimensione Formato  
Tardella_Discrete-midpoint_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 11.66 MB
Formato Adobe PDF
11.66 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1368197
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
social impact