IMA Minneapolis, February 23-27, 2015
Convexity and Optimization: Theory and Applications

DC Programmingin Discrete Convex Analysis
Kazuo Murota (U. Tokyo)
withTakanori Maehara (Shizuoka U.)
150224DCprogIMAminneapolis1Discrete Convex Functions
functions Zn → R
convex-extensible

L♮

SeparableM♮

f : Zn → R

f is convex-extensible⇔ ∃ convex f :f (x) = f (x)f is separable ⇔ f (x) = φ1(x1) + · · · + φn(xn)2Discrete DC Program
DC = Diﬀerence of Convex

min {g(x) − h(x)}x∈Zng, h: “convex” (dom g ⊆ dom h)convexity: M♮–M♮, M♮–L♮, L♮–M♮, L♮–L♮(Examples)
Submod. max. under matroid constraint: M♮–L♮
Subm-superm proc. (Narasimhan-Bilmes): L♮–L♮3

DC Algorithm(Pham Dinh Tao 1985(ca.))min{g(x) − h(x)}=⇒min{g(x) − ⟨p, x⟩}

subgradient p ∈ ∂h(x)Algorithm 1
DC algorithm
Let x(1) be an initial solution
for k = 1, 2, . . . do(Dual phase) Pick p(k) ∈ ∂h(x(k))(Primal phase) Pick x(k+1) ∈ argmin (g − p(k))
if (g − p(k))(x(k)) = (g − p(k))(x(k+1)) thenReturn x(k)end ifend for• concave-convex proc (Yuille–Rangarajan 03)• submod-supermod proc (Narasimhan–Bilmes 05)
cf. supermod-submod proc, mod-mod proc
(Iyer–Bilmes 12; Iyer–Jegelka–Bilmes 13)
4

Subdiﬀerentiability & Biconjugacy∂f (x) = {p | f (y) − f (x) ≥ ⟨p, y − x⟩ (∀y)}
f •(p) = sup {⟨p, x⟩ − f (x)}xp ∈ arg min{f •(q) − ⟨q, x⟩}q⇐⇒ p ∈ ∂f (x)⇕x ∈ arg min{f (y) − ⟨p, y⟩}x⇐⇒ x ∈ ∂f •(p)biconjugacy: f •• = f

5

Integral Subgradients & Biconjugacy
f : Zn → Z(Discrete life is not easy)∂Zf (x) ̸= ∅ ?
f •• = f ?

Example: D = {(0, 0, 0), ±(1, 1, 0), ±(0, 1, 1), ±(1, 0, 1)}{(x1 + x2 + x3)/2, x ∈ D,f (x1, x2, x3) =+∞,o.w.

D is “convex”: conv(D) ∩ Zn = D∂fR(0) = {(1/2, 1/2, 1/2)}∂Zf (0) = ∅f ••(0) = − inf max{0, |p1+p2−1|, |p2+p3−1|, |p3+p1−1|}p∈Z3f ••(0) = −1 ̸= 0 = f (0)6Biconjugacy in Matroids (promising clue)
Biconjugacy
Independent sets I

Rank function ρExchange axiom⇐⇒

Submodularity(vertex)⇐⇒(face)

Subgradients∂ρ(∅) = Independence polyhedron7L-convex and M-convex
Functions8L♮-convexity from Mid-pt-convexity(Favati-Tardella 1990, Murota 1998, Fujishige–Murota 2000)
6qqq p+q p2

-p+q2

=⇒pp

Mid-point convex (g(: Rn →) R):
p+qg(p) + g(q) ≥ 2g2=⇒ Discrete mid-point convex (g : Zn → R)(⌈p+qg(p) + g(q) ≥ g2
L♮-convex function

⌉)(⌊

⌋)

p+q+g2(L = Lattice)9Mid-pt Convexity for 01-Vectors
qFor p, q ∈ {0, 1}n:
⌊p+q2

⌋

⌈

6p+q2

⌉

=p∨q

p=p∧q

Discrete mid-pt convexity:
(⌈⌉)
(⌊
⌋)
p+q
p+qg(p) + g(q) ≥ g+g22⇐⇒ Submodularity:g(p) + g(q) ≥ g (p ∨ q) + g (p ∧ q)
10

L♮-convexity from Submodularity—original definition (Murota 1998) —Def:

g : Zn → RL♮-convex ⇐⇒g̃(p0, p) = g(p − p01) is submodular in (p0, p)g̃ : Zn+1 → R,

1 = (1, 1, . . . , 1, 1)

11

Rem: L♮-convex vs Submodular
n=1

Fact 1: Any g : Z → R is submodular
Fact 2: Function g : Z → R is L♮-convex⇐⇒ g(p − 1) + g(p + 1) ≥ 2g(p) for all p ∈ Z

12

L♮-convex Function: Examples
Quadratic: g(p) =∑∑i

⇔ aij ≤ 0aij pipj is L♮-convex

j(i ̸= j),∑aij ≥ 0 (∀i)

j

Separable convex: For univariate convex ψi and ψij∑∑g(p) =ψi(pi) +ψij (pi − pj )ii̸=jRange: g(p) = max{p1, p2, . . . , pn} − min{p1, p2, . . . , pn}
Submodular set function: ρ : 2V → R⇔ ρ(X) = g(χX ) for some L♮-convex g
Multimodular: h : Zn → R is multimodular ⇔h(p) = g(p1, p1 + p2, . . . , p1 + · · · + pn) for L♮-convex g13M♮-convexity from Equi-dist-convexity(Murota 1996, Murota –Shioura 1999)
6

jy6

yy′x′

=⇒
xy y ′ x′ x
Equi-distance convex (f : Rn → R):--x if (x) + f (y) ≥ f (x − α(x − y)) + f (y + α(x − y))=⇒ Exchange (f : Zn → R) ∀x, y , ∀i : xi > yi[f (x) + f (y) ≥ min f (x − ei) + f (y + ei),]min {f (x − ei + ej ) + f (y + ei − ej )}xj <yjM♮-convex function(M = Matroid)14

M♮-convex Function: Examples
Quadratic: f (x) =∑∑i

⇔ aij ≥ 0,aij xixj is M♮-convexjaij ≥ min(aik , ajk ) (∀k ̸∈ {i, j})

Min value: f (X) = min{ai | i ∈ X}

[unit preference]

Matroid rank: f (X) = − rank of X
Cardinality convex: f (X) = φ(|X|)∑Separable convex: f (x) =φi(xi)(φ: convex)(φi: convex)

iLaminar convex: f (x) =∑φA(x(A))(φA: convex)

A{A, B, ....}: laminar ⇔ A ∩ B = ∅ or A ⊆ B or A ⊇ B
15

Matching / Assignment
U
u1
u2
u3
u4

V
v1
v2
v3

X = {u1, u2}
u1
v1
u2
v2

X = {u1, u2}
u1
v1
u2
v3

M1

M2

E

Max weight for X ⊆ Uf (X) = max{∑(w: given weight)

w(e) | M : matching, U ∩ ∂M = X}e∈M

Max-weight func f is M♮-concave (Murota 1996)• Proof by augmenting path
• Extension to min-cost network flow16

M-L Conjugacy Theorem
Integer-valued discrete fn
Legendre transform:f : Zn → Zf •(p) = sup [⟨p, x⟩ − f (x)]x∈ZnM♮-convex and L♮-convex are conjugate
f 7→ f • = g 7→ g • = ffunction Zn → Z
convex-extensible

M♮

L♮(Murota 1998)

biconjugacy
f •• = f17

Discrete Toland-Singer Dualityf •(p) = sup{⟨p, x⟩ − f (x) | x ∈ Zn}
h : Zn → Z: M♮-convex or L♮-convex(g : any fn)

Toland-Singer Duality(Maehara-Murota 13)
inf {g(x) − h(x)} = inf {h•(p) − g •(p)}x∈Znp∈Zn(Proof) Integral biconjugacy: h•• = h.

inf {g(x) − h(x)} = inf {g(x) − h••(x)}xx= inf {g(x) − sup{⟨p, x⟩ − h•(p)}}xp= inf inf {g(x) − ⟨p, x⟩ + h•(p)}xp= inf {h•(p) − sup{⟨p, x⟩ − g(x)}} = inf {h•(p) − g •(p)}.
pxp18

Toland-Singer vs Fenchelf •(p) = sup{⟨p, x⟩ − f (x) | x ∈ Zn}

Toland-Singer Duality(Maehara-Murota 13)

inf n{g(x) − h(x)} = infn{h•(p) − g •(p)}x∈Zp∈Z(g, h)= (any, M♮), (any, L♮)Fenchel Duality(Murota 1996, 1998)

inf n{g(x) + h(x)} = − infn{h•(p) + g •(−p)}

x∈Zp∈Z(g, h)= (M♮, M♮), (L♮, L♮)
containing: Edmonds’s matroid intersection
Frank’s weight splitting for wtd matroid intersection
Fujishige’s Fenchel duality for submod set functions
19Submodularity and Convexity—1980’s vs 2000’s —20Submodularity & Convexity in 1980’s
ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )• min/max algorithms(Grötschel–Lovász–Schrijver/ Jensen–Korte, Lovász)

min ⇒ polynomial,• Convex extension

max ⇒ NP-hard(Lovász)

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

discrete separation, Fenchel min-max

Submodular set function= Convexity + Discreteness21

But . . .
decreasing
marginal return ←→ concave/submodularThis means . . .
Submodular ≈ Concave

We know . . .
ρ(X) = φ(|X|) (φ: concave) is submodular
22Submodularity & Convexity in DCA• M♮-concave function is submodular• L♮-convex

function is submodularsubmodularM♮-L♮ -concave

convex• Sum of M♮-concave fns is submodular• Sum of L♮-convex fns is L♮-conv (subm)
23Representability of DC fns
Complexity of DC programs

24

Discrete DC Functions: Representability
Discrete DC = DDC = Diﬀerence of Discrete Convex

L♮–L♮ : (almost) all functions
L♮–M♮ : ⊆ submodular
M♮–L♮ : ⊆ supermodular
M♮–M♮ : ? – Not every function is M♮–M♮
25

Example of Non-M♮–M♮ DC Function
f (x, y, z, w) = xz + xw + yz is not M♮–M♮ DC(No h exists s.t. both f + h and h are M♮-convex)(Proof)discrete Hessian H(x) = [Hij (x)]:Hij (x) = f (x + ei + ej ) − f (x + ei) − f (x + ej ) + f (x)Theorem:(Hirai–Murota 04, Murota 07)
f is M♮-convex ⇔ for every x ∈ Zn:

Hij (x) ≥ 0 Hij (x) ≥ min{Hik (x), Hjk (x)} (i, j ̸= k)Both Hf + Hh and Hh must satisfy this condition
00Hf = 1100101
100



10

00∗∗Hh = ∗∗∗∗∗∗∗∗∗∗∗∗∗
∗
26

Complexity of Discrete DC Programs
DC = Diﬀerence of Convex

min {g(x) − h(x)}x∈Zng, h: “convex”

Convexity: M♮–M♮, M♮–L♮, L♮–M♮, L♮–L♮x ∈ Zng\hM♮
M♮ NP-hard
L♮
open

L♮
NP-hard
NP-hardpseudo-poly; submod min (ring family)x ∈ {0, 1}ng\hM♮
L♮M♮ NP-hard NP-hardL♮
PNP-hard
Kobayashi 14, submod min27

NP-hardness of M♮–M♮ DC Programs• Matroid rank fns are M♮-concave• NP-hard Problem:(Kobayashi 14)

Min f (X) s.t. |X| = m⇐⇒ Min f (X) + δm(X)(Fujishige 05)

for matroid rank fn f(δm: indicator for |X| = m)

f + δm = δm − (−f ) = (M♮-conv) − (M♮-conv)
Reduction from Max-Clique
For graph G, integer k,

f = rank function of graphic matroid,m=( )k2

G has k-clique ⇐⇒ min(f + δm) = k − 128

Discrete DC Algorithm

29

Discrete DC Algorithmminn{g(x) − h(x)}x∈Zminn{g(x) − ⟨p, x⟩}=⇒x∈Z
integral subgradient p ∈ ∂h(x)Algorithm 2
Discrete DC algorithm
Let x(1) be an initial solutionfor k = 1, 2, . . . do(Dual phase) Pick p(k) ∈ ∂h(x(k)) \ ∂g(x(k))(Primal phase) Pick x(k+1) ∈ argmin (g − p(k))
if (g − p(k))(x(k)) = (g − p(k))(x(k+1)) thenReturn x(k)end ifend for• monotone decreasing g(x) − h(x)• ∂g(x) ⊇ ∂h(x) guaranteed• local optimality within U =∪•(p)∂hp∈∂g(x)30Optimality Conditions minn{g(x) − h(x)}x∈Zx: global opt ⇐⇒ ∂ϵg(x) ⊇ ∂ϵh(x) (∀ϵ ≥ 0)⇓∂g(x) ⊇ ∂h(x)⇓x: local opt, i.e., x: minimum in∪∂h•(p)

U =p∈∂g(x)∂ϵf (x) = {p | f (y) − f (x) ≥ ⟨p, y − x⟩−ϵ (∀y)}
31

Subgradient of M♮-/L♮-convex Func
f : Zn → Z,
integral subgradients:∂f (x) = {p ∈ Zn | f (y) − f (x) ≥ ⟨p, y − x⟩ (∀y)}
f : M♮-convex⇒∂f (x) ̸= ∅: L♮-convex set− pi ≤ f (x − χi) − f (x),pj ≤ f (x + χj ) − f (x),pj − pi ≤ f (x − χi + χj ) − f (x)f : L♮-convex⇒(∀i, j)∂f (x) ̸= ∅: M♮-convex set

f (x) − f (x − χA) ≤ ⟨p, χA⟩ ≤ f (x + χA) − f (x) (∀A)

32

Testing for Local Opt: ∂g(x) ⊇ ∂h(x)
M♮–M♮

M♮–L♮

L♮–M♮

L♮–L♮

L♮ ⊇L♮L ♮ ⊇M♮M♮ ⊇L♮

M♮ ⊇M♮

poly-time

poly-time

poly-time

co-NP-compl.

O(n2) ineqs

O(n2) M-min

submod-min(McCormick 96)

g-polymatroid

dual of shortest-path33

Larger Conjugate Classes of Functions(i) sum of two M♮-convex fns M♮+M♮(ii) convolution of two L♮-conv fns L♮ 2 L♮
Subdiﬀerentiability & Biconjugacy holdToland-Singer Duality Thm

h : Zn → Z M♮+M♮ or L♮ 2 L♮

(extension)(g : any fn)

inf n{g(x) − h(x)} = infn{h•(p) − g •(p)}x∈Zp∈Z

34

(Preliminary)Computational Results

35

Max Clique Problem (M♮–M♮ DC)
G = (V, E)

graphrank (X) = maximum cardinality of a forest in X ⊆ E{(k )|X| − rank (X), |X| = 2
Maximizef (X) =−∞,otherwise
for an edge set incident to small number of vertices

f (X) =k(k − 1)
2− (k − 1) ⇐⇒ X is a k-clique36

Max Clique: random graph (M♮–M♮ DC)(k )f (X) = |X| − rank (X) if |X| = 2
Erdős–Rényi graph n = 100, p = 0.1 (av. degree 10)+ clique of size k = 10

max f = 36,Best max f = 35 in 1000 runs

100

4090

3580
30f(X) = |X| - rank(X)frequency

7060
50
4030

25201510205100010152025f(X) = |X| - rank(X)30350102030

405060708090100

iterations

37

Dolphins Network(M♮–M♮ DC)(http://konect.uni-koblenz.de/networks/dolphins)

Representing friendship relation between dolphins

62 vertices, 159 edges
Search for a community of size 10 by maximizing(10)f (X) = |X| − rank (X) if |X| = 2 = 45
30f(X) = |X| - rank(X)25201510

50051015202530

iterations

38

Step 0 (random): f (X) = 3

Visualized by Gephi (https://gephi.github.io/)39

Step 1: f (X) = 15

40

Step 2: f (X) = 1841

Step 4: f (X) = 1942

Step 5: f (X) = 22

43

Step 6: f (X) = 24

44

Step 19: f (X) = 2545

Step 21: f (X) = 27

46

Spanning Tree with Few Colors
G = (V, E)

E=

graph,∪(M♮–M♮ DC)

Ec (color classes)

c∈C

∑

|Ec ∩ X|2,

Maximize f (X) =X : spanning tree

c∈C


−∞,

otherwise

to obtain a spanning tree with few colors

Erdős–Rényi graph n = 100, p = 0.12,744 edges,

10 colors (|C| = 10)47Input48

Step 0 (random) f = 1221

(19, 15, 12, 12, 9, 9, 9, 6, 4, 4)49

Step 1

f = 3445(44, 32, 22, 1, 0, 0, 0, 0, 0, 0)

50

Step 2

f = 4195(47, 44, 7, 1, 0, 0, 0, 0, 0, 0)51

Summary• Framework of “discrete DC programming”
M♮–M♮, L♮–M♮ (subm), M♮–L♮ (superm), L♮–L♮,
integral subgradient, biconjugacy, Toland-Singer• Local optimality condition∂g(x) ⊇ ∂h(x), checking this condition• Algorithm
monotone, finite, local opt• Discrete convex analysis for nonconvex problems

Further study with
Takanori Maehara, Naoki Marumo, and ......
52

References
Maehara–Murota: A framework of discrete
DC programming by discrete convex analysis,
Math. Programming, 2014, on-line
Murota: Discrete Convex Analysis, SIAM, 2003
Fujishige: Submodular Functions and Optimization,
2nd ed., Elsevier, 2005 (Chap. VII)53

Survey/Slide/Video/Software[Survey]
Murota: Recent developments in discrete convexanalysis (Research Trends in Combinatorial
Optimization, Bonn 2008, Springer, 2009, 219–260)[Slide] [Video]
http://www.misojiro.t.u-tokyo.ac.jp/ murota/publist.html#DCA[Video]https://smartech.gatech.edu/xmlui/handle/1853/43257/
https://smartech.gatech.edu/xmlui/handle/1853/43258/[Software] DCP (Discrete Convex Paradigm)
http://www.misojiro.t.u-tokyo.ac.jp/DCP/

54

E N D

55