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

Discrete Convex Analysis III:
Algorithms for Discrete Convex Functions
Kazuo Murota(Tokyo Metropolitan University)

160512BonnHCMecon3
1

Contents of Part III
Algorithms for Discrete Convex Functions
A1. Minimization (General)
A2. M-convex Minimization
A3. L-convex Minimization
A4. M-convex Intersection
A5. Submodular Maximization

2

A1.
Minimization (General)
Optimality Criterion
Descent Method
Scaling and Proximity

3

Optimality Criterion
Global opt

Local optvsf (x)convexf (x)nonconvex

Local opt wrt neighborhood4Descent Methodf (x)S0: Initial sol x∗
S1: Minimize f (x) in nbhd of x∗ to obtain x•
S2: If f (x∗) ≤ f (x•), return x∗ (local opt)
S3: Update x∗ := x•; go to S1……What is nbhd ?
5

Scaling and Proximity
6f1(x)
f2(x/2)

Proximity theorem:
True minimum • exists
in a neighborhood of•a scaled local minimum-−2−1 0 1 2 3 4x

⇒ efficient algorithm

Facts in DCA:

• Scaling preserves L-convexity• Scaling does NOT preserve M-convexity• Proximity thms known for L-conv and M-conv
6

A2.
M-convex Minimization

7

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

M-convex(Murota 96)x∗: global opt⇐⇒ local opt 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 ⇒8Steepest Descent for M-convex Fn
S0: Find a vector x ∈ dom f
S1: Find (i, j) that minimizes f (x − ei + ej )S2: If f (x) ≤ f (x − ei + ej ), stopx∗(x: minimizer)
S3: Set x := x − ei + ej
and go to S1

j6

I-

Minimizer Cut Thm∃ minimizer x∗ withix(Shioura 98)x∗(i) ≤ x(i)−1, x∗(j) ≥ x(j)+1⇒ Murota 03, Shioura 98, 03, Tamura 05• Dress–Wenzel’s alg for valuated matroid• Kalaba’s alg for min spanning tree
9

Min Spanning Tree Problem
Tee0

length d : E → R
total length of TX
˜ )=d(Td(e)e∈TThm˜ ) ≤ d(T˜ − e + e0 )T : MST ⇐⇒ d(T⇐⇒ d(e) ≤ d(e0)if T − e + e0 is tree
Algorithm Kruskal’s,
DCA view

Kalaba’s• linear optimization on an M-convex set• M-optimality: f (x∗) ≤ f (x∗ − ei + ej )10Tree: Exchange Property
eeGiven pairof trees

e0

T
T0
..........................................

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 ∈ T11

A3.
L-convex Minimization12

Local vs Global Opt (L\-conv)
Thm：g : Zn → R

L\-convex(Murota 98,03)⇐⇒ local opt g(p∗) ≤ g(p∗±q)(∀q ∈ {0, 1}n)p∗: global opt

Ex: p∗ + (0, 1, 0, 1, 1, 1, 0, 0)p∗⇐⇒ ρ±(X) = g(p∗±χX ) − g(p∗)
takes min at X = ∅Can check with n5 (or less) fn evals
using submodular fn min algorithm(Iwata-Fleischer-Fujishige, Schrijver,Orlin,Lee-Sidford-Wong)
13

Steepest Descent for L\-convex Fn(Murota 00, 03, Kolmogorov-Shioura 09, Murota-Shioura 14)

S0: Find a vector p◦ ∈ dom g

and set p := p◦

S1: Find ε = ±1 and X that minimize g(p + εχX )S2: If g(p) ≤ g(p + εχX ), stop (p: minimizer)
S3: Set p := p + εχXand go to S1

Thm:(Murota-Shioura 14)

Termination exactly in µ(p◦) + 1 iterations, where∗ − p◦k− | p∗ ∈ arg min g}+kpµ(p◦) = min{kp∗ − p◦k+∞∞kqk+∞ = max max(0, q(i)),
ikqk−∞ = max max(0, −q(i))
i14

Monotone Steepest Descent for L\-convex FnS0: Find a vector p◦ ∈ dom g s.t{q | q ≥ p◦} ∩ argmin g 6= ∅and set p := p◦

S1: Find X that minimizes g(p + χX )S2: If g(p) ≤ g(p + χX ), stop (p: minimizer)
S3: Set p := p + χX

Thm:and go to S1(Murota-Shioura 14)

Termination exactly in µ̂(p◦) + 1 iterations, whereµ̂(p◦) = min{kp∗ − p◦k∞ | p∗ ∈ arg min g, p∗ ≥ p◦}⇒ Application to ascending auction
15

Steepest Descent Path for L\-convex Fn3200=g

2

1000

210000011122 12O

11µ(p◦) = µ̂(p◦) = 2kp◦, argmin gk∞ = 1µ(p◦) = µ̂(p◦) = 2kp◦, argmin gk∞ = 216

Shortest Path Problem (one-to-all)one vertex (s) to all vertices,length ` ≥ 0, integer

Dual LPMaximize Σ p(v)subject to p(v) − p(u) ≤ `(u, v) ∀(u, v)
p(s) = 0Algorithm

Dijkstra’s

DCA view• linear optimization on an L\-convex set (inpolyhedral description)(M.-Shioura 12)• Dijkstra’s algorithm= steepest ascent for L\-concave maximization
with uniform linear objective (1, 1, . . . , 1)17

Optimality & Proximity Theorems
Func Class
L-convex

M-convex

L2-convex(L∗L convol)
M2-convex(M+M)
integrally
convex

Optimality

Proximityf (x∗) ≤ f (x∗ + χS ) (∀S)∗−xαk ≤ (n−1)(α−1)
kxf (x∗ + 1) = f (x∗)(Iwata-Shigeno 03)(M. 01)f (x∗) ≤ f (x∗ − χu + χv )kx∗−xαk ≤ (n−1)(α−1)(∀u, v ∈ V )(Moriguchi-M.-Shioura 02)(M. 96)f (x∗) ≤ f (x∗ + χS ) (∀S)∗−xαk≤2(n−1)(α−1)
kxf (x∗ + 1) = f (x∗)(M.-Tamura 04)
2f (x∗) ≤ f (x∗ − χU + χW ) kx∗−xαk ≤ n (α−1)
2(∀U, W )(M. 01)(M.-Tamura 04)
f (x∗) ≤ f (x∗ − χU + χW )???
(∀U, W ) (Favati-Tardella 90)

k · k = k · k∞18

A4.
M-convex Intersection(Fenchel Duality)

19Intersection Problem (f1 + f2)
Recall:L \ + L \ ⇒ L\ ,M\ + M\ 6⇒ M\

M-convex Intersection Algorithm:
Minimizes f1 + f2 for M\-convex f1, f2⇔ Maximizes f1 + f2 for M\-concave f1, f2(submodular function maximization)⇔ Fenchel duality (min = max)
⇒ Valuated matroid intersection(Murota 96)⇒ Weighted matroid intersection(Edmonds, Lawler, Iri-Tomizawa 76, Frank 81)
20M-convex Intersection:
f1, f2 : M\-convex(Zn → R),

Min [M\+M\]

M\+M\ is NOT M\x∗ ∈ dom f ∩ dom f(1) x∗ minimizes f1 + f22(Murota 96)⇐⇒ ∃ p (certificate of optimality)• x∗ minimizes f (x) − hp, xi
1• x∗ minimizes

1f2(x) + hp, xi(M-opt thm)
(M-opt thm)(2) argmin (f1 + f2) = argmin (f1 − p) ∩ argmin (f2 + p)(3) f1, f2 are integer-valued ⇒ integral p21

M-concave Intersection:[Concave version]
f1, f2 : M\-concave (Zn → R),

Max [M\+M\]

M\+M\ is NOT M\x∗ ∈ dom f ∩dom f1

2

f1 + f2 is submodular(1) x∗ maximizes f1 + f2

(Murota 96)⇐⇒ ∃ p (certificate of optimality)• x∗ maximizes f (x) − hp, xi
1• x∗ maximizes

f2(x) + hp, xi(M-opt thm)
(M-opt thm)(2) argmax (f1 + f2) = argmax (f1 − p) ∩ argmax (f2 + p)(3) f1, f2 are integer-valued ⇒ integral p22

M-convex Intersection Algorithms
Natural extensions ofweighted (poly)matroid intersection algorithms
Exchange arcs are weightedii

f1(x − ei + ej )?
− f1(x)f2(x − ei + ek )− f2(x)6

j“upper-bound lemma”

k“unique-max lemma”• cycle-canceling(Murota 96, 99)• successive shortest path
(Murota-Tamura 03)• scaling(Iwata-Shigeno 03, Iwata-Moriguchi-M. 05)
23

Convolution
Convolutions of M\-convex functions:(f12f2)(x) = min(f1(y) + f2(x − y))y(f12f22f3)(x),(f12f22 · · · 2fk )(x)can be computed by M-convex intersection algorithms
cf. aggregated utility function

f1
f1 2 f2
f2

24

A5.
Submodular Maximization

25

Submodularity & Convexity in DCA• M\-concave function is submodular• L\-convex

function is submodular

f : Zn → R submodular

M\-concave

L\ -convex

sbm + sbm ⇒ sbm
L\ + L \ ⇒ L\M\ + M\ 6⇒ M\• Sum of M\-concave fns is submodular(i) M\(ii) M\ + M\(iii) M\ + M\ + M\
26

Submodular Set Function in DCA• Submodular set func = L\-convex on {0, 1}n• (Sums of) M\-concave form nice subclasses
f : {0, 1}n → R
submod=L\-convex
M\ + M \ + M \M\ + M \M\-concave

f : Zn → R
submodular
M\ concave

L\ convex

27

Set Function and Extensions
Set function ⇐⇒ Function on {0, 1}n=ρ(X)ρ̂(χX )
Every set function ρ : {0, 1}n → R can beextended to convex/concave function
610

convex ext
01-

6concave ext

1001-

cf. Lovász extension
28

M\-concave Set Functions
M\-concave is submodular (NOT conversely)
M\-concave forms a nice subclass for maximization• µ(X) = ϕ(|X|)(ϕ: concave)X• µ(X) =(ϕA: concave)ϕA(|A ∩ X|)
A∈T

T : laminar (A, B ∈ T ⇒ A ∩ B = ∅ or A ⊆ B or A ⊇ B )• max-value µ(X) = max{ai | i ∈ X}
• matroid rank

(Fujishige 05)µ(X) = max{|I| | I : independent, I ⊆ X}
• weighted matroid rank (w ≥ 0)

(Shioura 09)µ(X) = max{w(I) | I : independent, I ⊆ X}
29

Dual Character of Matroid Rank Func
ρ(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
Y
submod maximization
submod minimization(M\-concave + M\-concave)(L\-convex + L\-convex)
30

Algorithms for Submodular Set Func
convex extension
computable as
Lovász extension

concave extension
subclass: M\-concave(valuated matroid)(Lovász 03)

1. Greedy algorithm for max of an M\-concave fn(Dress-Wenzel 90)

2. Matroid intersection-type algorithm for max of asum of two M\-concave fns(Murota 96)

3. Pipage rounding algorithm for approx max of asum of several nondecr. M\-concave fns (Shioura 09)31

M\-concave Maximization Algorithmµ(X): M\-concave set function (µ(∅) > −∞ )Greedy algorithm
S0: Put X := ∅S1: Find j ∈ V \ X that maximizes µ(X ∪ {j})S2: If µ(X) ≥ µ(X ∪ {j}), stop (X :maximizer of µ)
S3: Set X := X ∪ {j} and go to S1• (Variant of) Dress–Wenzel’s for valuated matroid• Kruskal’s algorithm for min spanning tree32Submodular Max. under Matroid Constraint
Maximize f (S) s.t. |S| = k
Maximize f (S) s.t. |S| ≤ kMaximize f (S) s.t. S : base in a matroid
Maximize f (S) s.t. S : independent in a matroid
Submodular function maximization under a matroid
constraint is an NP-hard problem in general
BUT
If f is M\-concave, this is an M\-concave intersection
problem and, hence poly-time solvable33

Submodular Welfare Maximization
Maximize f1(S1) + f2(S2) + · · · + fk (Sk ) s.t.

(S1, S2, . . . , Sk ): partition of S

(fi: submodular)

Submodular welfare maximization is an NP-hardproblem in general
BUT
If fi’s are M\-concave, this reduces to an M\concave intersection (or, M\-concave convolution)
and, hence poly-time solvable.
This is the case if fi(X) = ϕi(|X|) with concave ϕi34

E N D35