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

2-A-5

離散凸関数の族に関する包含・交わり関係
01606770
016031941.

東京都立大学
統計数理研究所・東京都立大学

はじめに離散関数 f : Zn → R ∪ {+∞} に対して，種々の凸性が定義されている．これらの凸性の間には，その定義から自明に包含関係が導かれるものや，離散凸解析 [3] において既知の関係がある．例えば，L♮凸関数でかつ M♮ 凸関数である関数は分離凸関数であることが知られている [3, 4]．ここで分離凸関数∑とは，Φ(x) = ni=1 φi (xi ) (ただし φi (t−1)+φi (t+1) ≥2φi (t), t ∈ Z) の形の関数である．
一方で，関係は単純ではなく，精査が必要なものもある．例として，M♮ 凸性とマルチモジュラ性の対を取り上げると，2 次元の場合，M♮ 凸関数とマルチモジュラ関数は同じことになる [1] が，一般の次元では状況は異なり，M♮ 凸関数の族とマルチモジュラ関数の族に包含関係はなく，その交わり（M♮ 凸かつマルチモジュラである関数）には分離凸関数でないものが（多数）存在する．このように，異なる離散凸性の関係は単純ではない．本研
究では，離散凸関数の諸族の包含・交わり関係を網羅的に整理する．既知の事実に本研究の結果を加えてまとめると，表１のようになる．

2.

解析の方針

本研究の目標は「離散凸関数の族の対の関係」を調べることである．そのために，離散凸解析において知られている，離散凸関数と離散凸集合の密接な関係を利用して，これを「離散凸集合の族の対の関係」に帰着する．そして，離散凸集合の凸包の不等式表現に着目して，離散凸集合の族の関係を調べる．
離散凸解析では，離散凸関数に対応する離散凸集合が標示関数を介して定義される．集合 S の標示関数を δS とすると，ある離散凸関数概念「A 凸関数」に対して，S が A 凸集合 ⇐⇒ δS が A 凸関数(1)によって「A 凸集合」の概念が定義される．このとき，関数から集合への帰着は以下の通りである．

*森口聡子
室田一雄

MORIGUCHI Satoko
MUROTA Kazuo

2 種類の離散凸関数の族の交わりが分離凸関数であるかどうかを以下のようにして調べる．分離凸関数に対応する集合は Box（整数区間 {x ∈ Zn |ai ≤ xi ≤ bi (i = 1, . . . , n)}, a, b ∈ Zn ）である．対象とする 2 種類の離散凸性を「A 凸性」と「B 凸性」と書くことにする．これについて次の自然な性質を仮定しよう．
(仮定＊) f が A 凸関数ならば，任意の p に対して
arg min f [−p] は A 凸集合．B 凸性についても同様．
補題 1 (仮定＊) のもとで，(F) A 凸関数 ＆ B 凸関数 は分離凸関数である(S) A 凸集合 ＆ B 凸集合 は Box であるの二つの命題は同値である．
以下，この補題を証明する．その際に，分離凸関数では (仮定＊) の逆も成り立つことを利用する．
補題 2f が凸拡張可能のとき，f が分離凸関数 ⇐⇒任意の p に対して arg min f [−p] は Box．
［補題 1 の証明］(F) =⇒ (S) は，(F) を集合の標示関数に適用して (1) に注意すればよい．(S) =⇒(F) は，以下のように示すことができる．

1. 関数 f : Zn → R ∪ {+∞} が A 凸関数 ＆ B 凸関数 とする．
2. (仮定＊) より，任意の p ∈ Rn に対して，集合S = arg min f [−p] は A 凸かつ B 凸である．
3. 仮定 (S) より，任意の p ∈ Rn に対して，
arg min f [−p] は Box である．
4. このことと補題 2 により， f は分離凸関数．

3. 注意すべき凸性の関係
補題 1 と離散凸集合の凸包の不等式表現により，以下のことが本研究において明らかとなった．

• L♮ 凸かつマルチモジュラである関数は分離凸関数である．
♮• さらに，L2 凸かつマルチモジュラである関数は分離凸関数である．

表 1: 離散凸関数族の関係
分離凸 整凸 L 凸
分離凸 =
⊂線形
整凸=
⊃
L凸=
L2 凸L♮ 凸L♮2 凸M凸M2 凸M♮ 凸M♮2 凸m.m.
g-dmc
d-dmc

L2 凸線形⊃⊂=L♮ 凸⊂⊃⊂
L=L♮2 凸⊂⊃⊂⊂
⊂
=

M凸一点
⊃ナシ
ナシ
一点一点=

M2 凸一点
⊃ナシ
ナシ
一点一点
⊂
=M♮ 凸⊂⊃
線形線形
分離凸分離凸⊂M=M♮2 凸⊂⊃
線形線形
分離凸分離凸⊂⊂⊂
=m.m.
⊂⊃
線形線形
分離凸 ∗分離凸 ∗△∗△∗△∗△∗=g-dmc⊂⊃⊂▽L含∗⊂△ L♮ 含 ∗▽∗▽∗△∗△∗△∗=d-dmc⊂⊃⊂▽L含⊂△ L♮ 含▽∗▽∗△∗△∗△∗=注）m.m.=マルチモジュラ，g-dmc=globally discrete midpoint convex [2], d-dmc=directed discrete midpoint
convex [5]，△:両者に包含関係はなく，交わりが分離凸関数及び分離凸以外の関数を含む，▽:両者に包含関係はなく，交わりが分離凸関数を含まないが分離凸以外の関数を含む，
包含記号：列の項目 [包含記号] 行の項目．∗ ：本研究の結果．
♮例：S = {x ∈ Z4 | x1 + x2 − x3 − x4 = 0} の標示• M 凸性や M♮ 凸性，M2 凸性，M2 凸性とマル関数 δS は L2 凸だが g-dmc（大域離散中点凸
チモジュラ性には包含関係はなく，M 凸かつ[2]）ではない． x = (1, 0, 1, 0), y = (0, 3, 3, 0)
マルチモジュラである関数は分離凸関数とはx+yとすると ∥x − y∥∞ ≥ 2 で ⌈ 2 ⌉ = (1, 2, 2, 0) <限らない．
S , ⌊ x+y
例：S = {x ∈ Z3 | 0 ≤ xi ≤ 3 (i = 1, 2, 3),
2 ⌋ = (0, 1, 2, 0) < S となる．ゆえに，δS♮♮は g-dmc でない．ここで L2 ⊃ L2 だから, L2 \x1 + x2 ≤ 5, x2 + x3 ≤ 5, x1 + x2 + x3 = 6}
g-dmc , ∅ でもある. また，T = {(1, 0), (0, 1)}= {303, 123, 321, 132, 231} ∪ {213, 222, 312} (前♮の標示関数は g-dmc だが，L2 凸でも L2 凸での５点が端点) は，マルチモジュラかつ Mもない．
凸 になっている．まず，M 凸集合であることは多面体表現から明らか．次に，変数変換
謝辞：本研究は JSPS/MEXT 科研費 (JP20K11697,y1 = x1 , y2 = x1 + x2 , y3 = x1 + x2 + x3 にJP17K00037, JP21K04533) の助成を受けた．
よって，S = {x} を T = {y} に変換すると，
参考文献
T = {336, 136, 356, 146, 256} ∪ {236, 246, 346}
[1] Moriguchi, S., Murota, K.: On fundamental opera(前の５点が端点) となる．すべての点で y3 = 6
tions for multimodular functions. Journal of the Operations Research Society of Japan 62, 53–63 (2019)であり，(y1 , y2 ) をプロットすると• •• • •• • •[2] Moriguchi, S., Murota, K., Tamura, A., Tardella, F.:
Discrete midpoint convexity. Mathematics of Operations Research, 45, 99–128 (2020)のようになり，T は L♮ 凸集合である．したがっ [3] Murota, K.: Discrete Convex Analysis. SIAM (2003)て，S はマルチモジュラ集合である．この例[4] Murota, K., Shioura, A.: Relationship of M-/L-convex
functions with discrete convex functions by Millerの構成法から，マルチモジュラ かつ M 凸であand by Favati–Tardella. Discrete Applied Mathematる集合は Box でないものがたくさんあること
ics 115, 151–176 (2001)が分かる．したがって，マルチモジュラ かつ[5] Tamura, A., Tsurumi, K.: Directed discrete midpoint
M2 凸である Box でない集合もたくさんある．
convexity. Japan Journal of Industrial and Applied• 離散中点凸性は L♮ 凸性を包含する概念である♮が，L2 凸性や L2 凸性と包含関係はない．

Mathematics 38, 1–37 (2021)