# Discrete Convex Analysis III: Algorithms for Discrete Convex Functions Kazuo Murota

## Full text

(1)

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

### Kazuo Murota

(Tokyo Metropolitan University)

180726rimsCOSS3

(2)

(3)

## A1.

(4)

W

(5)

separable convex

### 2n+ 1

integrally convex

n

L-

convex

n+1

M-

convex

1

n

X

Y

X

i

j

(6)

### x

#neigh poly-time algorithm -bors local opt global opt

submodular

n Y

(set fn)

separable-conv

Y

integrally-conv

n N L-conv (Zn)

n Y M-conv (Zn)

2 Y

(7)

-

6

f1(x)

f2(x/2)

True minimum

### •

exists

in a neighborhood of

a scaled local minimum

### •

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

(8)

### x

#neigh poly-time algorithm -bors local opt global opt

submodular

n Y Y

(set fn)

separable-conv

Y Y

integrally-conv

n N N

L-conv (Zn)

n Y Y

M-conv (Zn)

2 Y Y

(9)

## A2.

(10)

(Murota 96)

### Ex:

x + (0, 1, 0, 0, 1, 0, 0, 0) Can check with

2 fn evals

(11)

### Steepest Descent for M-convex Fn

S0: Find a vector x

S1: Find

that minimizes

i

j

S2: If

i

j

, stop

(

### x

: minimizer)

S3: Set x := x ei + ej and go to S1

- 6

I

(Shioura 98)

minimizer

with

,

### ⇒

Murota 03, Shioura 98, 03, Tamura 05

Dress–Wenzel’s alg for valuated matroid

Kalaba’s alg for min spanning tree

(12)

e

e

e

e

e

e

### DCA view

linear optimization on an M-convex set

M-optimality: f(x) f(x ei + ej)

(13)

### T

e

Given pair of trees

e e

. . . .

### T−e+e

e e

New pair of trees

### +e−e

e e

Exchange property: For any

, e

there exists e

s.t.

e

e

,

e

e

(14)

### Kruskal’s Greedy Algorithm for MST

Kruskal (1959)

S0: Order edges by length:

1

2

S1:

;

S2: Pick edge

i

S3: If

i S4: Update

i;

; go to S2

(15)

### Kalaba’s Algorithm for MST

Kalaba (1960), Dijkstra (1960)

S0:

### T=

any spannning tree

S1: Order e

by length:

1

2

### )≤ · · ·k= 1

S2: ek = longest edge s.t.

ek

ek is tree S3:

ek

ek;

; go to S2

ek

ek

(16)

## A3.

(17)

(Murota 98,03)

±

### q)(∀q∈ {0,1}n)Ex:

p + (0, 1, 0, 1, 1, 1, 0, 0)

±

±

Can check with

### n

5 (or less) fn evals using submodular fn min algorithm

(Iwata-Fleischer-Fujishige, Schrijver,Orlin, Lee-Sidford-Wong)

(18)

### Steepest Descent for L♮-convex Fn

(Murota 00, 03, Kolmogorov-Shioura 09, Murota-Shioura 14)

S0: Find a vector

and set

S1: Find

and

that minimize

X

S2: If

X

, stop (

### p

: minimizer)

S3: Set p := p + εχX and go to S1

### Thm:

(Murota-Shioura 14)

Termination exactly in

### ) + 1

iterations, where

+

+

i

i

(19)

### Monotone Steepest Descent for L♮-convex Fn

S0: Find a vector

s.t

and set

S1: Find

that minimizes

X

S2: If

X

, stop (

### p

: minimizer) S3: Set p := p + χX and go to S1

### Thm:

(Murota-Shioura 14)

Termination exactly in

### ) + 1

iterations, where

### }

Application to ascending auction

(20)

0 0 0 1 2 0

0 0 0 1 1

0 0 0 1 2

1 1 1

1 3

2 2 2 O2

p

p

(21)

(one-to-all)

one vertex (

### s

) to all vertices, length

, integer

Maximize

subject to

### DCA view

linear optimization on an L-convex set (in polyhedral description)

Dijkstra’s algorithm (Murota-Shioura 12)

= steepest ascent for L-concave maximization with uniform linear objective (1, 1, . . . , 1)

(22)

### Optimality & Proximity Theorems

Func Class Optimality Proximity

L-convex f(x) f(x + χS) (S) f(x + 1) = f(x) (M. 01)

xxα∥ ≤ (n1)(α1)

(Iwata-Shigeno 03)

M-convex f(x) f(x χu + χv) (u, v V ) (M. 96)

xxα∥ ≤ (n1)(α1)

(Moriguchi-M.-Shioura 02)

L2-convex (L2L convol)

f(x) f(x + χS) (S)

f(x + 1) = f(x) xxα∥≤2(n1)(α1)

(M.-Tamura 04)

M2-convex (M+M)

f(x) f(x χU + χW)

(U, W; |U| = |W|) (M. 01)

xxα∥ ≤ n221)

(M.-Tamura 04)

integrally convex

f(x) f(x χU + χW)

(U, W) (Favati-Tardella 90)

xxα∥ ≤ (n+1)!2n1 1)

(Moriguchi-M.-Tamura -Tardella 16)

∥ · ∥ = ∥ · ∥

(23)

## A4.

(24)

### Intersection Problem (f1 +f2)

Recall: L + L L, M + M ̸⇒ M

Minimizes

1

2 for M-convex

1,

2

Maximizes

1

2 for M-concave

1,

### f

2 (submodular function maximization)

### ⇔

Fenchel duality (min = max)

Valuated matroid intersection (Murota 96)

Weighted matroid intersection

(Edmonds, Lawler, Iri-Tomizawa 76, Frank 81)

(25)

M+M is NOT M

,

: M-convex (Zn

R),

1

2

(1)

minimizes

1

2 (Murota 96)

### ⇐⇒ ∃p

(certificate of optimality)

minimizes

1

(M-opt thm)

minimizes

2

(M-opt thm)

(2)

1

2

1

2

(3)

1,

### f

2 are integer-valued

integral

(26)

### M-convex Intersection Algorithms

Natural extensions of

weighted (poly)matroid intersection algorithms

Exchange arcs are weighted

### k

f1(x ei + ej)?

f1(x) 6

f2(x ei + ek)

f2(x)

“upper-bound lemma”

“unique-max lemma”

### •

cycle-canceling (Murota 96, 99)

### •

successive shortest path (Murota-Tamura 03)

### •

scaling (Iwata-Shigeno 03, Iwata-Moriguchi-Murota 05)

(27)

### Convolution

Convolutions of M-convex functions:

12

2

y

1

2

12

22

3

12

22

2

k

### )(x)

can be computed by M-convex intersection algorithms cf. aggregated utility function

1

2

12

2

(28)

Updating...

## References

Related subjects :