Projection and convolution operations for integrally convex functions

DOI10.1016/J.DAM.2018.08.010zbMATH Open1411.90227arXiv1710.04077OpenAlexW2963674841MaRDI QIDQ1727752FDOQ1727752

Authors: Satoko Moriguchi, Kazuo Murota 

Publication date: 20 February 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: This paper considers projection and convolution operations for integrally convex functions, which constitute a fundamental function class in discrete convex analysis. It is shown that the class of integrally convex functions is stable under projection, and this is also the case with the subclasses of integrally convex functions satisfying local or global discrete midpoint convexity. As is known in the literature, the convolution of two integrally convex functions may possibly fail to be integrally convex. We show that the convolution of an integrally convex function with a separable convex function remains integrally convex. We also point out in terms of examples that the similar statement is false for integrally convex functions with local or global discrete midpoint convexity.

Full work available at URL: https://arxiv.org/abs/1710.04077

Recommendations

• Integrality of subgradients and biconjugates of integrally convex functions
• On convolution ofL-convex functions
• Discrete 2-convex functions
• Notes on L-/M-convex functions and the separation theorems
• Scaling and proximity properties of integrally convex functions

zbMATH Keywords

integer programminginfimal convolutionMinkowski sumdiscrete convex analysisintegrally convex function

Mathematics Subject Classification ID

Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10)

Cites Work

• Discrete Convex Analysis
• Discrete fixed point analysis and its applications
• Title not available (Why is that?)
• Recent developments in discrete convex analysis
• Discrete fixed point theorem reconsidered
• Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella.
• Discrete convex analysis
• Notes on L-/M-convex functions and the separation theorems
• On the solutions of discrete nonlinear complementarity and related problems
• Solving discrete systems of nonlinear equations
• Existence of a pure strategy equilibrium in finite symmetric games where payoff functions are integrally concave
• Bisubmodular polyhedra, simplicial divisions, and discrete convexity
• Scaling, proximity, and optimization of integrally convex functions
• Discrete modeling of economic equilibrium problems
• Scaling and proximity properties of integrally convex functions

Cited In (8)

• On fundamental operations for multimodular functions
• Integrality of subgradients and biconjugates of integrally convex functions
• Discrete Fenchel duality for a pair of integrally convex and separable convex functions
• Directed discrete midpoint convexity
• Recent progress on integrally convex functions
• Scaling and proximity properties of integrally convex functions
• On basic operations related to network induction of discrete convex functions
• A survey of fundamental operations on discrete convex functions of various kinds

This page was built for publication: Projection and convolution operations for integrally convex functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1727752)