日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-A-4

整凸関数と分離凸関数に対する Fenchel 双対性
0160319401306430

1.

統計数理研究所・東京都立大学
慶應義塾大学

はじめに

室田一雄
*田村明久

MUROTA Kazuo
TAMURA Akihisa

離散凸解析における Fenchel 双対性の一般形は離散凸解析 [3] においては，双対性が整数の世界で論じられ，L 凸関数や M 凸関数に関して Fenchel型最大最小定理が成り立つことが知られている．これは，マトロイドや劣モジュラ関数に関する最大最小定理を統一的に拡張したものである．
整凸関数の概念 [1, 3] は離散関数の一般的な枠組みを与えており，離散凸解析に登場する殆どすべての関数は整凸関数である．整凸関数は，マトロイド的な組合せ構造をもたない離散凸関数の概念と位置づけることができる．
本研究では，整数値の整凸関数と分離凸関数の組に対して Fenchel 型最大最小定理が成り立つことを示す．証明には，線形不等式系に対する Fourier–Motzkin の消去法を利用する．

minn { f (x) − g(x)} = maxn {g◦ (p) − f • (p)}x∈Zp∈Zである ( f : Zn → Z ∪ {+∞}, g : Zn → Z ∪ {−∞})．
定理 1 と既知の事実 [3, Theorem 8.21] により，これが成立する ( f, g) の組は以下の通りとなる：

f \ g 整凹 L♮ 凹 M♮ 凹 分離凹
整凸XXX
⃝
♮
L 凸X
⃝X
⃝
♮
M 凸XX
⃝
⃝
分離凸⃝⃝
⃝
⃝
♮
♮
(整凸 ⊃ L 凸 ⊃ 分離凸, 整凸 ⊃ M 凸 ⊃ 分離凸)多面体 P が box-integer であるとは，任意の整数ベクトル a, b に対して P ∩ {x | a ≤ x ≤ b} が整数多面体であることと定義される[6, Section 5.15].
2. 結果とその位置づけ
整数格子上の関数 f : Zn → R ∪ {+∞} を考える． Box-integer 多面体 P の整数点は整凸集合であり，逆に，整凸集合の凸包は box-integer 多面体である
実数ベクトル x ∈ Rn の整数近傍を N(x) = {z ∈ Zn |[4]．このことから，定理 1 の系として，次の定理∥x − z∥∞ < 1} と定義し， f の局所凸拡張 f˜ をが得られる．
f˜(x) = sup {⟨p, x⟩+α | ⟨p, z⟩+α ≤ f (z) (∀z ∈ N(x))}
定理 2. Box-integer 多面体 P ⊆ Rn と整数値の分離
p∈Rn ,α∈R凸関数 Φ : Zn → Z ∪ {+∞} に対して(x ∈ Rn ) と定義する (⟨p, x⟩ は内積)． f˜ が Rn 上で凸であるとき， f を整凸関数とよぶ．標示関数が整凸関数であるような集合 (⊆ Zn ) を整凸集合とい∑う．Ψ(x) = ni=1 ψi (xi ) (ただし ψi (t − 1) + ψi (t + 1) ≤2ψi (t), t ∈ Z) の形の関数 Ψ を分離凹関数と呼ぶ．
定理 1. 整数値の整凸関数 f : Zn → Z ∪ {+∞} と整数値の分離凹関数 Ψ : Zn → Z ∪ {−∞} に対して，

min{ f (x) − Ψ(x) : x ∈ Zn }= max{Ψ◦ (p) − f • (p) : p ∈ Zn }min{Φ(x) : x ∈ P ∩ Zn } = max{µ(p) − Φ• (p) : p ∈ Zn }が成り立つ．ただし，左辺の最小値は有限値と仮定し，µ(p) = min{⟨p, x⟩ : x ∈ P} である．
定理 2 は，box-TDI 多面体に関する同様の定理[2, Theorem 3.4] の一般化となっている．

3. 定理 1 の証明(1)

関数 f の凸拡張を f , Ψ の凹拡張を Ψ と表すと，次の関係がある：

が成り立つ．ただしf • (p) = max{⟨p, x⟩ − f (x) : x ∈ Zn },(2)Ψ◦ (p) = min{⟨p, x⟩ − Ψ(x) : x ∈ Zn }(3)

で，(1) の左辺の最小値は有限値と仮定する．

minn { f (x) − Ψ(x)} = minn { f (x) − Ψ(x)}x∈Zx∈R||◦

maxn {Ψ (p) − f (p)} ≤ maxn {Ψ◦ (p) − f • (p)}.
p∈Z•p∈Rここで，上の行の等号 = は，整凸関数 f − Ψ の凸で与えられる．添字集合の定義は以下の通り：
拡張可能性から導かれ，縦の等号 || は，連続変数+−の Fenchel 双対性である．Φ(x) := −Ψ(x) とおき， I1 = {i ∈ I | ai1 = +1}, I1 = {i ∈ I | ai1 = −1};
I10 = {i ∈ I | ai1 = 0},最小化問題の最適解を x∗ ∈ Zn とすると，

p ∈ ∂R f (x∗ ) ∩ (−∂R Φ(x∗ ))(4)を満たす p ∈ Rn が存在する (∂R f (x∗ ), ∂R Φ(x∗ ) は，f , Φ の x∗ における劣微分)．(4) を満たす整数ベク
トル p ∈ Zn の存在を示せば (1) が証明される．
Φ(x) は整数値の分離凸関数だから，∂R Φ(x∗ ) は整数区間である．すなわち，ある α ∈ (Z ∪ {−∞})n ,β ∈ (Z ∪ {+∞})n が存在して， p ∈ −∂R Φ(x∗ ) ⇐⇒−β j ≤ p j ≤ −α j

( j = 1, 2, . . . , n).

(5)

一方， f の整凸性により，∗∂R f (x ) = {p ∈ R |nn∑

d j p j ≤ f (x∗ + d) − f (x∗ )j=1

for all d ∈ {−1, 0, +1}n }である．上の不等式で f (x∗ + d) < +∞ に対応するものを集めてAp ≤ b(6)と表し，行列 A の行番号の集合を I とする．行列
A = (ai j ) の要素は ai j ∈ {−1, 0, +1} を満たし， ベク
トル b = (bi ) の成分 bi は整数である．
(5) と (6) を合併した不等式系に対して FourierMotzkin の消去法を適用する．その際，不等式 (5)が単純な形をしているので，不等式 (6) の部分に関する [5] の議論を拡張することができる．
補題 3. (5) と (6) を合併した不等式系について，変数消去の過程で生成される不等式は冗長である．
このことから， p ∈ ∂R f (x∗ ) ∩ (−∂R Φ(x∗ )) である
ための必要十分条件がn∑max maxap−b,−β≤ pℓ
kjjkℓ

− 
k∈I ℓ  j=ℓ+1
n∑
≤ min minb−ap,−α


ii
jjℓ




+


 i∈Iℓ j=ℓ+1(ℓ = n, n − 1, . . . , 1)

(7)

I +j = {i ∈ I 0j−1 | ai j = +1},

I −j = {i ∈ I 0j−1 | ai j = −1},

I 0j = {i ∈ I 0j−1 | ai j = 0} ( j ≥ 2).
添字集合 I +j , I −j は空集合である可能性もある．例
えば ℓ = n に対する不等式は，In+ = In− = ∅ のとき−βn ≤ pn ≤ −αn という意味である．(4) より，(7)の不等式条件を満たす実数ベクトル p が存在する．
次に整数性を考える．ℓ = n に対する不等式は}{}{,−β≤p≤minmin,−αmax max{−b}{b}inknn+−k∈Ini∈Inであるが，この下限，上限ともに整数であるから，これを満たす整数 pn が存在する．一般の ℓ (1 ≤ ℓ ≤n − 1) に対する不等式において， pn , pn−1 , . . . , pℓ+1が整数に選ばれているとすると，不等式の下限(max{maxk {· · · }, −βℓ }) と上限 (min{mini {· · · }, −αℓ })はともに整数であるから，不等式を満たす整数 pℓが存在する．したがって，(7) の不等式条件を満たす整数ベクトル p が存在する．すなわち，(4) の不等式条件を満たす整数ベクトル p が存在する．
(定理 1 の証明終)
謝辞：本研究は JSPS/MEXT 科研費 (JP20K11697,JP16K00023) の助成を受けた．

参考文献[1] Favati, P., Tardella, F.: Convexity in nonlinear integer
programming. Ricerca Operativa 53, 3–44 (1990)[2] Frank, F., Murota, K.: A discrete convex min-max formula for box-TDI polyhedra. Mathematics of Operations Research, to appear.
[3] Murota, K.: Discrete Convex Analysis. SIAM (2003)[4] Murota, K.: On basic operations related to network
induction of discrete convex functions. Optimization
Methods and Software 36, 519–559 (2021)[5] Murota, K., Tamura, A.: Integrality of subgradientsand biconjugates of integrally convex functions. Optimization Letters 14, 195–208 (2020)[6] Schrijver, A.:
Combinatorial Optimization—
Polyhedra and Eﬃciency. Springer, Heidelberg(2003)