Discrete Convexity and Optimization, RIMS, October 16, 2012

M-convex Functions
on Jump Systems— A Survey —Kazuo Murota (U. Tokyo)

121016rimsJUMP
1

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, matrices2

Discrete Convex Functions
f (x)g(p)x2p2p1x1

L♮-convex fnM♮-convex fn

3

General Understanding
Poly. Solvable ≈ Discrete Convex
Linear/Convex Functions on • • • • •• Matroids / Polymatroids / Base Polyhedra
spanning tree, bipartite matching,min-cost ﬂow• Jump Systems
nonbipartite matching, factor
4

Contents
J0. Brief Overview
J1. Jump System
J2. M-convex Function
J3. Polynomial with Half-Plane Property
J4. Sum and Convolution
J5. Duality
J6. Minimization Algorithm

5J1.
Jump System6

Tree: Exchange Property
eeGiven pairof trees

e′T′T..........................................

eee′
T − e + e′e′T ′ + e − e′New pairof trees

Exchange property: For any T, T ′ ∈ T , e ∈ T \ T ′there exists e′ ∈ T ′ \ T s.t. T − e + e′ ∈ T , T ′ + e − e′ ∈ T
7Jump Systems
Bouchet–Cunningham (95) SIAM
“jump system”
Sebő (95)
observations on gap, sum, etc.
Geelen (96) WEB
observations on exchange, etc.
Lovász (97) JCTB
membership problem
Cunningham (02) MPsolvability=jumpKabadi–Sridhar (05) JAMDC
relation to ∆-matroid
Szabó (08) SIAM
conjecture of Recski

8Jump System
Bouchet-Cunningham (95)⇐⇒ (2-step axiom)

J : jump system∀x, y ∈ J , ∀ (x, y)-incrs ,either x + s ∈ Jor else ∃ (x + s, y)-incr t s.t.
t

6xx+s+t∈Jt
y-ys

6-x s
9

Constant-Parity Jump System
J : const-parity jump system(Geelen)⇐⇒ ∀x, y ∈ J , ∀ (x, y)-incr s, ∃ (x + s, y)-incr t
x + s + t, y − s − t ∈ Js.t.
t

6tysx
simultaneous exchange

6y-sx
2-step axiom10Degree System
010300G = (V, E)

1 H = (V, F )032

Degree sequence:

degH ∈ ZV

degH (v) = # edges incident to v

J = {degH | H ⊆ G}: const-parity jump system

11Subclasses of Jump Systems−→(projection)≡

const-sum jump

[Fujishige]base polyhedron≃

generalized polymatroid[Geelen]const-parity jump≃

simul. exchange jump[Wenzel, Duchamp]

even ∆-matroid≃simul. exch. ∆-matroidJ : simul. exchange jump system∀x, y ∈ J , ∀ (x, y)-incr s ,⇐⇒ (SE axiom)

either x + s, y − s ∈ Jor else ∃ (x + s, y)-incr t s.t. x + s + t, y − s − t ∈ J12

J2.
M-convex Function(M = Matroid)13M-convex Function on Base Polyhedraf : Zn → R ∪ {+∞}

j6
yei: i-th unit vector

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 )domf ⊆ const-sum hyperplane♮
Mn+1 ≃ Mn⊅=6MMnM♮-14Matching / Assignment
U
u1
u2
u3
u4

V
v1
v2
v3

X = {u1, u2}
u1
v1
u2v2

X = {u1, u2}
u1v1
u2
v3

M1

M2

EMax weight for X ⊆ Uf (X) = max{∑e∈M(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
15

Convex Functions on Jump Systems
Ando–Fujishige–Naitoh (95) JORSJ

separable convex

Murota (06) SIAM
“M-convex function”
Murota–Tanaka (06) IEICEdescent alg for M-convex
Shioura–Tanaka (07) SIAM
polynom alg for M-convex
Kobayashi–Murota–Tanaka (07) SIAM operations on M-convex
Kobayashi–Murota (07) DAM
transform. by linking
Kobayashi–Takazawa (09) JCTB
weighted even factor
Kobayashi (10) DO
C3-free 2-matching
Kobayashi–Szabo–Takazawa (12) JCTB
Ck -free 2-matching
Berczi–Kobayashi (12) JCTB(n − 3) connectivity augment.
Brändén (10) SIAM

polynomial w/ half-plane property

16M-convex Function on Jump Systems
f :J →R

J : const-parity jump system,(M-EXC) ∀ x, y ∈ J and (x, y)-incr s,∃ (x + s, y)-incr t s.t. x + s + t, y − s − t ∈ J ,f (x) + f (y) ≥ f (x + s + t) + f (y − s − t)t

6xy-

• local opt

global opt• transformation by graphs• NO integral duality=⇒s• Valuated delta matroid (Dress–Wenzel 91)• Minsquare factor (Apollonio–Sebő 04)• Even factor (Kobayashi–Takazawa 09)

17

Minsquare Factor Problem
Apollonio and Sebő 04010

300

G = (V, E)

1 H = (V, F )302Degree sequence:degH ∈ ZV

• given: number of edges k∑
Minimize f (x) =(x(v))2v∈Vs.t. x = degH∑
H has k edges⇔x(v) = 2kv∈VProblem:()

M-convex minimization under const-sum constraint
18

Edge-Weighted Factor Problem
edge cost w : E → R,01x: degree sequence
0300

G = (V, E)

1 H = (V, F )302

Problem:(cost on edges)

Minimizes.t.

x = degH ,w(F )∑+v∈Vφv (x(v))

H has k edges

f (x) = min{w(F ) | degH = x} +H(cost on vertices)∑v∈Vφv (x(v))

is M-convex19

Skew-Symmetric Polynomial Matrix
X
A= X

aji = −aij

{X | det A[X, X] ̸= 0}:even delta-matroid (const-parity jump)
Bouchet 87, Chandrasekaran-Kabadi 88, Dress-Havel 86

f (X) = deg det A[X, X]:
valuated delta-matroid (M-concave fn)
Dress–Wenzel 91
20

Even Factor

Cunningham–Geelen 01

vertex-disjointF
paths
even-length cycles
#: Find F with max number of arcs |F |w: Find F with max arc-weight w(F )• NP-hard in general• Polynomially solvable if odd-cycle symmetric#:Cunningham-Geelen 01, Pap 04/07, Harvey 06
w:Cunningham-Geelen 01, Takazawa 05/08, Király–Makai 04
21

Odd-Cycle Symmetry vs Convexity
Odd-cycle symmetric (OCS) ⇐⇒#: ∀ odd cycle C , ∃ reverse cycle C
w: ∀ odd cycle C , w(C) = w(C)d(F ) = outdeg(F ) ⊕ indeg(F )J (G) = {d(F ) | F : even factor}
f (x) = max{w(F ) | d(F ) = x, F : even factor}
Thm#: G is OCS(Kobayashi–Takazawa 09)⇐⇒ J (G) is jump system

w: (G, w) is OCS ⇐⇒ f (x) is M-concave on J (G)solvable case (OCS) ⇐⇒ discrete convex
22

J3.
Polynomial with
Half-Plane Property

23

Polynomial with Half-Plane PropertyαP (z1, . . . , zn) =cαz : polynomialα∑supp(P ) = {α | cα ̸= 0}⊆ Zn

H : open half-plane of C

6H-(0 ∈ H )P : HPP-polynomial ⇔ ∃H s.t. P (z) ̸= 0 (∀z ∈ H)
Thm(Choe-Oxley-Sokal-Wagner 04)

P : homog. multiaﬃne HPP =⇒ supp(P ): matroid baseThm (general)(Brändén 07)

P : HPP =⇒ supp(P ): jump system (possibly non-even)24M-convexity from HPP-Polynomial
P (z1, . . . , zn) =∑cα(t)z α: polynomial

αcα(t): Puiseux (fractional power) series in tν(cα(t)): leading exponent cα(t) = b t−ν + · · ·α 7→ ν(cα(t))=⇒ trop(P ) : supp(P ) → R

Thm(Brändén 10)

Assume: supp(P ) is a const-parity jump system

P : HPP =⇒ trop(P ): M-concave function
supp(P ) = {α | cα(t) ̸= 0}
P : HPP-polynomial ⇔ ∃H s.t. P (z) ̸= 0 (∀z ∈ H)

25

Examples of HPP-Polynomials(1) P (z1, z2) = 1 + tw z1z2

H = right half-planez2 6Brändén 10w
0-z1w(ij): weight of edge ij(2) degree sequence;P (z1, . . . , zn) = Πij∈E 1 + tw(ij)zizj ⇒ tropP (α) = max weight of H with degH = α→ alternative proof to M-concavity(3) positive-semideﬁnite matrices A1(t), . . . , An(t)P (z1, . . . , zn) = det (z1A1(t) + · · · + znAn(t))→ connection to “hive” (n=3)

26

J4.
Sum and Convolution27Sum/Convolution Operations
Minkowski Sum(discrete system)
J1 + J2 = { x1 + x2 | x1 ∈ J1, x2 ∈ J2 }matroidbase polyhedron∆-matroid
jump system

Rado (42) , Edmonds (68)
McDiarmid (75)
Bouchet (89)
Bouchet–Cunningham (95)

Convolution(discrete function)(f12f2)(x) = inf {f1(x1) + f2(x2) | x1 + x2 = x}valuated matroid
Murota (96)
M-convex (base)
Murota (96)valuated ∆-matroid↓M-convex (jump)
Kobayashi-Murota-Tanaka (07)28

Transformation by Graph/Network→x →→→→→ y→min{f (x) | x ←→ y} := g(y)Thm:(Kobayashi-Murota-Tanaka 07)

f : M-convex =⇒ g : M-convex
Proof byelementary construction:→x →→→→→ y→

29

J5.
Duality30

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

31

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
32

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

No Separation Theorem for Jump-M
Even real-separation does not hold
J = {(x, y) | x, y : even }const-parity jumpf (x, y) = |x + y − 2|

M-convexh(x, y) = 2 − |x − y|M-concave
2-2-101120• f (x, y) ≥ h(x, y) (∀(x, y) ∈ J ) true
• No α∗ ∈ R, p∗ ∈ R2 satisﬁes

4-1
2-20-2f (x) ≥ α∗ + ⟨p∗, x⟩ ≥ h(x)34

No Integral Separation for Jump-M
J = {(x, y) | x ≡ y mod 2}: const-parity jumpf (x, y) = max(0, x + y) M-convex
h(x, y) = min(x, y)M-concave

separable, but
nonintegralp∗ = (1/2, 1/2), α∗ = 0 unique separating plane35

J6.
M-convex Minimization

36

Min Spanning Tree Probleme′Telength d : E → R
total length of T˜ )=d(TThm∑e∈Td(e)˜ ) ≤ d(T˜ − e + e′ )T : MST ⇐⇒ d(T⇐⇒ d(e) ≤ d(e′)
if T − e + e′ is tree

Algorithm

Kruskal’s,

Kalaba’s

DCA view• linear optimization on an M-convex set• M-optimality: f (x∗) ≤ f (x∗ − ei + ej )37

Local vs Global Opt (M-base)Thm: f : Zn → R

M-convex(Murota 96)x∗: global min⇐⇒ local min f (x∗) ≤ f (x∗ − ei + ej )x∗(∀i ̸= j )Ex: x∗ + (0, 1, 0, 0, −1, 0, 0, 0)
Can check with n2 fn evalsx∗

For M♮-convex fn ⇒38

Local vs Global Opt (M-jump)
Thm:f :J →R(Murota 06)

M-convex on const-parity jumpx∗: global min⇐⇒ local minx∗f (x∗) ≤ f (x∗ ± ei ± ej )(∀i, j )Ex: x∗ +(0, ±1, 0, 0, ±1, 0, 0, 0)
Can check with n2 fn evals

39

Minimizer Cut Theoremsx∗⇒ Domain reduction algorithm⇒ Descent algorithm

j6I-Thm (M-base) x ̸∈ argmin fix(Shioura 98)

For (i, j) that minimizes f (x − ei + ej ),∃ minimizer x∗ withx∗i ≤ xi − 1, x∗j ≥ xj + 1

Thm (M-jump) x ̸∈ argmin f(Murota-Tanaka 06)

For (i, j; σi, σj ) that minimizes f (x ± ei ± ej ),± ±∃ minimizer x∗ withσi(x∗i − xi) ≥ 1, σj (x∗j − xj ) ≥ 1
40

Sum-Constrained Minimization
s.t. x ∈ Jk

Problem [k]: Min. f (x)J : const-parity jump,

Jk = {x ∈ J | Σ xi = k}

Thm:(Murota 06)• global min ⇐⇒ local min wrt ∥ ∥1 ≤ 4• convex optimal values:fopt(k − 1) + fopt(k + 1) ≥ 2 fopt(k)• nested minimizers:∀xopt(k), ∃xopt(k − 1), ∃xopt(k + 1):xopt(k − 1) ≤ xopt(k) ≤ xopt(k + 1)
41

Proof: Local ∥ ∥1 ≤ 4 ⇒ Global opt
Problem [k]: Min. f (x)s.t. x ∈ J,

• You do not have to read this slide •∑xi = kBy way of contradiction, assumef (x) > f (y) for y ∈ Jk with ||y − x||1 → min
If you are still reading, you are already in contradiction :-)Claim: ∀i ∈ supp+(y − x), ∀j ∈ supp−(y − x):f (x) + f (y) < 2f (x) ≤ f (x + ei − ej ) + f (y − ei + ej )(M-EXC) for (x, y) & Claim,∃ i1 ∈ supp+(y − x), i2 ∈ supp+(y − x − ei1 ),j1 ∈ supp−(y − x), j2 ∈ supp−(y − x − ej1 ):f (x) + f (y) ≥ f (x + ei1 + ei2 ) + f (y − ei1 − ei2 )f (x) + f (y) ≥ f (x − ej1 − ej2 ) + f (y + ej1 + ej2 )

(1)
(2)

(continued)
42

(M-EXC) for (x + ei1 + ei2 , x − ej1 − ej2 ) & local opt,

f (x + ei1 + ei2 ) + f (x − ej1 − ej2 )≥ min[f (x + ei1 − ej1 ) + f (x + ei2 − ej2 ),f (x + ei1 − ej2 ) + f (x + ei2 − ej1 ),f (x) + f (x + ei1 + ei2 − ej1 − ej2 )]≥ 2f (x)(3)(M-EXC) for (y − ei1 − ei2 , y + ej1 + ej2 ),f (y − ei1 − ei2 ) + f (y + ej1 + ej2 )≥ min[f (y − ei1 + ej1 ) + f (y − ei2 + ej2 ),f (y − ei1 + ej2 ) + f (y − ei2 + ej1 ),f (y) + f (y − ei1 − ei2 + ej1 + ej2 )]≥ f (x) + f (y)(1)+(2)+(3)+(4) = contradiction(4)
Q.E.D.
43

Optimality Criteria
Problem [∗]: Min. f (x) s.t. x ∈ J
Problem [k]: Min. f (x) s.t. x ∈ J,
Problem [∗]Local: || · ||1 ≤ 2∑

xi = kProblem [k]Local: || · ||1 ≤ 4

jump:
Murota (06)Murota (06)M-convex
jump:
Ando-Fujishige-Naitoh Apollonio-Sebő (04)separ. conv
(95)
degree sequencevaluated
Dress-Wenzel (91)
Murota (96)∆-matroid
valuated
Dress-Wenzel (90)——matroid——polymatroid:
Murota (96)
Murota-Shioura (99)M/M♮-conv
Murota-Shioura (99)44BooksMurota: Matrices and Matroids for Systems Analysis,
Springer, 2000/2010 (Chap.5)
valuated matroid intersection algorithm
Murota: Discrete Convex Analysis, SIAM, 2003
Fujishige: Submodular Functions and Optimization,
2nd ed., Elsevier, 2005 (Chap. VII)45

E N D46