Abstract: M-convex functions form a class of well-behaved discrete convex functions. They are defined in terms of an exchange axiom and are characterized as functions obtained by piecing together M-convex sets in a consistent way or as collections of distance functions with some consistency. Fundamental properties of M-convex functions are established in this chapter, including the local optimality criterion for global optimality the proximity theorem for minimizers, integral convexity, and extensibility to convex functions. Duality and conjugacy issues are treated in Chapter 8 and algorithms in Chapter 10.6.1 M-Convex Functions and M♮-Convex FunctionsWe recall the definitions of M-convex functions and M♮-convex functions from section 1.4.2.A function ƒ : ZV → R ∪ {+∞} with dom ƒ ≠ ∅ is said to be an M-convex function if it satisfies the following exchange axiom:(M-EXC[Z]) For x, y ∈ dom ƒ and u ∈ supp+(x − y), there exists v ∈ supp−(x − y) such thatƒ(x)+ƒ(y)≥ƒ(x−χu+χυ)+ƒ(y+χu−χυ).(6.1)Inequality (6.1) implicitly imposes the condition that x − χu + χv ∈ dom ƒ and y + χu − χv ∈ dom ƒ.
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot