RIMS Summer School (COSS 2018), Kyoto, July 2018

Discrete Convex Analysis I:
Concepts of Discrete Convex Functions

Kazuo Murota(Tokyo Metropolitan University)

180726rimsCOSS1
1

Minimization and Convexity

W

local minglobal min

convex

nonconvex

2Convex Functionf (x)convexf (x)nonconvex

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

f (x) 6xz
y-λx + (1 − λ)yR = R ∪ {+∞}
3

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

Part II: Properties,

Part III: Algorithms
4

Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
3. conjugacy (Legendre transform)
4. separation theorem
5. Fenchel duality

5

C1.
Univariate
Discrete Convex Functions(Ingredients of convex analysis)6

Deﬁnition 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

Legendre Transformation (Intuition)
y 6

y 6

f (x)

-xf (x)-x9Legendre Transformation (Intuition)
y 6

y 6f (x)

-x

-x

10

Legendre Transformation (Intuition)y 6y 6f (x)--xy6xyx-

6x-11Legendre Transformationf : Z → Z (integer-valued)
Deﬁne 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Legendre Transformationf •(p) = sup{px − f (x) | x ∈ Z}y 6y 6f (x)--xy6f (x)xyx-6x-13

Conjugacy for Quadratic Function
f (x) = x2
1 2•2R: f (p) = max{px − x | x ∈ R} = p
41 2••f (x) = max{px − p | p ∈ R} = x24   pp•2
Z: f (p) = max{px − x | x ∈ Z} =·22   pp••f (x) = max px −·| p ∈ Z = x2
22

14

Separation Theorem
f :Z→Rconvex

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

15

Separation Theoremf (x)f :Z→Rconvex

p∗h:Z→Rconcaveh(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

16

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∈Z

17

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

18

C2.
Classes ofDiscrete Convex Functions

19Submodular Function

R = R ∪ {+∞}

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

ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )XX ∩YYcf. |X| + |Y | = |X ∪ Y | + |X ∩ Y |Set function ⇐⇒ Function on {0, 1}n20

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 ⇒ exponential(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 + Discreteness21

11th Math.Prog.Symp, Bonn, 198222

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
23

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

24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
25

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

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

27

Discrete Convex Functions
1. submodular(set fn)
1. separable-conv
1. integrally-conv
2. L-conv(Zn)

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

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

1990 Valuated matroid
Integrally convex fn

Dress–Wenzel
Favati–Tardella

1996 Discrete convex analysis
MurotaM/L/M/L
M.-Shioura, Fujishige-M.
2000 Submodular minimization algorithm
Iwata–Fleischer–Fujishige, Schrijver

2006 M-convex fn on jump system Murota
2012 L-convex fn on graph Hirai, Kolmogorov
29

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 ﬂow, resource allocation
economics, gamenetwork tension, image processing
OR (inventory, scheduling)
network ﬂow, matchingeconomics (game, auction)
mixed polynomial matrix
deg sequence, (2-)matching
polynomial (half-plane property)
multiﬂow, multifacility location
30

Integrally Convex Set

YESNO⊆ ZnNO31

Integrally Convex Set

YESNO

32

Integrally Convex Set

YESNO

33

Integrally Convex Set

YESNO

34

Integrally Convex Set

YESNO35

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

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

Local convex extension:f˜(x) = sup{p, x + α | p, y + α ≤ 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) = 1
f (x) = 036

Five Properties of “Convex” Functions
1. convex extension
2. local opt = global opt
3. biconjugacy (Legendre transform ×2)

hold, but
3. conjugacy (Legendre transform)
4. separation theorem
5. Fenchel duality

failfor

integrally convex functions
37

Discrete Convex Functions
1. submodular(set fn)
1. separable-conv
1. integrally-conv
2. L-conv(Zn)

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

Classes of Discrete Convex Functions
f : Zn → R
convex-extensible
integrally convex
M-convex
separable
convexL-convex

M ∩ L = separable
39

C3.
L-convex Functions40

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

(L = Lattice)(Murota 98)qp∨q

compnt-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-41

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

g : Zn → R

L-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  Ln42

L-convexity from Mid-pt-convexity(Favati-Tardella 1990, Fujishige–Murota 2000)
6qqq p+q p2-p+q2p=⇒pMid-point convex (g: Rn → R):
p+qg(p) + g(q) ≥ 2g2=⇒ Discrete mid-point convex (g : Zn → R)p+qg(p) + g(q) ≥ g2
L-convex function

p+q+g2(L = Lattice)43

Mid-pt Convexity for 01-Vectorsq

For p, q ∈ {0, 1}np+q2

6=p∨q

pp+q
2=p∧q

Discrete mid-pt convexity:
p+qp+qg(p) + g(q) ≥ g+g22⇐⇒ Submodularity:g(p) + g(q) ≥ g (p ∨ q) + g (p ∧ q)44

Translation Submodularity (L)g(p) + g(q) ≥ g((p − α1) ∨ q) + g(p ∧ (q + α1))
q + α1qpp(α ≥ 0)α=2
p − α1transl submodq

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)45

Rem: L-convex vs Submodular
n=1

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

46

Typical L-convex Function: Energy Function
πi: given
αi, αij ≥ 0ψi(pi) = αi|pi − πi|2
i pi

jpj

ψij (pi − pj ) = αij |pi − pj |2g(p) =i

ψi(pi) +ψij (pi − pj )is L-convexi=jψi, ψij : any univariate convex functions47

L-convex Function: Examples
Quadratic: g(p) =i⇔ aij ≤ 0aij pipj is L-convexj(i = j),aij ≥ 0 (∀i)

jEnergy function: For univariate convex ψi and ψij
g(p) =ψi(pi) +ψij (pi − pj )ii=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 g48

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

L-convex Function on Graphs(Hirai 12)

integer latticeoriented modular graphdirect product of trees:x(Kolmogorov 11)(Huber-Kolmogorov 12)y50

Mid-point Convexity on Tree Products(Hirai 13,15)x x+y2  x+y2 yf (x) + f (y) ≥ f

L-convex|| (def)
mid-point convex
x+y2+f

x+y2• submodular on (rooted) trees (Kolmogorov 11)• k-submodular (Huber-Kolmogorov 12)51

C4.
M-convex Functions

52

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

j6y6yyxx=⇒x iy y  x 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 > yif (x) + f (y) ≥ min f (x − ei) + f (y + ei),min {f (x − ei + ej ) + f (y + ei − ej )}xj <yjM-convex function(M = Matroid)53

M-convex Function
f : Zn → R ∪ {+∞}
ei: i-th unit vector(M = Matroid)j6y(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  Mn

6M
 MnM

-54

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

aij xixj is M-convexaij ≥ min(aik , ajk ) (∀k ∈ {i, j})

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

[unit preference]

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

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

M-concave Functions from Matroids
Matroid rank: f (X) = r(X) (rank of X) (Fujishige 05)
Matroid rank sum: f (X) =αiri(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 f56

Matching / Assignment
U

u1
u2
u3
u4

V
v1
v2
v3

X = {u1, u2}
v1
u1
u2
v2

X = {u1, u2}
v1
u1
u2
v3

M1

M2

EMax weight for X ⊆ Uf (X) = max{(w: given weight)

w(e) | M : matching, U ∩ ∂M = X}e∈M

Max-weight func f is M-concave (Murota 1996)• Proof by augmenting path
• Extension to min-cost network ﬂow57

Polynomial Matrix
A=s+1 s 1 01

1 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  ∈ B, i ∈ J \ J , there exists j ∈ J  \ Js.t. J − i + j ∈ B, J  + i − j ∈ B,
ω(J ) + ω(J ) ≤ ω(J − i + j) + ω(J  + i − j)
Ex. J = {1, 2},J  = {3, 4},
i=1det A[{1, 2}] = det A[{3, 4}] = 1,ω(J ) = ω(J ) = 0
Can take j = 3: J − i + j = {3, 2}, J  + i − j = {1, 4}
ω(J − i + j) = 1, ω(J  + i − j) = 158

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

M-convex functions⇒ Part II59

Five Properties (Summary/Preview)

submod.
(set fn)
separable-convex
integrally-convex
L-convex(Zn)
M-convex(Zn)convexext.
Ylocal opt/global opt
Y

Legendrebiconjug.
Yseparat.
theoremYFenchel
dualityYYYYYYYYYNNYYYYYYYYYY60

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

61཭ࢄತղੳ ͷ ࢀߟॻ
2001: ࣨా, ཭ࢄತղੳ, ‫ཱڞ‬ग़൛
2007: ࣨా, ཭ࢄತղੳͷߟ͔͑ͨ, ‫ཱڞ‬ग़൛2009: ాଜ, ཭ࢄತղੳͱήʔϜཧ࿦, ே૔ॻళ2013: ࣨా, ԘӜ, ཭ࢄತղੳͱ࠷దԽΞϧΰϦζϜ, ே૔2015: ݀Ҫɼ੪౻, ࠓ೔͔Β࢖͑Δʂ૊߹ͤ࠷దԽ, ߨஊࣾ62

Survey/Slide/Video/Software[Survey]
Murota: Recent developments in discrete convex analysis(Research Trends in Combinatorial Optimization,Bonn 2008, Springer, 2009, 219–260)
Murota: Discrete convex analysis: A tool for economics
and game theory. Journal of Mechanism and Institution
Design 1, 151–273 (2016)[Slide]http://www.comp.tmu.ac.jp/kzmurota/publist.html#DCA[Video]https://smartech.gatech.edu/xmlui/handle/1853/43257/
https://smartech.gatech.edu/xmlui/handle/1853/43258/[Software] DCP (Discrete Convex Paradigm)
https://ist.ksc.kwansei.ac.jp/∼tutimura/DCP/
63

E N D64