Sixth Asian Conference on Nonlinear Analysis and Optimization, Nov. 6, 2018

DC Programming in
Discrete Convex Analysis
Kazuo Murota
Tokyo Metropolitan University1

DC Programming (DC=Difference of Convex)
DC Program:

min 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℝ𝑛𝑛𝑔𝑔, ℎ: ℝ𝑛𝑛 → ℝ ∪ +∞ , convex[Tao 1985][Tuy 1987]

2

DC Programming
DC Program:

min 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℝ𝑛𝑛𝑔𝑔, ℎ: ℝ𝑛𝑛 → ℝ ∪ +∞ , convex

Discrete DC Program:[Tao 1985][Tuy 1987]

min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℤ

𝑔𝑔, ℎ: ℤ𝑛𝑛 → ℤ ∪ +∞ , discrete convex (L♮ or M♮）[Maehara-Murota 2015]

3

DC Programming
DC Program:

min 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℝ𝑛𝑛𝑔𝑔, ℎ: ℝ𝑛𝑛 → ℝ ∪ +∞ , convex

Discrete DC Program:[Tao 1985][Tuy 1987]

min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℤ

𝑔𝑔, ℎ: ℤ𝑛𝑛 → ℤ ∪ +∞ , discrete convex (L♮ or M♮）[Maehara-Murota 2015]

Discrete DC Program:

min 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥𝑥𝑥∈ℤ𝑛𝑛𝑔𝑔, ℎ: ℤ𝑛𝑛 → ℤ ∪ +∞ , integrally convex[Murota-Tamura 2018]
4

Backgrounds• DC Programming (DC = Difference-of-Convex)
 DC Algorithm
 Subgradient, biconjugacy• Discrete Convex Analysis
 Integral convexity
 Integral subgradient5

1. DC Programming (continuous)
2. Discrete Convex Analysis
3. DC Programming (M/L-convex)
4. DC Programming (integrally convex)

1. DC Programming (continuous)
2. Discrete Convex Analysis
3. DC Programming (M/L-convex)
4. DC Programming (integrally convex)

DC Programming (DC=Difference of Convex)
DC Program:

min 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℝ𝑛𝑛𝑔𝑔, ℎ: ℝ𝑛𝑛 → ℝ ∪ +∞ , convex[Tao 1985][Tuy 1987]8

Some Features of DC Programming• Expressive Power Almost all optimization problems• Mathematical Properties
 Toland-Singer duality theorem, Optimality conditions• Algorithms
 Convex analysis approach: for local opt
subgradient, monotonicity guarantee, fast Combinatorial approach: for global opt
cutting plane, branch-and-bound9

Subgradient & Subdifferential• Subgradient 𝑝𝑝 :𝑓𝑓 𝑦𝑦 − 𝑓𝑓 𝑥𝑥 ≥ 𝑝𝑝, 𝑦𝑦 − 𝑥𝑥∀𝑦𝑦 ∈ ℝ𝑛𝑛

𝑝𝑝 ∈ ℝ𝑛𝑛

𝑓𝑓 𝑦𝑦 − 𝑓𝑓 𝑥𝑥 ≥ 𝑝𝑝, 𝑦𝑦 − 𝑥𝑥∀𝑦𝑦 ∈ ℝ𝑛𝑛

• Subdifferential :𝜕𝜕𝜕𝜕 𝑥𝑥 =𝜕𝜕𝜕𝜕 𝑥𝑥 = 1

𝜕𝜕𝜕𝜕 𝑥𝑥 = [−1, 1]
10

DC Algorithm (continuous variables)[Tao c. 1985]

min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

Initial point 𝑥𝑥𝑥𝑥∈ℝ𝑝𝑝 ← subgradient of ℎ 𝑥𝑥 at 𝑥𝑥ℎ 𝑦𝑦 ≃ ℎ 𝑥𝑥 + 𝑝𝑝, 𝑦𝑦 − 𝑥𝑥(first-order approx)

𝑥𝑥 ← solve convex program min𝑛𝑛 𝑔𝑔 𝑦𝑦 − 𝑝𝑝, 𝑦𝑦𝑦𝑦∈ℝ

Stop if 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥 does not decrease11ｇ12

1. DC Programming (continuous)
2. Discrete Convex Analysis
3. DC Programming (M/L-convex)
4. DC Programming (integrally convex)

Discrete Convex Analysis
Theory of Matroid

M♮-convex&[Murota 98]

Submodular Func. + Convex
Analysis⟷L♮-convex

14

Structures for Discrete Convex Functions (1)discrete(ly) convex,
separable convex

15

Structures for Discrete Convex Functions (1)discrete(ly) convex,separable convex

submodular (195*/6*),
valuated matroid (1990)

16

Structures for Discrete Convex Functions (1)discrete(ly) convex,
separable convex

submodular (195*/6*),
valuated matroid (1990)

17

Structures for Discrete Convex Functions (1)discrete(ly) convex,
separable convex

submodular (195*/6*),
valuated matroid (1990)

multi-modular (1985),
integrally convex (1990),
M-/ M♮-convex (1996,1999), L-/ L♮-convex (1998,2000),
BS-conv (2013), UJ-conv (2013)18

Discrete Convex Functions
functions ℤ𝑛𝑛 → ℝ

Integrally convex

L♮ separable M♮

𝑓𝑓: ℤ𝑛𝑛 → ℝ

𝑓𝑓 is separable ⟺ 𝑓𝑓 𝑥𝑥 = 𝜑𝜑1 𝑥𝑥1 + ⋯ + 𝜑𝜑𝑛𝑛 𝑥𝑥𝑛𝑛

19Some History of Discrete Convex Analysis
1935 Matroid

Whitney

1965 Submodular function

Edmonds

1975 Engineering application of matroid

Iri, Recski

1983 Submodularity and convexity
Lovász, Frank, Fujishige
1990 Valuated matroid

Integrally convex function

Dress–Wenzel

Favati–Tardella1998 Discrete convex analysis

Murota2000 Submodular function minimization algorithm
Iwata–Fleischer–Fujishige, Schrijver
2015 Discrete convex functions on graphs

Hirai20

Structures for Discrete Convex Functions (1)discrete(ly) convex,
separable convex

DCA on {0,1}𝑛𝑛submodular (195*/6*),
valuated matroid (1990)

DCA on ℤ𝑛𝑛multi-modular (1985),
integrally convex (1990),
M-/ M♮-convex (1996,1999), L-/ L♮-convex (1998,2000),
BS-conv (2013), UJ-conv (2013)21

Structures for Discrete Convex Functions (2)×× ・・・ ×bisubmodular

L-conv fn on trees/graphs

× ・・・ (Kolmogorov 2011, Hirai 2015)

DCA beyond ℤ

𝑛𝑛

L-conv fn on CAT(0)(advocated by Hirai)

22

References for Discrete Convex Analysis
Murota:Discrete Convex Analysis, SIAM, 2003

Fujishige: Submodular Functions and Optimization,
2nd ed., Elsevier, 2005 (Chap. VII)
The Logic of Logistics,
Simchi-Levi, Chen, Bramel:
3rd ed., Springer, 2014 (Chap. 2)
http://www.comp.tmu.ac.jp/kzmurota/index.en.html

23

1. DC Programming (continuous)
2. Discrete Convex Analysis
3. DC Programming (M/L-convex)
4. DC Programming (integrally convex)

Discrete DC Programming

min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥𝑥𝑥∈ℤ

𝑔𝑔, ℎ: “convex”(often on 01-vectors)

Some previous works (before 2013)
Quadratic program(Le Thi Hoan An-Pham Dinh Tao 2001)
Discrete tomography (Schüle-Schnörr-Weber-Hornegger 2005)
Mixed Integer program(Niu- Pham Dinh Tao 2008)
Submod-supermod procedure(Narasimhan-Bilmes 2005)
Difference of submod (for global)(Kawahara-Washio 2011)25

DC Programming (DC=Difference of Convex)
DC Program:

min 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℝ𝑛𝑛𝑔𝑔, ℎ: ℝ𝑛𝑛 → ℝ ∪ +∞ , convex
Discrete DC Program:[Tao 1985][Tuy 1987]

min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

𝑥𝑥∈ℤ

𝑔𝑔, ℎ: ℤ𝑛𝑛 → ℤ ∪ +∞ , discrete convex (L♮ or M♮ ）[Maehara-Murota 2015]26

Integral Subgradient & Subdifferential• Integral subgradient 𝑝𝑝 :𝑓𝑓 𝑦𝑦 − 𝑓𝑓 𝑥𝑥 ≥ 𝑝𝑝, 𝑦𝑦 − 𝑥𝑥∀𝑦𝑦 ∈ ℤ𝑛𝑛

𝑓𝑓 𝑦𝑦 − 𝑓𝑓 𝑥𝑥 ≥ 𝑝𝑝, 𝑦𝑦 − 𝑥𝑥∀𝑦𝑦 ∈ ℤ𝑛𝑛

• Integral Subdifferential :𝜕𝜕𝜕𝜕 𝑥𝑥 =𝑝𝑝 ∈ ℤ𝑛𝑛𝜕𝜕𝜕𝜕 𝑥𝑥 = 1

𝜕𝜕𝜕𝜕 𝑥𝑥 = [−1, 1]
27

[Murota 1998]

ｇ28

Subdifferetiability and Biconjugacy[Murota 1998]

Lemma 𝑓𝑓: ℤ𝑛𝑛 → ℤ ∪ +∞ : integer-valued
Integral subdifferential 𝜕𝜕𝜕𝜕 𝑥𝑥 is nonempty
if and only if 𝑓𝑓 ●● (𝑥𝑥) = 𝑓𝑓(𝑥𝑥)Technical assumption:
Closed convex hull of dom f is rational-polyhedron

29

Discrete Convex Functions
functions ℤ𝑛𝑛 → ℝ

Integrally convex

L♮ separable M♮

𝑓𝑓: ℤ𝑛𝑛 → ℝ

𝑓𝑓 is separable ⟺ 𝑓𝑓 𝑥𝑥 = 𝜑𝜑1 𝑥𝑥1 + ⋯ + 𝜑𝜑𝑛𝑛 𝑥𝑥𝑛𝑛

30

31

ｇ
32

33

Discrete DC Progr. by Discrete Convex Analysis
DC = Difference of Convex[Maehara-Murota 2015]

min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥𝑥𝑥∈ℤ

𝑔𝑔, ℎ: “convex”( dom 𝑔𝑔 ⊆ dom ℎ )Convexity: M♮−M♮, M♮−L♮, L♮−M♮, L♮−L♮
Examples- Submod. max. under matroid constraint: M♮− L♮

max h (x) s.t. x: indep.  min g(x) - h(x)h(x): submod,g(x): indicator fn of matroid- Submod-supermod proc. (Narasimhan-Bilmes): L♮−L♮
34

Subdifferetiability and Biconjugacy[Murota 1998]

Thm 𝑓𝑓: M♮ - or L♮ - convex,

integer-valued- Subdifferential 𝜕𝜕𝜕𝜕 𝑥𝑥 is an integral polyhedron (≠∅)- Hence integral subgradient 𝑝𝑝 exists at every point x- Hence 𝑓𝑓 ●● = 𝑓𝑓

35

ｇ
36

37

ｇ38

DC Algorithm (discrete variables)
min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥

Initial point 𝑥𝑥𝑥𝑥∈ℤ

𝑝𝑝 ← integral subgradient in 𝜕𝜕ℎ 𝑥𝑥 ＼ 𝜕𝜕𝑔𝑔 𝑥𝑥ℎ 𝑦𝑦 ≃ ℎ 𝑥𝑥 + 𝑝𝑝, 𝑦𝑦 − 𝑥𝑥(first-order approx)

𝑥𝑥 ← solve convex program min𝑛𝑛 𝑔𝑔 𝑦𝑦 − 𝑝𝑝, 𝑦𝑦𝑦𝑦∈𝐙𝐙

Stop if 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥 does not decrease39[cf. Hiriart-Urruty 1989]

40

41

Complexity of Discrete DC Programs[Maehara-Murota 2015]

min𝑛𝑛 𝑔𝑔 𝑥𝑥 − ℎ 𝑥𝑥𝑥𝑥∈ℤ

𝑔𝑔, ℎ: “convex” ( dom 𝑔𝑔 ⊆ dom ℎ )Convexity: M♮−M♮, M♮−L♮, L♮−M♮, L♮−L♮

𝑔𝑔 ∖ ℎM♮L♮𝑥𝑥 ∈ ℤ𝑛𝑛M♮
L♮NP-hard NP-hard
open
NP-hardpseudo-poly; submod min (ring family)

𝑔𝑔 ∖ ℎM♮L♮𝑥𝑥 ∈ 0, 1 𝑛𝑛M♮
L♮NP-hard NP-hard
PNP-hard

Kobayashi 14,submod min42

1. DC Programming (continuous)
2. Discrete Convex Analysis
3. DC Programming (M/L-convex)
4. DC Programming (integrally convex)

Subclasses of Integrally Convex Functions

Sep-conv ⊂M♮-conv ⊂ M♮2-conv
L♮-conv

M ♮2 = M ♮ + M ♮ (sum)⊂ L♮2-conv
L ♮2 = L ♮ □ L ♮⊂ Int-conv(convolution)

44

Integrally Convex Set

YESNONO

45

Integrally Convex Set

YESNONO

46

Integrally Convex Function [Favati-Tardella 90]𝑧𝑧

integral neighborhood of 𝑥𝑥 ∈ R𝑛𝑛𝑧𝑧

Local convex extension of 𝑓𝑓:𝒛𝒛𝒛𝒛

𝒛𝒛Def. 𝑓𝑓 is integrally convex ⇔ 𝑓𝑓̃ is convex47Local Characterization of IC-Functions
local convex extension of 𝑓𝑓:𝒛𝒛

Def. 𝑓𝑓 is integrally convex ⇔ 𝑓𝑓̃ is convex

Prop.

𝒛𝒛

𝒛𝒛

𝑦𝑦𝑥𝑥

[Favati-Tardella90] [Moriguchi-Murota-Tamura-Tardella 17]

𝑓𝑓 is integrally convex（dom 𝑓𝑓 is integrally convex）⇔ ∀ 𝑥𝑥, 𝑦𝑦 ∈ dom 𝑓𝑓, 𝑥𝑥 − 𝑦𝑦 ∞ = 2

𝑓𝑓 𝑥𝑥 + 𝑓𝑓 𝑦𝑦 ≥ 2𝑓𝑓̃𝑥𝑥 + 𝑦𝑦248

Subgradient of Discrete Convex Function
Thm 𝑓𝑓: integrally convex,[Murota-Tamura 2018]

integer-valued- Integral subgradient 𝑝𝑝 exists at every point x- I.e., subdifferential 𝜕𝜕𝜕𝜕 𝑥𝑥 has an integer point(but NOT an integral polyhedron)- Hence 𝑓𝑓 ●● = 𝑓𝑓

[Murota 1998]

Thm 𝑓𝑓: M♮ -/L♮ -/M♮2-/L♮2-convex, integer-valued- Subdifferential 𝜕𝜕𝜕𝜕 𝑥𝑥 is an integral polyhedron- Hence integral subgradient 𝑝𝑝 exists at every point x
49

ｇ50

Subgradient of Integrally Convex Function
Thm 𝑓𝑓: integrally convex,[Murota-Tamura 2018]

integer-valued- Integral subgradient 𝑝𝑝 exists at every point x- I.e., subdifferential 𝜕𝜕𝜕𝜕 𝑥𝑥 has an integer point

Proof:

Thm 𝑓𝑓: integrally convex[Favati-Tardella90]𝑥𝑥 ∗ ∈ arg min 𝑓𝑓 （minimizer）⟺ 𝑓𝑓(𝑥𝑥 ∗ ) ≤ 𝑓𝑓(𝑥𝑥 ∗ + 𝑑𝑑) ∀𝑑𝑑 ∈ {−1,0, +1}𝑛𝑛+ Fourier-Motzkin elimination
51

ｇ52

ｇ53

DC Programming for Integrally Convex Function• Expressive Power Almost all optimization problems• Mathematical Properties
 Toland-Singer duality theorem, Optimality conditions• Algorithm
 Discrete DC algorithm Framework works using subgradient No polynomial complexity
54

Our Recent Papers on Integral Convexity


K. Murota and A. Tamura:
Integrality of subgradients and biconjugates of integrally convex
functions (arXiv 1806.00992, 2018)



S. Moriguchi, K. Murota, A. Tamura, and F. Tardella:
Scaling, proximity, and optimization of integrally convex functions,Mathematical Programming (2018) (DOI: s10107-018-1234-z)

S. Moriguchi, K. Murota, A. Tamura, and F. Tardella:Discrete midpoint convexity, Mathematics of Operations Research,to appear (arXiv 1708.04579, 2017)

S. Moriguchi and K. Murota:
Projection and convolution operations for integrally convex functions,
Discrete Applied Mathematics (2018) (DOI: 10.1016/j.dam.2018.08.010)
55

END56