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

Discrete Convex Analysis II:
Properties of Discrete Convex Functions
Kazuo Murota(Tokyo Metropolitan University)

160510BonnHCMecon2
1Features of [Discrete] Convex Functions• Occurrence in many models
motivations, applications• Operations and transformations• Sufficient structure for a theory
mathematically beautiful, practically useful• Minimization algorithms=⇒ Part III2

Local min = Global min=? neighbors poly-time alg
submodular(set fn)
separable-conv–

integrally-conv

YL-conv (Zn)

YM-conv (Zn)

YYx∗3

Contents of Part II
Properties of Discrete Convex Functions
P1. Convex Extension
P2. Operations
P3. Conjugacy
P4. Duality

4

P1.
Convex Extension

5

Convex Extension
f : Zn → R is convex-extensible⇔ ∃ convex f : Rn → R: f (x) = f (x) (∀x ∈ Zn)

Theorem:(1) Separable-convex fns are convex-extensible(2) L\-convex fns are convex-extensible(Murota 98)(3) M\-convex fns are convex-extensible(Murota 96)(4) Integrally-convex fns are convex-extensible (by def)6

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

7

P2.
Operations

8

Operations• scaling: af (x) + b,f (ax + b)

• linear addition: f (x) + hp, xi• section: f (x, 0)• projection: min f (x, y)y• sum: f1(x) + f2(x)• convolution: (f12f2)(x) = min(f1(y) + f2(x − y))y• transformation by graphs/networks

9

Scaling/Linear Additionaf (x)f (sx)f (−x) f (x)+(a > 0) (s ∈ Z+)
hp, xisubmodular
Y—Y*Y(set fn)
V \Xseparable-convYYY
Y±xi
integrally-conv
Y
Y*Y
Y(n = 2)±xi
L-conv (Zn)
YY
YY
M-conv (Zn)

YN

Y

Y

10

Section/Projection
submodular(set fn)
separable-conv
integrally-conv
L-conv (Zn)
L\-conv
M-conv (Zn)M\-conv

sectionprojection
f (x, 0)miny f (x, y)YY
restriction contraction
YY
Y
N

Y
Y
Y

YY
YNY

11

Sum and Convolution• (f1 + f2)(x) = f1(x) + f2(x)Theorem:f1, f2 : L-convex
L\-convex(Murota 98)=⇒ f1 + f2: L-convex=⇒L\-convex
f1, f2, . . . , fk : L (L\) =⇒ f1 + f2 + · · · + fk : L (L\)• (f12f2)(x) = min(f1(y) + f2(x − y))yTheorem:f1, f2 : M-convex
M\-convex(Murota 96)=⇒ f12f2: M-convex=⇒M\-convex
f1, f2, . . . , fk : M (M\) =⇒ f12f22 · · · 2fk : M (M\)
Rem:

M + M is not M,

L 2 L is not L
12Significance of M-convolution Thm
Concave convolution:(U12U2)(x) = max(U1(y) + U2(x − y))y

U1, U2, . . . , Uk : gross-substitute (M\-concave)⇒ aggregated utility U12U22 · · · 2Uk isgross-substitute (M\-concave)13Sum/Convolution
submodular(set fn)
separable-convsum f1 + f2
Ymin (ρ1(Y ) + ρ2(X \ Y ))

Y ⊆X

Y

integrally-conv
L-conv (Zn)
M-conv (Zn)convolution f1 2 f2
N matroid intersec
YNY

N
N → L2-convex

N → M2-conv Y
matr.intersec matroid union14

Transformation by Graph/NetworkGiven
G, f, c→x →→→→g(·)→ y→f (·)

cmin{f (x) + c(ξ) | x ←→ y} =: g(y)↑∃ flow ξ : ∂ξ = x ⊕ (−y)∃ matching M : ∂M = X ∪ YTheorem:f : M-convex
M\-convex(Murota 96)=⇒ g : M-convex=⇒M\-convex
15

Independent Assignment Valuation
G = (V, W ; E): bipartite graph, w: edge weight(V, I): matroid (I : indep. sets)
V
Corollary:g(Y ) = max{w(M ) | M : matching,V ∩ ∂M ∈ I, W ∩ ∂M = Y }IWg(·)

Mw

is M\-concave

16

Transformation by NetworkS
f (x)
g(p)

x, y : flowp, q : potential(fa, ga)--1j-jO*WjN

M-convex (Zn):(y ∈ ZT )f˜(y) = inf {f (x) +ξ,xXsq

>

Tf˜(y)g̃(q)1(ξ(a), η(a))

fa(ξ(a)) | ∂ξ = (x, −y, 0),a∈Aξ ∈ ZA, (x, −y, 0) ∈ ZS × ZT × ZV \(S∪T )}L-convex (Zn):(q ∈ ZT )X
ga(η(a)) | η = −δ(p, q, r),g̃(q) = inf {g(p) +η,p,ra∈Aη ∈ ZA, (p, q, r) ∈ ZS × ZT × ZV \(S∪T )}17

Transformation by Graphs/Networks
submodular(set fn)
separable-convY (conjugate formula)matroid 7→ matroidN

integrally-conv

N

L-conv (Zn)Y (conjugate formula)

M-conv (Zn)Y

18

Representation Problem

19

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
E
Max 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)
20

Endowed Assignment Valuation
Assignment valuation (AV):fw (X) = max w-weight of a matching covering X
Endowed assignment valuation (EAV):

fw,T (X) = fw (X ∪ T ) − fw (T )AV ⊆ EAV ⊆ GS
Thm:

EAV 6= GS(Hatfield-Milgrom 05)(Ostrovsky-Paes Leme 15)

Proof ideas• transveral matroids are base orderable (strong exch)• cycle matroid M(K4) is not base orderable• rank of M(K4) ∈ GS \ EAV
21

Matroid-based Valuation (MBV)
MBV =(Ostrovsky-Paes Leme 15)(0) Start with a weighted matroid valuation:f (X) = max{w(Y ) | Y : indep ⊆ X}(∗) Repeat(i) convolution: f˜(X) = max (f1(Y ) + f2(X \ Y ))Y ⊆X(ii) contraction: f˜(X) = f (X ∪ T ) − f (T )EAV $ MBV j GS
Conj.:

MBV = GS

(Ostrovsky-Paes Leme 15)

22

P3.
Conjugacy

23

Conjugacy: Discrete Legendre Transformy 6 f (x)y6−f •(p)slope p-x-xf •(p) = sup {hp, xi − f (x)}x∈Zn⇒

If f : Zn → Z,then f • : Zn → Z(integer-valued)24

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

f 7→ f • = g 7→ g • = ffunction Zn → Z
convex-extensible

M\L\(3) biconjugacy
f •• = ffor f ∈ M\ ∪ L\25

Conjugacy and Biconjugacy
f : Zn → Z
submodular(set fn)
separable-convex
Pf (x) =ϕi(xi)integrally-convex

f • : Zn → Zf •• = fsubmodular polyhedronY{x ∈ Zn | x(A) ≤ ρ(A)}separable-convex
Yϕ•1 (p1) + · · · + ϕ•n(pn)NN

L-convex (Zn)
L\-convex
M-convex (Zn)M\-convex

M-convex
M\-convex
L-convex
L\-convex

YYYY

26

Conjugacy in Polymatroids
Polyhedron S

Submodular fn ρ

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

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

Self-Conjugacy:

ρ(X) = |X| − ρ•(χX )Prf: ρ•(χX ) = max{|X ∩ Y | − ρ(Y )}Y= max {|X ∩ Y | − ρ(Y )} = |X| − ρ(X)Y ⊇X

ρ:subm ⇒ ρ:L\-conv ⇒ ρ•:M\-conv ⇒ ρ:M\-concave28History of Discrete Conjugacy
Matroid bases←→ Matroid rank fn

Whitney 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

Significance of Conjugacy• Economics (auction)
x: commodity bundle, p: price vector• Network flow (min-cost flow)
x: flow, p: tension (potential)• Electrical networkx: current, p: voltage (potential)(Iri’s book 69)• Discrete DC programming (Maehara-Murota 15)
Toland–Singer duality

30Implication in Economics
U (x) : Zn → Z ∪ {−∞}: utility
V (p) = max{U (x) − hp, xi}: indirect utilityx
Theorem:(Murota-Shioura-Yang 16)
Utility U (x) is gross-substitute (M\-concave)⇐⇒ Indirect utility V (p) is L\-convex

Application to Auction:
Ascending auction⇒ Lyapunov fn min. algorithm(Ausubel 06)⇒ L\-convex fn min. algorithm=⇒ Part III⇒ Precise analysis(M.-Shioura-Yang 16)
31

Conjugacy/Duality in Matroids
Conjugacy
Exchange axiom ⇔ Submodularity of rank function

Duality
Matroid intersection theorem (Edmonds)
Discrete separation (Frank)
Fenchel-type duality (Fujishige)

32

P4.
Duality33

Convex & Concave = Linearf , −f : convex =⇒ f (x) = hp, xi + α
submodular (set)(Zn)
separable-conv

YNY

integrally-conv

N(every set fn is int-conv)

L-conv (Zn)

YM-conv (Zn)

Y34

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

35

Difficulty of Discrete Separation (1)f (x, y) = max(0, x + y) convex
h(x, y) = min(x, y)concavenonintegral
separationp∗ = (1/2, 1/2), α∗ = 0 unique separating plane36

Difficulty of Discrete Separation (2)Even real-separation is nontrivial
f (x, y) = |x + y − 1|convex2-101h(x, y) = 1 − |x − y|-212concave

04-1
2-2
0-2

• f (x, y) ≥ h(x, y) (∀(x, y) ∈ Z2) true
• No α∗ ∈ R, p∗ ∈ R2:f (x) ≥ α∗ + hp∗, xi ≥ h(x)∵ f = 0 < h = 1 at (x, y) = (1/2, 1/2)
37

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 )ρ(X)• ρ, µ: integer-valued ⇒ x∗ ∈ ZVx∗µ(X)38Discrete Separation Theorems(Murota 96/98)

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

L-separation Thm (for L\-convex)⇒ Discrete separ. for submod. set fn (Frank 82)(submod. set fn = L\-convex fn on 0–1 vectors)

39

Separation and Min-Max Theorems
submodular(set fn)
separable-conv

separation min-max
YY(Frank)(Edmonds, Fujishige)YY

integrally-conv

N

N

L-conv (Zn)YY

M-conv (Zn)

Y

Y

40

Min-Max Duality
f : M\-convex,

h: M\-concave（Zn → Z）

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)

infn{f (x) − h(x)} = sup {h◦(p) − f •(p)}x∈Z

self-conjugatep∈Zn（f •: L\-convex, h◦: L\-concave)=⇒ Edmonds’ intersection thm
Fujishige’s Fenchel duality thm
41Edmonds’ Intersection Theorem
Submodular polyhedron(ρ(∅) = 0, ρ(V ) < +∞)P(ρ) = {x ∈ Rn | x(X) ≤ ρ(X) (∀X ⊆ V )}Theorem:(|V | = n)
(Edmonds 70)(1) For ρ1, ρ2 : 2V → R: submodular,max{x(V ) | x ∈ P(ρ1)∩P(ρ2)} = min{ρ1(X)+ρ2(V \X)}.
x

X(2) If ρ1 and ρ2 are integer-valued, thenP(ρ1) ∩ P(ρ2) = P(ρ1) ∩ P(ρ2) ∩ Zn
and there exists x∗ ∈ Zn that attains the maximum.
42

Relation among Duality Thms
Discrete Convex

Combinatorial Opt.

M-separationf (x) ≥ Lin ≥ h(x)mFenchel duality
inf {f − h}= sup{h◦ − f •}Fenchel duality (Fujishige 84)
matroid intersect. (Edmonds 70)m ⇒ discrete separ. for submod(Frank 82)⇒ valuated matroid intersect.
(M. 96)

mL-separationf •(p) ≥ Lin ≥ h◦(p)⇓weighted matroid intersect.
(Edmonds 79, Iri-Tomizawa 76,Frank 81)
43

DCA View on Matroid Union Formula
ρ(X) = max{|I| | I : independent, I ⊆ X}
is L\-convex and M\-concave
Self-Conjugacy:

ρ(X) = |X| − ρ•(χX )Edmonds’ matroid union formula:max{ρ1(X) + ρ2(V \ X)} = min{ρ1(Y ) + ρ2(Y ) + |V \ Y |}X

submod maximization(M\-concave + M\-concave)Ysubmod minimization(L\-convex + L\-convex)

44

Summarysubmod(set fn)
separ-conv
integ
-conv
L-conv(Zn)
M-conv(Zn)

Operations
sca sum cnvl graf
lngtion tran–
YN
Y*

Minimize
loc prox
glob mity––

Conjugacy/Duality
cnv bi- sep min
ext cnj thm max
Y
Y
Y
Y

Y

Y

Y

Y

Y

Y

Y

Y

Y

Y

Y*

N

N

N

Y

Y*

Y

N

NN

Y

Y

N

Y*

Y

Y

Y

Y

Y

Y

N

N

Y

Y

Y

Y

Y

Y

Y

Y45

Summarysubmod(set fn)
separ-conv
integ
-conv
L-conv(Zn)M-conv(Zn)

Operations
sca sum cnvl graf
lngtion tran–YN
Y*Minimizeloc proxglob mity––Conjugacy/Duality
cnv bi- sep min
ext cnj thm max
YYYYYYYYYYYYYYY*NNNYY*YNNNYYNY*YYYYYYNNYYY

Y

YYYY

46

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-convex functions• L\-convex functions• M\-convex functions
47

E N D48