Projection and convolution operations for integrally convex functions

DOI10.1016/J.DAM.2018.08.010MaRDI QIDQ1727752zbMATH OpenOpenAlexFDO

Authors Satoko Moriguchi, Kazuo Murota

Publication date 20 February 2019

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

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

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)

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.

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

Cites work

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

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)