Integrality of subgradients and biconjugates of integrally convex functions

Kazuo Murota, Akihisa Tamura

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Integrally convex functions constitute a fundamental function class in discrete convex analysis. This paper shows that an integer-valued integrally convex function admits an integral subgradient and that the integral biconjugate of an integer-valued integrally convex function coincides with itself. The proof is based on the Fourier–Motzkin elimination. The latter result provides a unified proof of integral biconjugacy for various classes of integer-valued discrete convex functions, including L-convex, M-convex, L2-convex, M2-convex, BS-convex, and UJ-convex functions as well as multimodular functions. Our results of integral subdifferentiability and integral biconjugacy make it possible to extend the theory of discrete DC (difference of convex) functions developed for L- and M-convex functions to that for integrally convex functions, including an analogue of the Toland–Singer duality for integrally convex functions.

Original languageEnglish
Pages (from-to)195-208
Number of pages14
JournalOptimization Letters
Issue number1
Publication statusPublished - 2020 Feb 1


  • Biconjugate function
  • Discrete convex analysis
  • Fourier–Motzkin elimination
  • Integrality
  • Integrally convex function
  • Subgradient

ASJC Scopus subject areas

  • Control and Optimization


Dive into the research topics of 'Integrality of subgradients and biconjugates of integrally convex functions'. Together they form a unique fingerprint.

Cite this