おわりに本書の第 I 部では，M♮ 凹集合関数を主役に据えて，経済学的概念との対応を示しながら，集合関数に対する離散凸解析を概観した．付値マトロイドに関する基本的な事実（室田 [218, 第 5 章], 2000 年）を M♮ 凹集合関数の性質に翻訳して記述し，その後に得られた結果（選択関数の代替性，多重交換不等式，マトロイド階数関数の最大最小定理，GS 関数の構成法など）を含めた．
第 II 部では，Zn 上の離散凸解析の理論を，近年の進展を含めて記述した．離散凸解析を体系的に記述した著書に，室田 [219] (2001 年，和文)，[220] (2003 年，英文)がある．藤重 [81, 第 VII 章] (2005 年）は，多面体的な観点から理論の主要部を再構築している．室田 [224] (2007 年)（および室田 [225]）は，離散と連続という一般的な視点から，離散凸解析の位置づけを論じている．2010 年以降の進展を記述したサーベイ論文として，室田 [230, 231]，森口・室田 [204]，室田・田村 [257] などがあるが，これらの内容も本書の第 II 部に反映した．アルゴリズムは離散凸解析において重要な要素であるが，本書では詳しく論じる余裕がなかった．基本的な結果については，室田 [219, 220] に記述がある．室田・塩浦 [239] は，アルゴリズムに焦点をあてて離散凸解析を紹介した教科書である．アルゴリズムに関する最近の進展については，補足 9.6，補足 9.15 に手短に記述した．
第 III 部では，経済学への応用を述べた18 ．離散凸解析は，経済学以外にもいろいろな分野に応用される．そのいくつかを以下に紹介する19 ．
離散不動点定理

通常の不動点定理は，写像の連続性と定義域の形に関する適当な仮定の下で不動点の存在を保証する．離散凸解析においては，整凸集合上の方向保存写像に対して離散不動点定理が成り立つ．方向保存性は，Zn の部分集合 S からそれ

18 室田 [227] は，経済学への応用とそれに必要な理論に焦点を絞ったサーベイ論文である．
19 有限距離空間（系統樹）や行列和の固有値への応用もある．室田 [224, 225] を参照されたい．

278

おわりに自身への写像（対応）に対する一種の連続性の概念である．詳細は飯村・室田・田村[134] を参照されたい（室田 [224, 第 12 章], [225, 227] にも解説がある）．これを契機として，離散相補性問題や経済学・ゲーム理論への応用などの研究が飯村，渡辺，Yang らによって行われた [133, 135, 136, 330, 331]．
混雑ゲーム

ネットワーク（道路網）における経路選択などの問題は，混雑ゲームとよばれる非協力ゲームで表現される．混雑ゲームでは，Nash 均衡がポテンシャルと20よばれる関数の最小化によって与えられる（Rosenthal [277]）．Nash 均衡はある種の「局所最適解」と捉えられるので，「ポテンシャル最小 ⇒ Nash 均衡」は「大域最適 ⇒ 局所最適」にあたる．「ポテンシャル最小 ⇔ Nash 均衡」が成り立つようなポテンシャル関数の離散凸条件が宇井 [324] によって考察されている．藤重ら [83] は，延長・並列ネットワーク上の混雑ゲームについて，ポテンシャル関数が M 凸関数であることを指摘し，そのことから，n 人のゲームでは最適反応を n 回繰り返すことで純粋 Nash 均衡に到達するという Fotakis [65] の結果が導かれることを示した．
オペレーションズ・リサーチ

在庫管理などのマルコフ決定過程を中心として，オペレーションズ・リサーチ（OR）の分野においても，離散凸解析は様々な問題に応用されている．在庫管理の分野では，離散凸関数という視点が既に 1971 年の Miller [197]に現れているが，本書の意味での離散凸解析の応用は，2005 年の Lu・Song [182] を嚆矢とし，2008 年の Zipkin [338] を経て広まった21 ．離散凸解析の概念（L♮ 凸関数，M♮ 凸関数）とその性質を用いて新たな問題が扱えるようになるだけでなく，古典的な結果に対して見通しのよい証明が得られる．Chen [34]，Chen・Li [35, 36] は，OR諸問題への応用に関する詳細なサーベイである．Simchi-Levi・Chen・Bramel の教科書 [298, 第 2.3 節] にも，L♮ 凸関数と M♮ 凸関数についての解説がある．

Lorentz 多項式 関数値の対数が凹関数となるような関数は，対数的凹関数とよばれ，確率論を始めとして数学のいろいろな分野で重要な役割を果たしている（Saumard・Wellner [281]）．1 変数多項式については，関数値の対数的凹性と係数の対数的凹性が密接に関係するという興味深い事実が知られていたが，2020 年にBrändén・Huh [32] によって Lorentz（ローレンツ）多項式の理論が構築され，多20 ポテンシャルが費用に対応すると考えて最小化としたが，利得に対応する場合は最大化となる．
（戦略が有限の）任意のポテンシャルゲームは，混雑ゲームとして定式化できる（Monderer・Shapley [200]）．
21 Miller [197] の扱った関数は，実は，L♮ 凸関数である（室田 [224, 第 14.7 節]）．Lu・Song [182, 命題1(c)] には「平均費用を表す関数 C(s) は L♮ 凸関数である」と述べられているが，これには反例がある（Bolandnazar・Huh・McCormick・室田 [27]）．

279

変数多項式に対して，同様の関係が（M 凹性の概念を使って）示された22 ．Lorentz多項式の定義はやや複雑であるが，斉次多項式の場合には「f (w) が Lorentz 多項式⇔ f 自身および f の任意階数の導関数が正象限 (w > 0) で対数的凹関数」が成り立つ．とくに，（斉次）Lorentz 多項式は対数的凹関数である．Lorentz 多項式の例には，Tutte 多項式（Welsh [326]）や体積多項式がある23 ．一般に，n 変数斉次多項式をf (w) =

∑αcαwα,α!

wαwα1 w2α2wαn:= 1··· nα!
α1 ! α2 !
αn !の形に表現する．ここで，w = (w1 , . . . , wn ), α = (α1 , . . . , αn )，各 αi は非負整数，∑n，cα は正規化された係数で，cα ≥ 0 と仮定する．このi=1 αi = d（多項式の次数）とき「log cα が（α を変数とする）M 凹関数 ⇒f (w) は Lorentz 多項式」という定理が成り立つ [32, 系 3.16]．さらに「M ⇔ Lorentz」の形の次の定理も知られている[32, 定理 3.14]：与えられた関数 ν : Zn+ → R に対して，q をパラメータ (0 < q ≤ 1)とする関数

fqν (w) =∑α∈dom (ν)

q ν(α)wαα!

（ν の指数型母関数）を定義すると，「ν が M 凸関数 ⇔ 任意の q (0 < q ≤ 1) に対してfqν が Lorentz 多項式」が成り立つ．ここで cα = q ν(α) とおくと，log cα = ν(α) log qで log q ≤ 0 であるから，ν(α) の M 凸性は log cα の M 凹性に対応する．
本書では，整凸関数，M♮ 凸関数，L♮ 凸関数を中心として，表 6.1 に示した種類の離散凸関数を扱った．上に述べた応用は，すべてこの範疇の離散凸関数に関するものである．以下では，離散凸関数の概念の拡張によって離散凸解析の応用範囲が拡大した例を述べる．
ジャンプシステム 第 4 章にも述べたように，二部グラフ上のマッチングは M 凸集合や M 凸関数と密接な関係をもつ．より一般の（二部グラフとは限らない）グラフ上のマッチングの離散凸性はジャンプシステム（Bouchet・Cunningham [31]）として抽出されるが，その上の関数にも M 凸関数の概念は拡張される（室田 [223, 232]）．ジャンプシステム上の M 凸関数の最小化元は，最急降下法によって求められる（室田 [223]，

22 June Huh は，組合せ論的 Hodge 理論とよばれる手法を構築して多くの未解決問題を解決したことにより，2022 年の Fields 賞を受賞している．Lorentz 多項式の理論もその一部である．詳しくは，Huh[130] および Kalai [154] を参照されたい．
23 Rd の凸体（コンパクトな非空凸集合）C (i = 1, . . . , n) に対して，各 C を w (≥ 0) 倍した集合のiii
Minkowski 和の体積 f (w) = vol(w1 C1 + · · · + wn Cn ) は (w1 , . . . , wn ) の多項式になることが知られており，体積多項式 (volume polynomial) とよばれる（Schneider [282]）．

おわりに280

塩浦・田中 [296]，南川 [198]）．ネットワークによる変換（第 8.7 節）などの演算も定義される（小林・室田・田中 [167]，小林・室田 [166], 室田 [230, 231]）が，共役性定理やFenchel 型双対定理は成り立たない．ジャンプシステム上の M 凸関数は，マッチング問題とその拡張の解析に利用される（小林，高澤ら [22, 163, 164, 168, 169, 307]）．
グラフ上の L 凸関数

ネットワークフローの問題は，組合せ最適化の中では扱いやすい問題であり，離散凸解析とも相性がよい（室田 [219, 第 2.3 節 & 第 7 章], [220,第 2.2 節 & 第 9 章]）．しかし，多品種フローになると格段に難しくなり，本書の第 II 部で述べた概念や定理では手に負えなくなる．多品種フロー問題を扱える形に進化した離散凸解析（L 凸関数の理論）が，2010 年以降の平井による一連の研究[106, 107, 108, 109, 110, 111, 113, 114] によって構築された（解説論文 [112] も参照）．この意味の L 凸関数をグラフ上の L 凸関数とよぶ．以下に要点を述べる．

• 定義域は，木（ツリー）の直積，ユークリッドビルディング，向き付け可能モジュラグラフなど，Zn より一般的な離散構造である．

• 定義域が木の直積やユークリッドビルディングの場合には，離散中点凸性に相当する不等式が定式化でき，これによって L 凸関数を定義することができる．

• より一般に，向き付け可能モジュラグラフ上に定義された関数に対する L 凸性は，各点の近傍（モジュラ半束）における劣モジュラ性によって定義される．

• 最小化に関する最適性条件は，定理 9.12 と同様の形で与えられる．
• 最急降下法（第 9.1.4 節）と同様の最小化アルゴリズムが動く．反復回数についても，定理 9.14 と類似の定理が成り立つ．

• 本書で扱った L♮ 凸関数は，Zn ,→ Rn という自然な埋め込みによって，Rn 上の凸関数に拡張されるが，グラフ上の L 凸関数の多くは CAT(0) 空間上の凸関数に拡張される．これによって連続緩和型のアルゴリズムが設計できる．
多品種フローの後続研究に，平井・池田 [116, 118] がある．グラフ上の L 凸関数の枠組みは，モジュラ束上の劣モジュラ関数最小化を扱えるので，非可換ランク，作用素スケーリングなど，代数的な最適化問題（最適な線形部分空間を求める問題）にも利用される（濱田・平井 [98]，平井 [115]，平井・池田 [117]，平井・岩政・大城・相馬 [120]）．
謝辞

本書の原稿を通読して詳細なチェックをして下さった田村明久氏，塩浦昭義氏，森口聡子氏，横井優氏に感謝する．小島武仁氏を代表者とする「ERATO 小島
マーケットデザインプロジェクト」(JST ERATO JPMJER2301) への参加は本書の執筆にも有意義であった．丸善出版の三崎一朗氏には終始お世話になった．