Modern Aspects of Submodularity, Georgia Tech, March 19, 2012

Minimization and Maximization
Algorithms inDiscrete Convex Analysis
Kazuo Murota (U. Tokyo)

120319atlanta2Algorithm
1Contents
B1. Submodularity and Convexity (2000’s)
B2. L-convex and M-convex Functions

A1. M-convex Minimization
A2. L-convex Minimization
A3. Submodular Maximization
A4. M-convex Intersection Algorithm

2

B1.
Submodularity and Convexity(2000’s)

3Submodularity & Convexity in 1980’s
ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )• min/max algorithmsmin ⇒ polynomial,• Convex extension(Grötschel-Lovász-Schrijver/Jensen-Korte, Lovász)

max ⇒ NP-hard(Lovász)

set fn is submod ⇔ Lovász ext is convex• Duality theorems(Edmonds, Frank, Fujishige)

discrete separation, Fenchel min-max

Duality for submodular set functions= Convexity + Discreteness4

On the other hand . . .
decreasing
marginal return ←→ concave/submodularThis means . . .
Submodular ≈ Concave

Moreover . . .
ρ(X) = ϕ(|X|) (ϕ: concave) is submodular
5Submodularity & Convexity in DCA• M\-concave function is submodular• L\-convex

function is submodular

f : Zn → R submodular

M\ -L\-concave

convexsbm + 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\
6

B2.
L-convex and M-convex
Functions7

L-convex Function(L = Lattice)p∨qqg : Zn → R ∪ {+∞}
p∨q

compnt-max

p∧qcompnt-min



pp∧q

Def: g is L-convex ⇐⇒• Submodular:g(p) + g(q) ≥ g(p ∨ q) + g(p ∧ q)

• Translation:∃r, ∀p:\Ln+1 ' Ln⊃
6=g(p + 1) = g(p) + r
6LnL


-L\8M-convex Function (M = Matroid)f : Zn → R ∪ {+∞}

j6yei: 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⊃
6=6MMnM\-9

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

10

Optimality Criterion
Global opt

Local opt

vsf (x)convexf (x)nonconvex

Local opt wrt neighborhood
11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 ?
12

Scaling and Proximity
6

f1(x)f2(x/2)

Proximity theorem:
True minimum • exists

in a neighborhood ofa scaled local minimum−2−1 0 1 2 3 4-x•⇒ eﬃcient algorithm

Facts in DCA:

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

A1.
M-convex Minimization

14

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

Algorithm

Kruskal’s,

Kalaba’s

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

Tree: Exchange Property
eeGiven pairof trees

e0TT0..........................................

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 ∈ T
16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 ⇒17

Steepest Descent for M-convex Fn(Murota 03, Shioura 98, 03, Tamura 05)

S0: Find a vector x ∈ domf
S1: Find i 6= j that minimize f (x − ei + ej )S2: If f (x) ≤ f (x − ei + ej ), stop (x: minimizer)
S3: Set x := x − ei + ej and go to S1

Minimizer Cut Thm∃ minimizer x∗ with(Shioura 98)x∗i ≤ xi − 1, x∗j ≥ xj + 1x∗• Kalaba’s for min spannning tree
• Dress–Wenzel’s for valuated matroid j 6I-i18x

A2.
L-convex Minimization

19

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) = 0

Algorithm

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

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

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

S0: Find a vector p ∈ domg
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• Dijkstra’s algorithm for shortest path (M.-Shioura 12)
π : potential, V \ U : permanent labeled
Special case with g(p) = −1>p:π(v) = min{p(u) + `(u, v) | u 6∈ U }(v ∈ U \ {s})22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)
f (x∗) ≤ f (x∗ − χU + χW ) kx∗−xαk ≤ n (α−1)
2(M. 01)(∀U, W )(M.-Tamura 04)
f (x∗) ≤ f (x∗ − χU + χW )???
2(∀U, W ) (Favati-Tardella 90)

k · k = k · k∞23

A3.
Submodular Maximization24Submodularity & Convexity in DCA• M\-concave function is submodular• L\-convex

function is submodular

f : Zn → R submodular

M\ -L\-concave

convexsbm + 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\25

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

f : Zn → Rsubmodular
M\ concave

L\convex

26

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

610convex ext
01-

6concave ext

1001-

27

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

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}
28

Dual Character of Matroid Rank Funcρ(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\-concave

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

submod maximization

submod minimization(M\-concave + M\-concave)(L\-convex + L\-convex)29

Polymatroid Rank Function
Polymatroid rank function is NOT M\-concave
Exampleρ : 2V → Z on V = {1, 2, 3, 4}(Shioura)ρ(∅) = 0, ρ(i) = 2 (i ∈ V ), ρ(1, 2) = ρ(3, 4) = 4,
ρ(1, 3) = ρ(1, 4) = ρ(2, 3) = ρ(2, 4) = 3,
ρ(X) = 4 if |X| ≥ 3
Exchange fails for X = {1, 2}, Y = {3, 4}30

Algorithms for Submodular Set Func
convex extension
computable asLovász extension

concave extension
subclass: M\-concave(valuated matroid)(Lovász 03)(=⇒ Shioura’s talk)

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 spannning tree

32

A4.
M-convex Intersection Algorithm(Fenchel Duality)

33

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

M-concave Intersection:

Max [M\+M\][Concave version]
M\+M\ is NOT M\
f1, f2 : M\-concave (Zn → R), x∗ ∈ domf1 ∩ domf2
f1 + f2 is submodular, NOT M\-concave(1) x∗ maximizes f1 + f2

(Murota 96)⇐⇒ ∃ p (certiﬁcate of optimality)• x∗ maximizes f (x) − hp, xi(M-opt thm)

f2(x) + hp, xi(M-opt thm)• x∗ maximizes

1(2) argmax (f1 + f2) = argmax (f1 − p) ∩ argmax (f2 + p)(3) f1, f2 are integer-valued ⇒ integral p35

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

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 solvable(This slide shows my answer to a question during the talk)37

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 ϕi(This slide shows my answer to a question at the end of the talk)38

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

E N D40