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

Discrete Convex Analysis III:Algorithms for Discrete Convex Functions

Kazuo Murota(Tokyo Metropolitan University)

180726rimsCOSS3
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

2

A1.
Minimization (General)3Descent Methodf (x)W

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 S1What is neighborhood ?
4

Neighborhood for Local Optimality
separableconvex

integrallyconvex

L♮convexM♮convex

2n + 1

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

{χX − χY }5

Local Optimalityx∗submodular(set fn)
separable-conv#neigh poly-time algorithm-bors local opt global opt
2nY

2nY

integrally-conv

3nN

L♮-conv (Zn)2nY

M♮-conv (Zn)n2Y

6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 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
7

Minimizationx∗

submodular(set fn)
separable-conv#neigh poly-time algorithm-bors local opt global opt
2n
Y
Y

2nY

Y

integrally-conv

3n

N

N

L♮-conv (Zn)

2nY

YYY

M♮-conv (Zn)

n28

A2.
M-convex Minimization

9

Local vs Global Opt (M-conv)
Thm：f : Zn → RM-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 ⇒10

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 S1j6I-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
11

Min Spanning Tree Probleme′Teedge length d : E → R
total length of T∑
˜ )=d(Td(e)e∈TThm
˜ ) ≤ d(T˜ − e + e′)
T : MST ⇐⇒ d(T⇐⇒ d(e) ≤ d(e′)
if T − e + e′ is tree
Algorithm Kruskal’s,DCA view

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

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
13Kruskal’s Greedy Algorithm for MST
Kruskal (1959)

S0: Order edges by length: d(e1) ≤ d(e2) ≤ · · ·S1: T = ∅; i = 1
S2: Pick edge ei
S3: If T + ei contains a cycle, discard ei
S4: Update T = T + ei; i = i + 1; go to S2

T

14

Kalaba’s Algorithm for MST
Kalaba (1960), Dijkstra (1960)

S0: T = any spannning tree
S1: Order e′ ̸∈ T by length: d(e′1) ≤ d(e′2) ≤ · · ·k=1
S2: ek = longest edge s.t. T − ek + e′k is tree
S3: T = T − ek + e′k ; k = k + 1; go to S2Te′kek

15

A3.
L-convex Minimization

16

Local vs Global Opt (L♮-conv)
Thm：g : Zn → RL♮-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)
17

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 + εχX

and go to S1

Thm:(Murota-Shioura 14)

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

Monotone Steepest Descent for L♮-convex Fn
S0: Find a vector p◦ ∈ dom g s.t{q | q ≥ p◦} ∩ argmin g ̸= ∅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{∥p∗ − p◦∥∞ | p∗ ∈ arg min g, p∗ ≥ p◦}⇒ Application to ascending auction
19

Steepest Descent Path for L♮-convex Fn

3200= g210002

10000011122 12O

11µ(p◦) = µ̂(p◦) = 2∥p◦, argmin g∥∞ = 1µ(p◦) = µ̂(p◦) = 2∥p◦, argmin g∥∞ = 220

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)(Murota-Shioura 12)• Dijkstra’s algorithm= steepest ascent for L♮-concave maximization
with uniform linear objective (1, 1, . . . , 1)21

Optimality & Proximity Theorems
Func Class
L-convex
M-convex

L2-convex(L2L convol)
M2-convex(M+M)
integrallyconvex

Optimality

Proximityf (x∗) ≤ f (x∗ + χS ) (∀S) ∥x∗−xα∥ ≤ (n−1)(α−1)(Iwata-Shigeno 03)
f (x∗ + 1) = f (x∗) (M. 01)∥x∗−xα∥ ≤ (n−1)(α−1)
f (x∗) ≤ f (x∗ − χu + χv )(Moriguchi-M.-Shioura 02)(M. 96)(∀u, v ∈ V )f (x∗) ≤ f (x∗ + χS ) (∀S)∗−xα∥≤2(n−1)(α−1)∥xf (x∗ + 1) = f (x∗)(M.-Tamura 04)

f (x∗) ≤ f (x∗ − χU + χW ) ∥x∗−xα∥ ≤ n2 (α−1)
2(∀U, W ; |U | = |W |) (M. 01)
f (x∗) ≤ f (x∗ − χU + χW )(∀U, W ) (Favati-Tardella 90)(M.-Tamura 04)(n+1)!
∥x∗−xα∥ ≤ 2n−1 (α − 1)(Moriguchi-M.-Tamura-Tardella 16)∥ · ∥ = ∥ · ∥∞

22

A4.
M-convex Intersection(Fenchel Duality)

23

Intersection Problem (f1 + f2)
Recall:L♮ + L♮ ⇒ L♮,

M♮ + M♮ ̸⇒ 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)
24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 + f2

12

(Murota 96)⇐⇒ ∃ p (certificate of optimality)• x∗ minimizes f (x) − ⟨p, x⟩(M-opt thm)f2(x) + ⟨p, x⟩(M-opt thm)• x∗ minimizes

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

M-convex Intersection Algorithms
Natural extensions ofweighted (poly)matroid intersection algorithms
Exchange arcs are weightedii
f2(x − ei + ek )− f2(x)6

f1(x − ei + ej )?
− f1(x)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-Murota 05)
26

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
f12 f2f2

27

E N D28