Hausdorff School: Economics and Tropical GeometryBonn, May 9-13, 2016

Discrete Convex Analysis I:
Concepts of Discrete Convex Functions
Kazuo Murota(Tokyo Metropolitan University)

160509BonnHCMecon11Convex Functionf (x)convexf (x)nonconvex

f : Rn → R is convex ⇐⇒λf (x) + (1 − λ)f (y) ≥ f (λx + (1 − λ)y)(0 < ∀ λ < 1)

f (x) 6xzky

-λx + (1 − λ)yR = R ∪ {+∞}
2

Features of Convex Functions• Occurrence in many models
motivations, applications• Operations and transformations• Sufficient structure for a theory
mathematically beautiful, practically useful• Minimization algorithms

3

Features of Convex Functions= Issues in discrete convex analysis• Occurrence in many models ?
motivations, applications• Operations and transformations ?

• Sufficient structure for a theory ?
mathematically beautiful, practically useful• Minimization algorithms ?

4Contents of Part I
Concepts of Discrete Convex Functions
C1. Univariate Discrete Convex Functions
C2. Classes of Discrete Convex Functions
C3. L-convex Functions
C4. M-convex Functions
C5. Remarks on Submodular Set Functions

Part II: Properties,

Part III: Algorithms5

C1.
Univariate
Discrete Convex Functions

Ingredients of convex analysis

6Definition of Convex Function
f :Z→R

R = R ∪ {+∞}f (x − 1) + f (x + 1) ≥ 2f (x)⇐⇒ f (x) + f (y) ≥ f (x + 1) + f (y − 1)

(x < y)⇐⇒ f is convex-extensible, i.e.,∃ convex f : R → R s.t. f (x) = f (x) (∀x ∈ Z)

convex

non-convex

7

Local vs Global Optimality
f :Z→R

Theorem:x∗: global opt (min)⇐⇒ x∗: local opt (min)f (x∗) ≤ min{f (x∗ − 1), f (x∗ + 1)}

convex

non-convex

8

Intuition of Legendre Transformationy 6y 6f (x)-xf (x)-x

9

Intuition of Legendre Transformationy 6y 6f (x)

-x-x

10

Intuition of Legendre Transformationy 6y 6f (x)

--x
y6xyx

-6x

-11

Legendre Transformationf : Z → Z (integer-valued)
Define discrete Legendre transform of f byf •(p) = sup{px − f (x) | x ∈ Z}
y 6 f (x)(p ∈ Z)y6−f •(p)slope p-x-x

Theorem:(1) f • is Z-valued convex function, f • : Z → Z(2) (f •)• = f(biconjugacy)
12Separation Theorem
f :Z→R
convex

f (x)

h:Z→R
concave

f (x)

p∗
h(x)

h(x)

Theorem (Discrete Separation Theorem)(1) f (x) ≥ h(x)(∀x ∈ Z) ⇒ ∃ α∗ ∈ R, ∃ p∗ ∈ R:

f (x) ≥ α∗ + p∗ x ≥ h(x)(∀x ∈ Z)(2) f , h: integer-valued ⇒ α∗ ∈ Z, p∗ ∈ Z

13

Separation Theoremf (x)f :Z→R
convexp∗

h:Z→R
concaveh(x)Theorem (Discrete Separation Theorem)(1) f (x) ≥ h(x)(∀x ∈ Z) ⇒ ∃ α∗ ∈ R, ∃ p∗ ∈ R:f (x) ≥ α∗ + p∗ x ≥ h(x)(∀x ∈ Z)(2) f , h: integer-valued ⇒ α∗ ∈ Z, p∗ ∈ Z

14

Fenchel Duality (Min-Max)
f : Z → Z: convex,
h : Z → Z: concave
Legendre transforms:f •(p) = sup{px − f (x) | x ∈ Z}h◦(p) = inf {px − h(x) | x ∈ Z}

Theorem:inf {f (x) − h(x)} = sup {h◦(p) − f •(p)}x∈Zp∈Z15

Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
3. Legendre transform (biconjugacy)
4. separation theorem
5. Fenchel duality
hold for univariate discrete convex functions

16

C2.
Classes ofDiscrete Convex Functions

17

Classes of Discrete Convex Functions
1. Submodular set fn (on {0, 1}n)1. Separable-convex fn on Zn
1. Integrally-convex fn on Zn
2. L-convex (L\-convex) fn on Zn
2. M-convex (M\-convex) fn on Zn
3. M-convex fn on jump systems
3. L-convex fn on graphs
18Submodular Function

R = R ∪ {+∞}

Set function ρ : 2V → R is submodular⇐⇒X ∪Y

ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )XX ∩Y

Ycf. |X| + |Y | = |X ∪ Y | + |X ∩ Y |Set function ⇐⇒ Function on {0, 1}n19

Separable-convex Function
f : Zn → R is separable-convex⇐⇒f (x) = ϕ1(x1) + ϕ2(x2) + · · · + ϕn(xn)ϕi: univariate convex
ϕi 6-20

Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
3. Legendre transform (biconjugacy)
4. separation theorem
5. Fenchel duality
hold for separable discrete convex functions

21

Some History
1935 Matroid
Whitney, Nakasawa
1965 Submodular function
Edmonds
1969 Convex network flow (electr.circuit) Iri
1982 Submodularity and convexity
Frank, Fujishige, Lovász

1990 Valuated matroid
Integrally convex fn
1996 Discrete convex analysis

Dress–Wenzel
Favati–Tardella
Murota2000 Submodular minimization algorithm
Iwata–Fleischer–Fujishige, Schrijver

2006 M-convex fn on jump system Murota
2012 L-convex fn on graph Hirai, Kolmogorov
22Motivations/Applications/Connections
1. submodular
1. separable-conv
1. integrally-conv
2. L-conv (Zn)
2. M-conv (Zn)

3. M-conv (jump)
3. L-conv (graph)

MANY problems
graph cut, convex game
MANY problems
min-cost flow, resource allocation[mathematical aesthetics]
network tension, image processing
OR (inventory, scheduling)
network flow, conjestion gameeconomics (game, auction)
mixed polynomial matrix
deg sequence, (2-)matching
polynomial (half-plane property)
multiflow, multifacility location
23

Books (discrete convex analysis)
2000: Murota, Matrices and Matroids for Systems
Analysis, Springer
2003: Murota, Discrete Convex Analysis, SIAM
2005: Fujishige, Submodular Functions andOptimization, 2nd ed., Elsevier
2014: Simchi-Levi, Chen, Bramel,
The Logic of Logistics, 3rd ed., Springer

24

Convex Extension•f : Zn → R is convex-extensible⇔ ∃ convex f : Rn → R: f (x) = f (x) (∀x ∈ Zn)•f is a convex extension of f•convex closure= (pointwise) max convex extension

convex-extensible

NOT convex-extensible

25Integrally Convex Function
N (x) = {y ∈ Zn | kx − yk∞ < 1}x

(Favati-Tardella 1990)(x ∈ Rn)x

Local convex extension:f˜(x) = sup{hp, xi + α | hp, yi + α ≤ f (y) (∀y ∈ N (x))}
p,αDef: f is integrally convex ⇐⇒f˜ is convex

Ex: f (x1, x2) = |x1 − 2x2| is NOT integrally convex

f =1
f =0

f =0x = (1, 1/2)
f =1f˜(x) = 1f (x) = 0
26

Integrally Convex Set

YESNO

27

Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
hold for integrally convex functions
3. Legendre transform (biconjugacy)
4. separation theorem
5. Fenchel duality
fail for integrally convex functions
28

Definitions
1. submodular(set fn)
1. separable-conv1. integrally-conv
2. L-conv(Zn)ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )f (x) = ϕ1(x1) + ϕ2(x2) + · · · + ϕn(xn)ϕi(t − 1) + ϕi(t + 1) ≥ 2ϕi(t) (∀t ∈ Z)
Local convex ext f˜(x) is convex

2. M-conv(Zn)
3. M-conv(jump)
3. L-conv(graph)29

Classes of Discrete Convex Functions
f : Zn → R
convex-extensible
integrally convex
submodM\-convex
set fnseparableconvex
L\-convex

L-convex
on graphM-convex
on jump30

Bivariate L\- and M\-convex Functionsf (x)g(p)

x2
p2

p1x1

L\-convex fn

M\-convex fn31

C3.
L-convex Functions

32

L-convex Function
g : Zn → R ∪ {+∞}p∨q
p∧q

(L = Lattice)(Murota 98)

qp∨qcompnt-max
compnt-min

pp∧q
Def: g is L-convex ⇐⇒• Submodular:g(p) + g(q) ≥ g(p ∨ q) + g(p ∧ q)

• Translation:∃r, ∀p:g(p + 1) = g(p) + r

1 = (1, 1, . . . , 1)
6L
L\-33

L\-convexity from Submodularity(Murota 98, Fujishige–Murota 2000)

g : Zn → RL\-convex ⇐⇒g̃(p0, p) = g(p − p01) is submodular in (p0, p)g̃ : Zn+1 → R,

1 = (1, 1, . . . , 1)g̃(p̃) + g̃(q̃) ≥ g̃ (p̃ ∨ q̃) + g̃ (p̃ ∧ q̃)q̃p̃ ∧ q̃p̃ ∨ q̃p̃

Ln+1 ' L\n ) Ln34

L\-convexity from Mid-pt-convexity(Favati-Tardella 1990, Fujishige–Murota 2000)
6qq

q p+q p2

-p+q2=⇒ppMid-point convex (g: Rn → R):
p+qg(p) + g(q) ≥ 2g2=⇒ Discrete mid-point convex (g : Zn → R)

lp+qg(p) + g(q) ≥ g2
L\-convex function

m

jk

p+q+g2(L = Lattice)35

Mid-pt Convexity for 01-Vectors
qFor p, q ∈ {0, 1}n
jp+q2

k

l

6p+q2

m=p∨q

p=p∧q

Discrete mid-pt convexity:
lm
jk
p+q
p+q
g(p) + g(q) ≥ g+g2
2⇐⇒ Submodularity:g(p) + g(q) ≥ g (p ∨ q) + g (p ∧ q)36

Translation Submodularity (L\)g(p) + g(q) ≥ g((p − α1) ∨ q) + g(p ∧ (q + α1))
q + α1pα=2p − α1q(α ≥ 0)

qp
discrete mid-pt convexg̃(p0, p) = g(p − p01) is submodular in (p0, p)⇔ translation submodular⇔ discrete mid-pt convex⇔ submod. integ. convex(Fujishige-Murota 00)(Fujishige-Murota 00)(Favati-Tardella 90)37

Rem: L\-convex vs Submodular
n=1

Fact 1: Every g : Z → R is submodular
Fact 2: Function g : Z → R is L\-convex⇐⇒g(p − 1) + g(p + 1) ≥ 2g(p) for all p ∈ Z

38

L\-convex Function: Examples
Quadratic: g(p) =XXi⇔ aij ≤ 0aij pipj is L\-convex

j(i 6= j),

Xaij ≥ 0 (∀i)

j

Energy function: For univariate convex ψi and ψij
XXg(p) =ψi(pi) +ψij (pi − pj )ii6=jRange: g(p) = max{p1, p2, . . . , pn} − min{p1, p2, . . . , pn}
Submodular set function: ρ : 2V → R⇔ ρ(X) = g(χX ) for some L\-convex g
Multimodular: h : Zn → R is multimodular ⇔h(p) = g(p1, p1 + p2, . . . , p1 + · · · + pn) for L\-convex g39Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
3. Legendre transform (biconjugacy)
4. separation theorem
5. Fenchel duality
hold for L-convex functions⇒ Part II40

Bivariate L\- and M\-convex Functions
f (x)

g(p)

x2
p2

p1

x1

L\-convex fn

M\-convex fn

41

C4.
M-convex Functions42

M\-convexity from Equi-dist-convexity(Murota 1996, Murota –Shioura 1999)

j6

y6

yy0x0

=⇒x-x i-y y 0 x0 x
Equi-distance convex (f : Rn → R):

f (x) + f (y) ≥ f (x − α(x − y)) + f (y + α(x − y))=⇒ Exchange (f : Zn → R) ∀x, y , ∀i : xi > yif (x) + f (y) ≥ min f (x − ei) + f (y + ei),min {f (x − ei + ej ) + f (y + ei − ej )}xj <yj

M\-convex function(M = Matroid)43M-convex Function
f : Zn → R ∪ {+∞}
ei: i-th unit vector(M = Matroid)j
6y(Murota 96)

Def: f is M-convex⇐⇒ ∀x, y ,∀i : xi > yi,x i-∃j : xj < yj :f (x) + f (y) ≥ f (x − ei + ej ) + f (y + ei − ej )dom f ⊆ const-sum hyperplane\Mn+1 ' Mn6M) Mn
M\-44Gross Substitutes (for set function)f : 2V → R
putility (reservation value) function

price vector

D(p) = arg max(f −p) = {X | f (X)−p(X) is maximum}
demand correspondence

Gross substitutes property: (Kelso–Crawford 82)
X ∈ D(p), p ≤ q⇒ ∃ Y ∈ D(q) : {i ∈ X | pi = qi} ⊆ Y
Equiv. cond. for D(p)Equiv. cond. for f(Gul–Stacchetti 99)(Reijnierse–van Gallekom–Potters 02)& equivalence to M\-concavity (Fujishige–Yang 03)
45

Gross Substitutes for f (not for D(p))
f : 2V → R(set function)f : gross substitutes ⇐⇒(i) f (S ∪ {i, j}) + f (S) ≤ f (S ∪ {i}) + f (S ∪ {j})(submodular)(ii) f (S ∪ {i, j}) + f (S ∪ {k}) ≤max[f (S ∪ {i, k}) + f (S ∪ {j}), f (S ∪ {j, k}) + f (S ∪ {i})](Reijnierse–van Gallekom–Potters 02)

cf. Local exchange axiom of M\-concave functions46

M\-concavity = Gross Substitutes
f : Zn → RM\-concave ⇐⇒ Gross substitutes (+ ∗ ∗)(Reijnierse–van Gallekom–Potters 02, Fujishige-Yang 03
Danilov-Koshevoy-Lang 03, Murota -Tamura 03)⇒ Shioura-Tamura’s survey (J. OR. Soc. Japan, 2015)
https://www.jstage.jst.go.jp/article/jorsj/58/1/58 61/ pdf

Gross substitutes:(f : utility, p: price)x ∈ arg max(f − p), p ≤ q ,⇒∃ y ∈ arg max(f − q) : yi ≥ xiif pi = qi47

M\-convex Function: Examples
Quadratic: f (x) =⇔ aij ≥ 0,X

aij xixj is M\-convex

aij ≥ min(aik , ajk ) (∀k 6∈ {i, j})

Min value: f (X) = min{ai | i ∈ X}

[unit preference]

Cardinality convex: f (X) = ϕ(|X|)
X
Separable convex: f (x) =ϕi(xi)X
ϕA(x(A))
Laminar convex: f (x) =(ϕ: convex)(ϕi: convex)(ϕA: convex)

A{A, B, ....}: laminar ⇔ A ∩ B = ∅ or A ⊆ B or A ⊇ B

48

M\-concave Functions from Matroids
Matroid rank: f (X) = r(X) (rank of X)
Xαiri(X)
Matroid rank sum: f (X) =ri ← ri+1 (strong quotient), αi ≥ 0 (Shioura 12)
Weighted matroid: w: weight vectorf (X) = max{w(Y ) | Y : indep ⊆ X}

(Shioura 12)

Valuated matroid: ω : 2V → R⇔ ω(X) = f (χX ) for some M-concave f49

Matching / Assignment
U

u1
u2
u3
u4

V
v1
v2
v3

X = {u1, u2}
u1
v1
u2
v2

X = {u1, u2}
u1
v1
u2
v3

M1
M2
EMax weight for X ⊆ U(w: given weight)
Xf (X) = max{w(e) | M : matching, U ∩ ∂M = X}e∈M

Max-weight func f is M\-concave(cf. Murota 1996)• Proof by augmenting path
Assignment valuation is GS(cf. Hatfield-Milgrom 2005)
50

Polynomial Matrix
A=s+1 s 1 0
11 1 1(Dress-Wenzel 90)

Valuated Matroid

ω(J ) = deg det A[J ]B = {J | J is a base of column vectors}
Grassmann-Plücker ⇒ Exchange (M-concave)
For any J, J 0 ∈ B, i ∈ J \ J 0, there exists j ∈ J 0 \ J
s.t. J − i + j ∈ B, J 0 + i − j ∈ B,
ω(J ) + ω(J 0) ≤ ω(J − i + j) + ω(J 0 + i − j)
Ex. J = {1, 2},
J 0 = {3, 4},
i=1
det A[{1, 2}] = det A[{3, 4}] = 1,ω(J ) = ω(J 0) = 0Can take j = 3: J − i + j = {3, 2}, J 0 + i − j = {1, 4}
ω(J − i + j) = 1, ω(J 0 + i − j) = 151

Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
3. Legendre transform (biconjugacy)
4. separation theorem
5. Fenchel duality
hold for M-convex functions⇒ Part II52

C5.
Remarks on
Submodular Set Functions

53

Submodularity & Convexity in 1980’s
ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )• min/max algorithms(Grötschel–Lovász–Schrijver/ Jensen–Korte, Lovász)

min ⇒ polynomial,• Convex extension

max ⇒ NP-hard(Lovász)

set fn is submod ⇔ Lovász ext is convex• Duality theorems(Edmonds, Frank, Fujishige)

discrete separation, Fenchel min-max

Submodular set functions= Convexity + Discreteness54

Set Function and Extensions
Set function ⇐⇒ Function on {0, 1}n=ρ(X)ρ̂(χX )
Every set function ρ : {0, 1}n → R can beextended to convex/concave function
610convex ext
01-

6

concave ext

1001-

cf. Lovász extension
55

Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
3. Legendre transform (biconjugacy)
4. separation theorem
5. Fenchel duality
hold for submodular set functions(1980’s)

56Submodular Set Function in DCA• Submodular set fn = L\-convex on {0, 1}n• M\-concave fns form a nice subclass• M\ + M\ are polynomially tractable• Sums of M\-concave fns are still OK
f : {0, 1}n → R
submod=L\-convex

f : Zn → R
submodular

M\ + M \M\-concave

M\ concave

L\ convex

57

Dual Character of Matroid Rank Fn
Given a matroid:

ρ(X) = max{|I| | I : independent, I ⊆ X}
is L\-convex and M\-concave

Polymatroid rank function is NOT M\-concave58

E N D59