Hungarian-Japanese Symposium (HJ 2019), Tokyo, May 2019

Discrete Convex Analysis View on
Discrete Decreasing Minimization
Kazuo Murota(Tokyo Metropolitan University)

withAndrás Frank(Eötvös University)
190528decminHJ
1

Lexico-Optimization on Discrete Sets
Discrete Sets:- M-convex set (integer pts in integ. base polyhedron)- Intersection of two M-convex sets
- Network flow
- Submodular flow

Applications:[balancing, fairness, egalitarian]- Graph orientation- Resource allocation (in OR, computer science)- Economics and game theory
2

Contents
1. Dec-Minimization

via Convex Optimization

2. Optimality Condition

via M-optimality Criterion

3. Min-max Formulas

via Fenchel-type Duality

4. Structure of Dec-min

via M-convex Intersection

5. Discrete vs Continuous3Dec-Min: Discrete (Z) vs Continuous (R)(Z) M-convex set
62(1, 2)

62(2, 1)10Base-polyhedron (R)

1-

1

2

dec-min3(1.5, 1.5)

0-

1

2

3

dec-min= min-norm(Fujishige, 1980)

4

1.
Dec-Minimization
via Convex Optimization5

Decreasing-Minimality: Definitionx = (2, 5, 5, 1, 4)x↓ = (5, 5, 4, 2, 1)

y = (1, 5, 5, 5, 1)y↓ = (5, 5, 5, 1, 1)

Def: x is decreasingly smaller than y(x <dec y )⇐⇒ x↓ is lexicographically smaller than y↓
Def: (Q: set of vectors)x ∈ Q is decreasingly minimal (dec-min) in Q⇐⇒ x ≤dec y for all y ∈ Q
Def: inc-max by x↑ = (1, 2, 4, 5, 5)• inc-max = lexico-optimal (Megiddo, Fujishige)• dec-min = co-lexico-optimal (Fujishige)
6Concept of Majorization
Def: x is majorized by yk∑x↓(i) ≤k∑(x ≺ y )y↓(i) (∀k),

i=1
i=1(sum of k-largest components)

n
∑
i=1

“more uniform”x↓(i) =n∑y↓(i)i=1

Def: (Q: set of vectors)x ∈ Q is least majorized in Q ⇐⇒ x ≺ y for all y ∈ Q
Fact 1: least majorized element may NOT exist
Ex: Q = {(2, 2, 2, 0), (3, 1, 1, 1)}
dec-mininc-max(M-conv ∩ M-conv)∄ least majorized

Fact 2: least majorized ⇒ dec-min & inc-max
7Dec-Min by Convex Optimization
Def: φ : Z → R “rapidly increasing”⇐⇒ φ(k + 1) is ‘much larger’ than φ(k)φ(k + 1) ≥ N φ(k) > 0(N ≥ |S|)

Prop: Any D ⊆ ZS , m ∈ D , φ rapid increas. convex∑m is dec-min ⇐⇒ m minimizes
φ(x(s)) on D

Can use Discrete Convex Analysis
for discrete dec-minimization
Def: φ : Z → R convex ⇐⇒ φ(k − 1) + φ(k + 1) ≥ 2φ(k)82.
Optimality Condition (for Dec-Min)
via M-optimality Criterion9Separable convex functions in DCA
Min

Φ(x) =∑φs(x(s))

s.t. x ∈ B

M-convex sets∈Sφs: convex φs(k − 1) + φs(k + 1) ≥ 2φs(k)Thm:m ∈ B is a minimizer of Φ(Groenevelt, 1985,1991)(global opt)⇐⇒ φs(m(s) + 1) + φt(m(t) − 1) ≥ φs(m(s)) + φt(m(t))
if m + χs − χt ∈ B(local opt)
DCA view:• A special case of M-optimality criterion (Mu.1996)• Separ. conv on M-conv set is M-convex function
10Optimality Conditions for Dec-Min
As a consequence of Groenevelt’s theorem:

Thm: B : M-convex set, m ∈ B ,m is dec-min in B
⇔ m(s) ≥ m(t) − 1ifm + χs − χt ∈ B⇔ m minimizes every symm. separ. convex fn · · · (∗)∑⇔ m minimizes square-sumx(s)2
Fact: (∗) ⇐⇒ m is least majorized

Cor: ∃ least majorized element in M-convex set- Known to experts (Tamir, Ando) ca. 1995
11

3.
Min-max Formulas (for Dec-Min)
via Fenchel-type Duality

12Min-Max Formulas for Dec-Min• Largest compnt β1 of dec-min m:(Frank+Mu.)(p: supermod.)β1 = max{ ⌈ p(X)/|X| ⌉ : X ̸= ∅ }• r1 = |{s : m(s) = β1}| for dec-min m:r1

β1
β1 − 1r1 = max{ p(X) − (β1 − 1)|X| }X• Square-sum:(p̂ = Lovász ext.)∑∑ ⌊ π(s) ⌋ ⌈ π(s) ⌉min {x(s)2} = max { p̂(π) −}x∈B22π∈ZSs∈Ss∈S13

Min-Max Formulas (cont.)• Total a-excess for each a ∈ Z:
∑min{(x(s) − a)+ : x ∈ B} = max{ p(X) − a|X| }
Xs∈S
β1r1

β1

r1aa14

DCA Strategy for Min-Max Formulas
Fenchel-type discrete duality theorem (Mu.1998)⇓Min-max for separable convex fn on an M-convex set∑∑min {φ(x(s)) } = max { p̂(π) −ψ(π(s)) }x∈Bπ∈ZSss conjugate

φ : Z → Z ∪ {+∞}

ψ(ℓ) = max{kℓ − φ(k) : k ∈ Z}
⇓Choose φ and calculate ψ to obtain formulas like:• β1 = max{ ⌈ p(X)/|X| ⌉ }• r1 = max{ p(X) − (β1 − 1)|X| }⌊⌋⌈⌉∑∑
π(s)π(s)• min{ x(s)2} = max{ p̂(π) −}22∑• min{ (x(s) − a)+} = max{ p(X) − a|X| }15

Proof of Formula for Square-Sum∑∑
min {φ(x(s))} = max { p̂(π) −ψ(π(s)) }x∈Bsπ∈ZSs⇓
Choose φ(k) = k2 and calculate its conjugate:
ψ(ℓ) = max{kℓ − k2 : k ∈ Z}
= max{kℓ − k2 : k ∈ {⌊ℓ/2⌋ , ⌈ℓ/2⌉}}⌊ ⌋ ⌈ ⌉ℓℓ=·22min {x∈B∑s∈S⇓x(s)2} = max { p̂(π) −π∈ZS∑ ⌊ π(s) ⌋ ⌈ π(s) ⌉s∈S22}

DCA oﬀers a method of discovery (and proof)
16

Proof of Formula for r1φψ66(k ≤ β1 − 1)
 01(k = β1)
φ(k) =
 +∞ (k ≥ β + 1)
1slope= β1β1 − 11slope=1--β1 − 1 β1 k0

(ℓ ≤ −1)
 +∞0(ℓ = 0)
ψ(ℓ) =
 β ℓ − 1 (ℓ ≥ 1)
10ℓ1

Figure 1: Mutually conjugate discrete convex functions φ and ψ in (4.21) and (4.22)

r1 := |{s : m(s) = β1}| for dec-min m
φ6||min {ψ∑x∈B
β1 − a6β1
φ(x(s)) } = maxslope={ p̂(π)−π∈ZSaslope=10a-β1 k1

ψ(π(s)) }L♮-concave-0∑||ℓ← π ∈ {0, 1}S1: Mutuallyconjugate
discreteconvexfunctions
φ andin (4.22)
and(4.23) − 1)|X|}
FigureFigure
2: Mutuallyconjugate
discreteconvexfunctions
φ andψ inψ(4.21)
and(4.22)
max{p(X)−(β1φ6ψ

176

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.
(Mu. 96)⇕L-separationf •(p) ≥ Lin ≥ h◦(p)⇓weighted matroid intersect.
(Lawler 75, Iri-Tomizawa 76,Edmonds 79, Frank 81)
18

4.
Structure of Dec-minvia M-convex Intersection

19

Matroidal Structure of Dec-min Elements
dm(B): set of the dec-min elements of B
Thm:

(Frank+Mu.)

dm(B) is a matroidal M-convex set:2

ˆ:∃ matroid M̂ , ∃ integer vector ∆ˆ : L is a basis of M̂ }dm(B) = {χL + ∆106

dec-min-12

Example: B = {m1, m2, m3, m4, m5}
m1 = (2, 1, 1, 0), m2 = (2, 1, 0, 1)
m3 = (1, 2, 1, 0), m4 = (1, 2, 0, 1)
dec-min (Z)m5 = (2, 2, 0, 0)
NOT dec-min (Z)M̂ : graphic matroid⌢ ⌢ ,•⌣•⌣•ˆ = (1, 1, 0, 0)∆20

3M-convex Intersection Theorem in DCA
f , g : M♮-convex, Z-valued

Min f (x) + g(x)Thm (M-convex intersection):∃π̂ ∈ Zn(Mu. 1996)(opt certificate, subgradient)argmin (f (x) + g(x))= argmin (f (x) − ⟨π̂, x⟩) ∩ argmin (g(x) + ⟨π̂, x⟩)extension of weight-splitting
Choose f (x) =∑⇓x(s)2,g(x) = δ(x) (indicator of B )⇓∑dm(B) = arg min {x(s)2} = argmin (f (x) + g(x))
x∈B= argmin (f (x) − ⟨π̂, x⟩) ∩ argmin (g(x) + ⟨π̂, x⟩)21• For f (x) =∑⇓x(s)2argmin (f (x) − ⟨π̂, x⟩) = Box{⌊π̂(s)/2⌋ , ⌈π̂(s)/2⌉}• For g(x) = δ(x) (indicator of B )argmin (g(x) + ⟨π̂, x⟩) = {π̂ -min elements of B}(M-convex set)⇓dm(B) = (unit-sized box) ∩ (M-convex set)

= matroidal M-convex set
Q.E.D.
Note: M-convex intersection ⇐⇒ Fenchel duality
22

Canonical Partition and Near-Uniformity
canonical partition
essential values{S1, S2, . . . , Sq }β1 > β 2 > · · · > β q

Thm: m ∈ B is dec-min(Frank+Mu.)⇐⇒ • βi − 1 ≤ m(s) ≤ βi for s ∈ Si (near-uniform)• Ci := S1 ∪ · · · ∪ Si is tight, i.e., m(Ci) = p(Ci)
β161?

β261?
β361?

S1S2S323

Canonical Partition: Alternative Construction- Maximizers of p(X) − β|X| form a lattice for β ∈ ZLet L(β) be the smallest maximizer- ∃ finitely many β ∈ Z with L(β) ̸= L(β − 1)

β1 > β2 > · · · > βq : essential values∅ = L(β1) ⊂ L(β1 − 1) = · · · = L(β2) ⊂ L(β2 − 1)
= · · · = L(βq ) ⊂ L(βq − 1) = S- Define Cj := L(βj − 1)

(j = 1, 2, . . . , q)

C1 ⊂ C2 ⊂ · · · ⊂ Cq : canonical chain- Define Sj = Cj − Cj−1

(j = 1, 2, . . . , q),

C0 = ∅{S1, S2, . . . , Sq }: canonical partition24

5.
Discrete vs Continuous

25Structure of Dec-Min Elements(Z) M-convex set(R) Base-polyhedron

6622110-

1230-

123

Matroidal M-convex set

Unique = min-norm point(Frank+Mu.)(Fujishige)

26Canonical Partition vs Principal Partition
Same construction with parameter
Integer β ∈ ZvsReal λ ∈ R

β1 > β2 > · · · > βq
λ1 > λ 2 > · · · > λ r(essential values)(critical values)
Principal Partition: Japanese tradition, 1968–1980’s
Kishi-Kajitani, Ozawa, Iri, Tomizawa, Fujishige, Nakamura/
Bruno-Weinberg, Narayanan(Survey by Fujishige, 2009)Thm:(Frank+Mu.)- β is essential value ⇐⇒ ∃λ with β ≥ λ > β − 1- Essential values βj are distinct members of⌈λ1⌉ ≥ ⌈λ2⌉ ≥ · · · ≥ ⌈λr ⌉(round-up critical values)- Canonical parttn is aggregation of princical parttn- Canonical chain is a subchain of principal chain27

Proximity Theorem for Dec-Min
Thm:(Frank+Mu.)

mR: minimum norm point of BR∀ dec-min element mZ of BZ satisfies⌊mR⌋ ≤ mZ ≤ ⌈mR⌉−→ Continuous relaxation algorithm
using strong-polynomial algo for min-norm pt mR

28

Example: Proximity Theorem for Dec-Min
mR minimum norm{point} of BR⇒m ∈ BZ is dec-min⌊mR⌋ ≤ m ≤ ⌈mR⌉
̸⇐
6

m3

m5

21mR

Example: BZ = {m1, m2, m3, m4, m5}
0• m1 = (2, 1, 1, 0), m2 = (2, 1, 0, 1)
1
m3 = (1, 2, 1, 0), m4 = (1, 2, 0, 1)
dec-min (Z)m5 = (2, 2, 0, 0)
NOT dec-min (Z)• mR = (3/2, 3/2, 1/2, 1/2) min-norm point (R)• m5 = (2, 2, 0, 0) satisfies(1, 1, 0, 0) = ⌊mR⌋ ≤ m5 ≤ ⌈mR⌉ = (2, 2, 1, 1)

m1
-229

Min-Max Formulas: (Z) vs (R)• Largest compnt of dec-min m:(Z) β1 = max{ ⌈ p(X)/|X| ⌉}X̸=∅(R) λ1 = max{ p(X)/|X| }X̸=∅• Total a-excess: (Z) a ∈ Z( R) a ∈ R∑
min{(x(s) − a)+ : x ∈ B} = max{ p(X) − a|X| }Xs∈S(BZ or BR)• Square-sum:∑∑ ⌊ π(s) ⌋ ⌈ π(s) ⌉x(s)2} = max { p̂(π) −(Z) min {}x∈BZ22π∈ZSs∈Ss∈S∑∑ ( π(s) )2x(s)2} = max { p̂(π) −}(R) min {Sx∈BR2π∈
Rs∈Ss∈S
30

Concluding Remark
Discrete convexity approach works for- M-convex set(Part I)

- Intersection of two M-convex sets
- Network flow

(Part III)- Submodular flow

(Part IV)

- Their weighted versions(Part IV)(Part V)(dec-min/lexico-opt with respect to weight vectors)

31

E N D32

Supplement33

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

6MM♮

-34

Fenchel-type Duality in DCA
f : M♮-convex,

h: M♮-concave（Zn → Z）

Legendre–Fenchel transformf •(p) = max{⟨p, x⟩ − f (x) | x ∈ Zn}h◦(p) = min{⟨p, x⟩ − h(x) | x ∈ Zn}

Fenchel-type duality thm(Murota 96, 98)◦•
minn{f (x) − h(x)} = maxn{h (p) − f (p)}x∈Zp∈Z

35

Referencing Relations between Papers
Vei Meg Fuj Gro F-G I-K D-R Fuj Hoc Tam
Veinott 1971·–––––––––
Megiddo 1974–·––––––––
Fujishige 1980
–R·–––––––
Groenevelt 1985/91 –R
R·R–––––Feder.–Groen.1986–RR–·–––––
Ibaraki–Katoh 1988 –RRRR·––––––––––·–––Dutta–Ray 1989
Fujishige 1991
–R
RR–R R2nd ·–––––R
RR––·–
Hochbaum 1994
RRRR––R
R–Tamir 1995
·Paper at the left refers to papers marked R in the same row
R2nd means that reference is made in the 2nd edition (2005) only36

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

M♮ ∩ L♮ = separable
37