Modern Aspects of Submodularity, Georgia Tech, March 19, 2012

Introduction toDiscrete Convex Analysis
Kazuo Murota (U. Tokyo)

120319atlanta1Intro1

Discrete Convex Analysis
Convexity Paradigm in Discrete Optimization

Matroid Theory + Convex Analysis
Submodular fn ↔ Matroid base⇓⇓L-convex fn↔ M-convex fn6-

• Global optimality ⇐⇒ local optimality• Conjugacy:

Legendre–Fenchel transform• Duality (Fenchel min-max, discrete separation)• Minimization algorithms• Applications:OR, game, economics, matrices
2Applications• Combinatorial optimization– matching, even factor, min-cost ﬂow,
shortest path, min-cost tension• Mathematical economics / Game theory– indivisible goods, stable marriage• Operations research– inventory, queueing, resource allocation• Discrete structures– ﬁnite metric space• Algebra– polynomial matrix, tropical geometry3Some History
1935 Matroid

Whitney

1965 Submodular function

Edmonds

1975 Engrg application of matroid

Iri, Recski

1983 Submodularity and convexity
Lovász, Frank, Fujishige
1990 Valuated matroid
Integrally convex fn

Dress–Wenzel
Favati–Tardella

1996 Discrete convex analysis

Murota2000 Submod. fn minimization algorithm
Iwata–Fleischer–Fujishige, Schrijver

4

Contents
B0. Brief Overview
B1. Submodularity and Convexity (1980’s)
B2. L-convex and M-convex Functions
B3. Conjugacy — Legendre transform
B4. Duality
B5. Discrete Hessian5

B1.
Submodularity and Convexity(1980’s)

6Submodular Function
Set function ρ is submodular:X ∪Y

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

g : Zn → R

is submodular:g(p) + g(q) ≥ g(p ∨ q) + g(p ∧ q)

q

X ∩YY

compnt-maxp∨qp∧qcompnt-minp7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

Duality for submodular set functions= Convexity + Discreteness8Frank’s Discrete Separation(Frank 82)

ρ : 2V → R: submodular(ρ(∅) = 0)

µ : 2V → R: supermodular(µ(∅) = 0)

● ρ(X) ≥ µ(X)(∀X ⊆ V ) ⇒ρ(X) ≥ x∗(X) ≥ µ(X)∃ x∗ ∈ RV :(∀X ⊆ V )● ρ, µ: integer-valued ⇒ x∗ ∈ ZV

Equivalent to Edmonds’ polymatroid intersection
9B2.
L-convex and M-convex
Functions10Discrete Convex Functions
f : Zn → Rfunctions Zn → R
convex-extensible

M\ Separable

L\f is convex-extensible⇔ ∃ convex f :f (x) = f (x)Convex-extensibility does not help much11

L\-convexity from Mid-pt-convexity(Murota 98, Fujishige–Murota 00)
6qqq p+q p
2-p+q2=⇒ppMid-point convex (g : Rn → R):g(p) + g(q) ≥ 2g  p+q2=⇒ Discrete mid-point convex (g : Zn → R)












p+qp+qg(p) + g(q) ≥ g
2  + g
2
L\-convex function(L = Lattice)




12

Mid-pt Convexity for 01-Vectors
For p, q ∈ {0, 1}nq6







p+q  = p ∨ q2 p
p+q = p ∧ q
2Discrete mid-pt convexity:

 p+q p+qg(p) + g(q) ≥ g  2  + g  2 ⇐⇒ Submodularity:g(p) + g(q) ≥ g (p ∨ q) + g (p ∧ q)13

L\-convexity from Submodularity—Original deﬁnition of L\-convexity—

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

1 = (1, 1, . . . , 1, 1)

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

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

L\-convex vs Submodular• L\-convex function is convex-extensible• General submodular function is NOT

Fact 1:
Any function g : Z → R is submodular⇒ Submodularity does not guarantee convexity

Fact 2:A function g : Z → R is L\-convex⇐⇒ g(p − 1) + g(p + 1) ≥ 2g(p) for all p ∈ Z(This slide shows my answer to a question during the talk)16

L\-convex Function: Examples
Quadratic: g(p) =⇔ aij ≤ 0n∑n∑

i=1 j=1

aij pipj is L\-convex(i 6= j),n∑j=1aij ≥ 0 (∀i)

Separable convex: For univariate convex ψi and ψijg(p) =n∑i=1ψi(pi) +∑i6=j

ψij (pi − pj )Range: g(p) = max{p1, p2, . . . , pn} − min{p1, p2, . . . , pn}
Submodular set function: ρ : 2V → R⇔ ρ(X) = g(χX ) for L\-convex g
Multimodular: h : Zn → R is multimodular ⇔h(p) = g(p1, p1 + p2, . . . , p1 + · · · + pn) for L\-convex g
17

M\-convexity from Equi-dist-convexity(Murota 96, Murota–Shioura 99)
6

jy6

yy0x0

=⇒
xx iy 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 > 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)18

Tree: Exchange Property
eeGiven pairof trees

e0TT0..........................................

eee0
T − e + e0e0
T 0 + e − e0

New pairof trees

Exchange property: For any T, T 0 ∈ T , e ∈ T \ T 0
there exists e0 ∈ T 0 \ T s.t. T − e + e0 ∈ T , T 0 + e − e0 ∈ T19

Discrete Convex Functions
f (x)

g(p)

x2
p2

p1x1

L\-convex fnM\-convex fn20

Matching / Assignment
U
u1
u2
u3
u4

Vv1
v2
v3{u1, u2}
u1
u2

v1
v2{u1, u2}
u1u2

v3

E

M1

Max weight for X ⊆ Uf (X) = max{∑e∈M

v1

M2(w: given weight)

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

Max-weight function f is M\-concave(Murota 96)• Proof by augmenting path
• Extension to min-cost network ﬂow
21

M\-concavity = Gross Substitutes
Think of f as a utility function
M\-concave ⇐⇒ Gross substitutes
Reijnierse–van Gallekom–Potters 02, Fujishige-Yang 03
Danilov-Koshevoy-Lang 03, M.-Tamura 03

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

if pi = qi=⇒ Applications to economics / game theory
22

Polynomial Matrix(Dress-Wenzel 90)

A=s+1 s 1 01

1 1 1

ω(J ) = deg det A[J ]B = {J | J is a base of column vectors}
Grassman-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) = 123

S u m m a r yFrom Continuous to Discrete
Convex: λf (x) + (1 − λ)f (y) ≥ f (λx + (1 − λ)y)Mid-pt convex: f (x) + f (y) ≥ 2f ( x+y2 )


 x+y x+y−→ Discrete mid-pt conv: ≥ f  2  + f  2 Equi-dist: f (x)+f (y) ≥ f (x−α(x−y))+f(y +α(x−y))





−→ Exchange: ≥ min f (x − ei) + f (y + ei),





min {f (x − ei + ej ) + f (y + ei − ej )}Cont Rn → R
mid-pt convmconvex
mequi-dist conv

xj <yjDisc Zn → R−→ disc mid-pt
discr (L\-convex)(M\-convex)−→ exchange

discrjy6~}
-x i
24

B3.
Conjugacy— Legendre transform25

Conjugacy in Polymatroids
Polyhedron S

Submodular fn ρ

S = {x | x(A) ≤ ρ(A) ∀A} ←→ ρ(A) = max x(A)x∈S26

Conjugacy in Polymatroids
Polyhedron S

Submodular fn ρ

S = {x | x(A) ≤ ρ(A) ∀A} ←→ ρ(A) = max x(A)x∈SIndicator fn of SLovász ext. of ρf (x) ∈ {0, +∞}g(p)→: g(p) = max hp, xi = max[hp, xi − f (x)] = f •(p)xx∈S←: f (x) = max[hp, xi − g(p)] = g •(x)p

Legendre transform
M\-convex
L\-convex
27

M-L Conjugacy Theorem
Integer-valued discrete fn
Legendre transform:f : Zn → Zf •(p) = sup [hp, xi − f (x)]x∈ZnM\-convex and L\-convex are conjugate
f 7→ f • = g 7→ g • = f(Murota 98)

function Zn → Z
convex-extensible

M\L\28

History of Discrete Conjugacy
Matroid bases←→ Matroid rank fnWhitney 35

Whitney 35⇓⇓

Polymatroid
Edmonds 70⇓
Valuated matroid
Dress–Wenzel 90⇓

M-convex fn
Murota 96

mM\-convex fn
Murota-Shioura 99←→Submodular fn
Edmonds 70⇓
Lovász extension||
Lovász 83|⇓| Submod. integ. conv. fn|
Favati-Tardella 90⇓←→ L-convex fn
Murota 98m←→ L\-convex fn
Fujishige–Murota 00

29

B4.
Duality30

Duality: Separation Theorem
main issue in convexity paradigm
f (x)

f (x)

p∗h(x)

h(x)f : Rn → R convex
h : Rn → R concave
f (x) ≥ h(x)(∀x) ⇒∃ α∗ ∈ R,f (x) ≥ α∗ + hp∗, xi ≥ h(x)∃ p∗ ∈ Rn:(x ∈ Rn)
31

Discrete Separation Theoremf (x)f : Zn → R “convex”
h : Zn → R “concave”● f (x) ≥ h(x)

f (x)

p∗

(∀x ∈ Zn) ⇒h(x)h(x)∃ α∗ ∈ R,∃ p∗ ∈ Rn:

f (x) ≥ α∗ + hp∗, xi ≥ h(x)(x ∈ Zn)● f , h: integer-valued ⇒ α∗ ∈ Z, p∗ ∈ Zn

32

Frank’s Discrete Separation(Frank 82)

ρ : 2V → R: submodular(ρ(∅) = 0)

µ : 2V → R: supermodular(µ(∅) = 0)

● ρ(X) ≥ µ(X)(∀X ⊆ V ) ⇒ρ(X) ≥ x∗(X) ≥ µ(X)∃ x∗ ∈ RV :(∀X ⊆ V )● ρ, µ: integer-valued ⇒ x∗ ∈ ZV

Equivalent to Edmonds’ polymatroid intersection
33

Diﬃculty of Discrete Separation (1)f (x, y) = max(0, x + y) convex
h(x, y) = min(x, y)concave

separablebutnonintegralp∗ = (1/2, 1/2), α∗ = 0 unique separating plane34

Diﬃculty of Discrete Separation (2)Even real-separation is nontrivial
f (x, y) = |x + y − 1|convexh(x, y) = 1 − |x − y|concave

2-2-101

120
4-1
2-20-2• f (x, y) ≥ h(x, y) (∀(x, y) ∈ Z2) true
• f (x, y) ≥ h(x, y) (∀(x, y) ∈ R2) not truesince f = 0 < h = 1 at (x, y) = (1/2, 1/2)=⇒ No α∗ ∈ R, p∗ ∈ R2 satisﬁes
f (x) ≥ α∗ + hp∗, xi ≥ h(x)35Discrete Separation Theorems(Murota 96/98)

M-separation Thm: M\-convex fn⊃ Weight splitting for weighted matroid intersection(Iri-Tomizawa 76, Frank 81)(linear fn, indicator fn = M\-convex fn)

L-separation Thm: L\-convex fn⊃ Discrete separation for submod. set function(Frank 82)(submod. set fn = L\-convex fn on 0–1 vectors)
36M-convex Intersection:
f1, f2 : M\-convex(Zn → R),

Min [M\+M\]
M\+M\ is NOT M\x∗ ∈ domf ∩ domf

(1) x∗ minimizes f1 + f2

12

(Murota 96)⇐⇒ ∃ p (certiﬁcate of optimality)• x∗ minimizes f (x) − hp, xi(M-opt thm)

f2(x) + hp, xi(M-opt thm)• x∗ minimizes

1(2) argmin (f1 + f2) = argmin (f1 − p) ∩ argmin (f2 + p)(3) f1, f2 are integer-valued ⇒ integral p=⇒ Frank’s weight splitting thm for matroid intersec.
37

Min-Max Duality
Legendre–Fenchel transformf •(p) = sup{hp, xi − f (x) | x ∈ Zn}h◦(p) = inf {hp, xi − h(x) | x ∈ Zn}

Fenchel-type duality thm(Murota 96, 98)

f : M\-convex

h: M\-concave（Zn → Z）

self-conjugate（f •: L\-convh◦: L\-conv)◦•
inf n{f (x) − h(x)} = sup {h (p) − f (p)}x∈Zp∈Zn=⇒ Edmonds’ matroid intersection thm38

Relation among Duality Thms
Discrete Convex

Combinatorial Opt.

M-separationf (x) ≥ Lin ≥ h(x)mFenchel duality
inf {f − h}= sup{h◦ − f •}m

L-separationf •(p) ≥ Lin ≥ h◦(p)

Fenchel duality (Fujishige 84)
matroid intersect. (Edmonds 70)m

⇒ discrete separ. for submod(Frank 82)⇒ valuated matroid intersect.
(M. 96)⇓weighted matroid intersect.
(Edmonds 79, Iri-Tomizawa 76,Frank 81)
39

B5.
Discrete Hessian40

Discrete Hessian Matrix
Hij (x) = f (x + ei + ej ) − f (x + ei) − f (x + ej ) + f (x)H11(0, 0) = f (2, 0) − 2f (1, 0) + f (0, 0)
H12(0, 0) = f (1, 1) − f (1, 0) − f (0, 1) + f (0, 0)

x2
6

-x1

Question:
Hessian º O ⇐?⇒ Convex Extensible⇐=6by a simple example
f (x1, x2) = |x1 − x2|

H(0, 0) =


0 −2 −20

41

Hessian º O 6⇒ Convex Extensible
Counterexample by semideﬁnite programming(Moriguchi–M. 12)

1098
7x2 6
5432
10

100735029
11−3−15−24−23−151045
21
1−17−32−44−52−48−35−151f : Z2 → Z
H(x1, x2) º O−4−25 −47
−43 −64 −56−57 −79 −71 −59−69 −91 −82 −71−78 −100 −91 −79−66 −78 −69 −57−48 −52 −44 −32−23 −24 −15 −32345x1−56−64 −47−43 −25 −4−171 21 45
1129 50 73 100
678 9 10convexity fails ( -35 − 2 × -66 + -100 = −3)42

Hessian for M\-/L\-convexity
M\-convexity:(Hirai-M. 04, M. 07)
f : Zn → R is M\-convex ⇐⇒ For each x ∈ Zn:• Hij (x) ≥ min(Hik (x), Hjk (x)) if {i, j} ∩ {k} = ∅• Hij (x) ≥ 0 for any (i, j)
combinatorial cond. stronger than H(x) º O
cf. “ultra metric” in ﬁnite metric space

L\-convexity: modiﬁed H̃ij (x)• H̃ii(x) ≥ Σj6=i|H̃ij (x)|(Moriguchi-M. 05)• H̃ij (x) ≤ 0 for any i 6= j43

Books/Surveys
Murota: Discrete Convex Analysis, SIAM, 2003
Fujishige: Submodular Functions and Optimization,
2nd ed., Elsevier, 2005 (Chap. VII)

M. 01

M. 07

Tamura 09

Murota: Recent developments in discrete convex analysis,
in: Research Trends in Combinatorial Optimization,
Bonn 2008, Springer, 2009, Chap. 11, 219–260.
44

E N D45