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

Discrete Convex Analysis II:
Properties of Discrete Convex Functions

Kazuo Murota(Tokyo Metropolitan University)

180726rimsCOSS2
1

Contents of Part II
Properties of Discrete Convex Functions

P1. Convex Extension
P2. Optimality Criterion(local = global)

P3. Operations
P4. Conjugacy(Legendre transform)

P5. Duality(separation, Fenchel)2

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 graphs3

P1.
Convex Extension

4

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) Integrally-convex fns are convex-extensible (by def)
(3) L♮-convex fns are convex-extensible(Murota 98)(4) M♮-convex fns are convex-extensible(Murota 96)

5\-convexFunctions
Bivariate L
BivariateL♮\-- andand MM♮-convexFunctionsBivariate L\- and M\-convex Functions
f (x)

f (x)
g(p)

g(p)
x2
p2

x2

p2

p1

x1

p1

L\-convex fn
L♮-convexL\-convex
fn fnx\M -convex fn
1M\♮-convex-convex fn
Mfn
6Triangulation for Discrete Convex Functions(n = 2 )66-

L♮-convex

6-M♮-convex-Integrally convex

7

Bivariate Integrally-convex Functions
6

60000-002
M
L
M
M

12104M
M
M
L

2
2004
L
M
L
M

32106 = g(4, 4)M
MLM

4 = g(4, 3)
220-g(x1, x2) = #(M) − #(L) in [0, (x1, x2)]
f (x1, x2) = A(x12 + x22) + g(x1, x2)

8

Convex Extension — Computationf : Zn → R is convex-extensible⇔ ∃ convex f : Rn → R: f (x) = f (x) (∀x ∈ Zn)
Theorem:(1) Separable-convex
easy to compute (consecutive points)(2) Integrally-convex
diﬃcult (exp-time) to compute(3) L♮-convex(Favati–Tardella 90, Murota 98)

easy to compute (Lovász ext.)(4) M♮-convex(Shioura 09,15)

poly-time to compute (via conjugacy)
9Classes of Discrete Convex Functions
f : Zn → R
convex-extensible
integrally convex
M♮-convex
separable
convexL♮-convex

M♮ ∩ L♮ = separable
10

P2.
Optimality Criterion(local opt = global opt)

11

Local vs Global Optimality (n = 1)
f :Z→Rx∗: global opt (min)⇐⇒ x∗: local opt (min)f (x∗) ≤ min{f (x∗ − 1), f (x∗ + 1)}x∗

12

Neighborhood for Local Optimality
separable
convexintegrally
convexL♮convexM♮convex

2n + 1

3n2n+1 − 1n(n + 1) + 1{±χX }{ei − ej }{±e1, . . . , ±en}

{χX − χY }13

Local min = Global minx∗

submodular(set fn)
separable-conv= #neigh poly-time algorithm?
-bors local opt global opt
Y2n
Y

2nintegrally-conv

Y3nL♮-conv (Zn)Y2nM♮-conv (Zn)Yn214

Local min = Global minx∗

submodular(set fn)
separable-conv= #neigh poly-time algorithm?
-bors local opt global opt
Y2nY
Y2n

Y

integrally-conv

Y3nN

L♮-conv (Zn)

Y2nY

M♮-conv (Zn)

Yn2Y

15

P3.
Operations

16

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

• linear addition: f (x) + ⟨p, x⟩• section: f (x, 0)• projection (partial minimization): min f (x, y)y• sum: f1(x) + f2(x)• convolution: (f12f2)(x) = min(f1(y) + f2(x − y))y• transformation by graphs/networks
17

Scaling/Linear Additionaf (x)f (sx)f (−x) f (x)+(a > 0) (s ∈ Z+)⟨p, x⟩
submodularY—
Y*Y(set fn)
V \Xseparable-conv
YYYY±xi
integrally-conv
YNYY±xi
L-conv (Zn)
YYYYM-conv (Zn)

YNY

Y

18

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

sectionprojectionf (x, 0)miny f (x, y)YY
restriction contraction*
YYY

YNY
YYYYN
Y

contraction: ρA(X) = ρ(X ∪ A) − ρ(A)19Sum and Convolution• (f1 + f2)(x) = f1(x) + f2(x)Theorem:f1, f2 : L
L♮(Murota 98)=⇒ f1 + f2: L=⇒L♮
f1, f2, . . . , fk : L / L♮ =⇒ f1 + f2 + · · · + fk : L / L♮

• (f12f2)(x) = min(f1(y) + f2(x − y))yTheorem:f1, f2 : M
M♮(Murota 96)=⇒ f12f2: M=⇒
M♮
f1, f2, . . . , fk : M / M♮ =⇒ f12f22 · · · 2fk : M / M♮
Rem:M + M is not M,L 2 L is not L
20

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)21Sum/Convolution
submodular(set fn)
separable-conv

sum 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
YNYN
N → L2-convex

N → M2-conv Y
matr.intersec matroid union

22

P4.
Conjugacy(Legendre transform)

23

Conjugacy: Discrete Legendre Transformy 6 f (x)y6−f •(p)slope p-x-x•
f (p) = sup {⟨p, x⟩ − 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 [⟨p, x⟩ − 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-extensibleM♮L♮(3) biconjugacy
f •• = ffor f ∈ M♮ ∪ L♮
25

Significance of M-L Conjugacy• Economics (game, auction)
x: commodity bundle, p: price vector• Network flow (min-cost flow)
x: flow, p: tension (potential)• Electrical networkx: current, p: voltage (potential)• Discrete DC programming(Iri’s book 69)(Maehara-Murota 15)• Convexity view on matroids26

Conjugacy in Linear Algebra[a1, · · · , a5] =1000
100011
100
11

Bases B = { {1, 2, 3}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5},{1, 4, 5}, {2, 3, 4}, {2, 4, 5}, {3, 4, 5} }Rank fn ρ(X) = rank {aj | j ∈ X}
Equivalence B ⇐⇒ ρ
ρ(X) = max{|X ∩ J | | J ∈ B}

(X ⊆ V )B = {J ⊆ V | ρ(J ) = |J | = ρ(V )}27

Axioms of Matroid

IJBasis axiom (set family B):

ij∀ I, J ∈ B, i ∈ I \ J , ∃ j ∈ J \ I :I − i + j ∈ B, J + i − j ∈ B

Rank axiom (set function ρ):X(R1) 0 ≤ ρ(X) ≤ |X|(R2) X ⊆ YY=⇒ ρ(X) ≤ ρ(Y )(R3) ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )Equivalence B ⇔ ρ(M ↔ L)

ρ(X) = max{|X ∩ J | | J ∈ B}

(X ⊆ V )B = {J ⊆ V | ρ(J ) = |J | = ρ(V )}28

Conjugacy in Matroid
Bases B = { {1, 2, 3}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5},{1, 4, 5}, {2, 3, 4}, {2, 4, 5}, {3, 4, 5} }Rank fn ρ(X) = rank {aj | j ∈ X}
Equivalence B ⇐⇒ ρ
ρ(X) = max{|X ∩ J | | J ∈ B}

(X ⊆ V )B = {J ⊆ V | ρ(J ) = |J | = ρ(V )}Bases(M♮-convex)⇐ conjugate ⇒Rank fn(L♮-convex)

29

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

Edmonds’ matroid union formula:max{ρ1(X) + ρ2(V \ X)} = min{ρ1(Y ) + ρ2(Y ) + |V \ Y |}XY
submod maximization

submod minimization(M♮-concave 2 M♮-concave)(L♮-convex + L♮-convex)

Self-Conjugacy:

ρ(X) = |X| − ρ•(χX )30

Conjugacy in Polymatroids
Polyhedron S

Submodular fn ρ

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

31

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 ⟨p, x⟩ = max[⟨p, x⟩ − f (x)] = f •(p)xx∈S←: f (x) = max[⟨p, x⟩ − g(p)] = g •(x)p

Legendre transform
M♮-convex
L♮-convex32

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⇕
M♮-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 98⇕←→ L♮-convex fn
Fujishige–Murota 00

33

Integral Subgradient & Biconjugacy
Subdiﬀerential: ∂f (x)= {p ∈ Rn | f (y) − f (x) ≥ ⟨p, y − x⟩ (∀y)}↑ subgradientIntegral subdiﬀerential: ∂Zf (x) = ∂f (x) ∩ Zn
= {p ∈ Zn | f (y) − f (x) ≥ ⟨p, y − x⟩ (∀y)}↑ integral subgradient

Prop: f : Zn → Z ∪ {+∞}

(Murota 98)

If ∂Zf (x) ̸= ∅ for all x ∈ dom f , then f •• = ff •(p) = sup [⟨p, x⟩ − f (x)]x∈Zn34

Integ. Subgradient & Biconjugacy: Example
f : Zn → Z(Discrete life is not easy)∂Zf (x) ̸= ∅ ?
f •• = f ?

Example: D = {(0, 0, 0), ±(1, 1, 0), ±(0, 1, 1), ±(1, 0, 1)}{(x1 + x2 + x3)/2, x ∈ D,f (x1, x2, x3) =+∞,o.w.

D is “convex”: conv(D) ∩ Zn = D∂fR(0) = {(1/2, 1/2, 1/2)}∂Zf (0) = ∅f ••(0) = − inf max{0, |p1+p2−1|, |p2+p3−1|, |p3+p1−1|}p∈Z3f ••(0) = −1 ̸= 0 = f (0)35Integral Subgradient & Biconjugacy
Thm:(Murota 98)
f : integer-valued L♮- / M♮- / L♮2- / M♮2-convex- Subdiﬀerential ∂f (x) is an integral polyhedron- Hence integral subgradient p exists- Hence f •• = f

Thm:(Murota -Tamura 18)
f : integer-valued integrally convex- Subdiﬀerential ∂f (x) is NOT an integral polyhedron- But
integral subgradient p exists- Hence f •• = f
36

Conjugacy and Biconjugacy
Legendre trans:f •(p) = sup [⟨p, x⟩ − f (x)]x∈Znf : Zn → Z
submodular(set fn)
separable-convex∑f (x) =φi(xi)integrally-convex
L-convex (Zn)L♮-convex
M-convex (Zn)M♮-convex

f • : Zn → Zf •• = f
submodular polyhedronY{x ∈ Zn | x(A) ≤ ρ(A)}separable-convex
Yφ•1 (p1) + · · · + φ•n(pn)Not integrally-convex
Y(characterization: open)
M-convex
YM♮-convex
YL-convexYL♮-convex
Y

37

P5.
Duality(separation theorem)(Fenchel duality)38

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

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

39Matroid Intersection Problem
Given two matroids . . . . . .
• Find a common indep. set X with max |X|• Find a common base B (if any)

Given two matroids and weight w . . . . . .
• Find a common indep. set X with max w(X)• Find a common base B with max w(B)LP formulation with integrality, combinatorial duality,
eﬃcient algorithms, many applications
40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)}xX(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
41

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)42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) ≥ α∗ + ⟨p∗, x⟩ ≥ h(x)(x ∈ Zn)• f , h: integer-valued ⇒ α∗ ∈ Z,p∗ ∈ Zn

43

Diﬃculty 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 plane44

Diﬃculty of Discrete Separation (2)Even real-separation is nontrivial
f (x, y) = |x + y − 1|convexh(x, y) = 1 − |x − y|concave• f (x, y) ≥ h(x, y) (∀(x, y) ∈ Z2) true
• No α∗ ∈ R, p∗ ∈ R2:f (x) ≥ α∗ + ⟨p∗, x⟩ ≥ h(x)∵ f = 0 < h = 1 at (x, y) = (1/2, 1/2)
45

Diﬃculty of Discrete Separation (3)Set function ⇐⇒ Function on {0, 1}nEvery set function {0, 1}n → R can beextended to convex/concave function
610

f : convex
01-

6

h : concave1001-• f (x, y) = h(x, y) (∀(x, y) ∈ {0, 1}2)
• No separation possible46

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)

47

Min-Max Duality
f : M♮-convex,

h: M♮-concave（Zn → Z）

Legendre–Fenchel transformf •(p) = sup{⟨p, x⟩ − f (x) | x ∈ Zn}h◦(p) = inf {⟨p, x⟩ − 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
48

Relation among Duality Thms
Discrete Convex

Combinatorial Opt.

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

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

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

50

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

Operations
sca sum cnvl graflngtion tran–YNY*Minimize
loc prox
glob mity
Y–Conjugacy/Duality
cnv bi- sep min
ext cnj thm max
YYYYYYYYYY

YYYY

N

N

NN

Y

Y*Y

YNN

Y

YN

Y*Y

YYYYYNN

Y

Y

Y

YY

Y

Y

Y

NN

Y

Y

Y?

NN

N

N?

Y––Y

Y*Y*?

?

?

51

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

Operations
sca sum cnvl graf
lngtion tran–YN
Y*Minimize
loc prox
glob mityY–Conjugacy/Duality
cnv bi- sep min
ext cnj thm max
YYY
YYYY

YYYYYYY

NNNN

Y

Y*Y

YNNYYNY*YYYYYYNNYYYYYYY

Y

NN

Y

Y

Y?

NN

NN?

Y

––Y

Y*Y*?

?

?

52

Summarysubmod(set fn)
separ-conv
integ
-conv
L-conv(Zn)M-conv(Zn)
M-conv(jump)
L-conv(treen)Operations
sca sum cnvl graflngtion tran–Y
N
Y*Minimize
loc prox
glob mity
Y–Conjugacy/Dualitycnv bi- sep min
ext cnj thm max
YYY
YYYY

YYYYYYYNNNNYY*YYNNYYNY*YYYYYYNNYYYYYYYY

NNY

YY?

NN

NN?

Y––Y

Y*Y*?

?

?

53

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• separable-convex functions• L♮-convex functions• M♮-convex functions
54

E N D55