2023 年 2 月 11 日更新

室田 一雄：「離散凸解析」 共立出版 の訂正と補足
誤り等を見つけた方はお知らせくだされば有難く存じます．

1

初版 (第１〜４刷) の共通項目• 80 頁 −1 行, 命題 3.6 の証明の最後「(B-EXC+ [Z]) の対偶により」という書き方が分かりにくいという指摘がありました．
「y ∈ B, y + χu∗ − χv ̸∈ B, y + χu∗ − χv0 ̸∈ B なので，y ′′ ∈ B だとすると(B-EXC+ [Z]) に矛盾する」と書いた方が分かりよかったかもしれません．
• 91 頁: 定理 3.17(2) の証明では次の命題を用いている．
命題: P を有理多面体 (⊆ Rn ) とするとき，P のすべての極小面が整数ベクトルを含むならば，P に含まれる整数ベクトルの凸包 PI = P ∩ Zn は P に一致する．
以下，補足説明を与える．この命題において，有理多面体という条件は必要であ√る．例えば，P = {(x1 , x2 ) | x1 − 2x2 ≥ 0} とすると，P は唯一の極小面 F =√{(x1 , x2 ) | x1 − 2x2 = 0} をもち，F は整数ベクトル (0, 0) を含む．しかし，PI =√{(0, 0)} ∪ {(x1 , x2 ) | x1 − 2x2 > 0} となり，P に一致しない（そもそも PI は多面体ですらない）．
一方，P が有理多面体のときには，PI は多面体になることが知られている．また，任意のベクトル c ∈ Rn に対して，max{⟨c, x⟩ | x ∈ PI } が有界 =⇒ max{⟨c, x⟩ | x ∈ P } が有界(E1)が成り立つ．なお，この二つの事実については，B. Korte and J. Vygen: Combinatorial
Optimization: Theory and Algorithms, Springer-Verlag, Berlin, 2000; 3rd ed., 2006;
4th ed., 2008, の Theorem 5.7 と Proposition 5.1 に証明とともに記述があります．
命題の証明 背理法で証明するために，仮に PI が P に一致しないとすると，あるy ∈ P \ PI が存在する．このとき，あるベクトル a ∈ Rn と実数 β が存在して，⟨a, y⟩ > β かつ ⟨a, x⟩ ≤ β (∀x ∈ PI ) が成り立つ．
［細かいことを言えば，(a, β) の存在を主張する際に，PI が多面体（したがって閉集合）であることを使っている．
］したがって，max{⟨a, x⟩ | x ∈ P } ≥ ⟨a, y⟩ > β,max{⟨a, x⟩ | x ∈ PI } ≤ βである．式 (E1) より，線形計画問題

max{⟨a, x⟩ | x ∈ P }1(E2)は有界であるから，最適解をもつ．最適解の全体 F は P の面を成すので，仮定より，F は整数ベクトルを含む（F に含まれる極小面が整数ベクトルを含むから）．しかし，これは式 (E2) に矛盾する．これで，命題の証明ができたことになる．

• 118 頁 定理 4.8 (8) ［M 凸関数の合成積が M 凸関数であること］
ここではネットワークによる変換を利用した証明になっていますが，より直接的な証
明が K. Murota: On infimal convolution of M-convex functions, 京都大学数理解
析研究所 講究録, No.1371 (2004), 20–26,
http://www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2004/METR04-12.pdfにあります．
• 121 頁 補足 4.14
条件 (4.41) は冗長で，条件 (4.40) から導かれます．
• 137 頁 補足 4.42
［整多面体的 M 凸関数 f ∈ M[Z|R → R] に対しては α0 = 1 とできる］ の証明．
任意の x, y ∈ dom f と u ∈ supp+ (x − y) に対して，ある v ∈ supp− (x − y) が存在
して，十分小さなすべての α > 0 に対して，不等式

f (x) + f (y) ≥ f (x − α(χu − χv )) + f (y + α(χu − χv ))(4.61)が成り立つ．定義域 dom f は f が線形（アフィン）であるような領域に分割されているが，それらの領域はすべて整数基多面体である．十分小さな α̂ > 0 に対して，x̂ ≡ x− α̂(χu −χv ) を相対的内点とする最小の基多面体を Bx とし, ŷ ≡ y + α̂(χu −χv )を相対的内点とする最小の基多面体を By とする．Bx , By はともに整基多面体であり，整基多面体においては交換容量 (exchange capacity) は整数だから [Fujishige [40]の (2.38) 式参照]，x − α̂(χu − χv ) ∈ Bx より x′ ≡ x − (χu − χv ) ∈ Bx が導かれ，y + α̂(χu − χv ) ∈ By より y ′ ≡ y + (χu − χv ) ∈ By が導かれる. f は Bx , By のそれぞれの上で線形だから x − β(χu − χv ) ∈ Bx , y + β(χu − χv ) ∈ By である任意の β に対して
f (x − β(χu − χv )) − f (x) = (β/α̂)[f (x − α̂(χu − χv )) − f (x)],f (y + β(χu − χv )) − f (y) = (β/α̂)[f (y + α̂(χu − χv )) − f (y)].
ここで β = 1 として両者を加えると

f (x′ ) + f (y ′ ) − f (x) − f (y) = (1/α̂)[f (x̂) + f (ŷ) − f (x) − f (y)]となるが，この右辺は (4.61) で α = α̂ としたものであるから，右辺 ≤ 0. したがって(4.61) が α = 1 で成り立つ．

• 145 頁 −9 行, 式 (5.4) の上「g̃ に対する条件 (5.2) において r = 0 となるように g̃ を選ぶことができる」の理由を説明します．
2L♮ 凸関数 g : ZV → R ∪ {+∞} に対して，g(p) = h(0, p) となる L 凸関数 h : ZṼ →R ∪ {+∞} が存在する．L 凸関数の定義より，ある r = rh ∈ R が存在して，任意の(p0 , p) ∈ Ṽ に対して
h(p0 + 1, p + 1) = h(p0 , p) + rが成り立つ．この h と r を用いて，関数 g̃ : ZṼ → R ∪ {+∞} をg̃(p0 , p) = h(p0 , p) − rp0((p0 , p) ∈ Ṽ )と定義する．g̃ は，L 凸関数 h と線形関数 rp0 = ⟨(r, 0), (p0 , p)⟩ の和であるから，劣モジュラである．さらに，

g̃(p0 +1, p+1) = h(p0 +1, p+1)−r(p0 +1) = (h(p0 , p)+r)−r(p0 +1) = h(p0 , p)−rp0 = g̃(p0 , p)となる．したがって，g̃ は L 凸関数であって，1 方向の線形性 (5.2) を r = 0 で満たす．

• 152 頁 定理 5.12（L 凸関数最小性規準）
ここでは整凸関数の最小性規準を利用した証明になっていますが，より直接的な証明
が K: Murota: A proof of the L-optimality criterion theorem, unpublished note,
July 2004, http://www.comp.tmu.ac.jp/kzmurota/paper/loptimality04.pdfにあります．
• 155 頁 定理 5.16（L 凸関数の凸拡張）の証明の解説：証明中 (156 頁) のこの構成法から h は各 p ∈ ZV に対して単位超立方体 [p, p + 1]R 上で凸関数であるが，実は，RV 全域で凸である．なぜなら，(5.2) からh(q − α1) = h(q) − αr(q ∈ RV , α ∈ R)

(5.24)

が成り立ち，各 q ∈ RV に対して，ある α ∈ R と p ∈ ZV が存在して，q − α1 は [p, p + 1]R の内点となるからである．
について論理の詳細を説明します．基本となる事実は，「凸集合上で定義された（連続変数の）関数の凸性は局所凸性と同値」という事実で，これを関数 h に適用しています．まず，関数 h の実効定義域は L 凸多面体になるので，凸集合であることに注意します．したがって，
命題 A：任意の q ∈ RV に対して，q のある凸開近傍 W が存在して，関数h は W 上で凸であるを示せば，h の凸性が証明されます．証明中に書いてあるように，(LOV) h は各単位超立方体の内部では (劣モジュラ関数の Lovász 拡張だから) 凸関数，(BND) h は各単位超立方体の境界では連続 (well-defined)3

です．したがって，命題 A における q が単位超立方体の境界にある場合が問題となります．
命題 A の証明
q の十分小さい開近傍

W = {t ∈ RV | ∥t − q∥∞ < ε}を考える（ただし，ε は十分小さい正の数）．

p+1WYWαY

pqq − α1

α = 2ε とおくと，Wα = W − α1 は，一つの単位超立方体の内部にある．したがって，(LOV) により，h は Wα 上で凸関数である．一方，(5.24) より
h(t) = h(t − α1) + αr(t ∈ W )である．t ∈ W のとき t − α1 ∈ Wα であるから，h は W 上で凸である（αr は定数なので凸性には影響しない）．

• 186 頁 定理 6.14（M 凸交わり定理）
ここでは M 分離定理を利用した証明になっていますが，より直接的な証明が K.
Murota: A proof of the M-convex intersection theorem, 京都大学数理解析研究所 講究録, No.1371 (2004), 13–19,
http://www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2004/METR04-03.pdfにあります．その証明は，田村明久：離散凸解析とゲーム理論，朝倉書店，2009 の2.7 節に分かりやすく (日本語で) 紹介されています．
• 195 頁 定理 6.31 の証明 第 1 段落の「L2 凸」(3 箇所) を「L♮2 凸」に変えて，最後に「そのためには，L2 凸集合が整凸集合であることを示せばよい．
」を追加してくだ
さい．訂正後の文章は以下の通りです：♮

実効定義域が有界な L2 凸関数 g に対して示せばよい．このとき，定理 2.49 が適用で♮きるが，任意の x ∈ RV に対して g[−x] が L2 凸関数であることと命題 6.30 により，L♮2 凸集合が整凸集合であることを示せばよいことになる．そのためには，L2 凸集合が整凸集合であることを示せばよい．
♮

なお，L2 凸集合（L2 凸集合）が整凸集合であることは，その不等式表現が box-TDIであること（S. Moriguchi and K. Murota: Note on the polyhedral description of4

the Minkowski sum of two L-convex sets, Japan Journal of Industrial and Applied
Mathematics, Vol.40 (2023), No.1, 223–263. https://doi.org/10.1007/s13160-02200512-3 (Open access) の Theorem 5.1）からも分かります．
• 268, 269 頁 「非補完性」は「無補完性」，「強非補完性」は「強無補完性」の方が自然な日本語と思いますので，そのように変更してください．
• 270 頁 「Ũ の強非補完性 (SNC) =⇒ U の M♮ 凹性」
この命題の逆も成立すること，すなわちŨ の強非補完性 (SNC) ⇐⇒ U の M♮ 凹性が成り立つことが示されています (K. Murota: Multiple exchange property for M♮ concave functions and valuated matroids, Mathematics of Operations Research,
Vol. 43 (2018), No. 3, pp. 781-788).

• 286 頁 [69]

13 (2002), 204–211.

5

2

初版 1 刷 (2001)〜3 刷 (2010) に該当する項目（４刷 (2015) では訂正済)• 20 頁 18 行
誤: f ′ (x; ·) : Rn → R∪{+∞}=⇒

正:f ′ (x; ·) : Rn → R∪{+∞, −∞}• 91 頁 2 行（定理 3.17(1) の証明中）
誤：ỹ も整数ベクトルである．
=⇒ 正：整数ベクトルの最適解 ỹ が存在する．
なお，最適解の全体に含まれる任意の極小面に着目すると，その中に ỹ が存在することが分かります．

• 91 頁 8 ∼ 13 行: 定理 3.17(2) の証明に不備があることを九州大学 川崎英文教授にご指摘頂きました．下の証明に入れ替えてください．
=⇒(2) 問題 (A) の実行可能領域の極小な面 F に着目し，F が最適解の全体に一致する
p ∈ (ZV を考える．縦ベクトルρ̃1 , ρ̃2 を ρ̃i = (ρi (X) | X ∈ Ti ) (i = 1, 2) と定義し，)ρ̃ =ρ̃1
ρ̃2とおく．線形計画の相補性（定理 2.12(3)）により，問題 (A) の実行可能解x が最適解であるためには Ax = ρ̃ を満たすことが必要十分である．このことと F が極小面（したがってアフィン部分空間）であることにより，F = {x ∈ RV | Ax = ρ̃}となる．係数行列 A は完全単模であるから，ρ̃ が整数ベクトルならば Ax = ρ̃ を満たす整数ベクトル x が存在する．すなわち，F は整数ベクトルを含む．一般に，有理多面体（有理数係数の不等式で記述される多面体）のすべての極小面が整数ベクトルを含むならば，その多面体に含まれる整数ベクトルの凸包は元の多面体に一致する（[132] A. Schrijver: Theory of Linear and Integer Programming, 1986 の 16.3 節参照）．したがって，(2) が成り立つ．
上に述べた基本事実を命題として述べ，説明を追加する．
命題: P を有理多面体 (⊆ Rn ) とするとき，P のすべての極小面が整数ベクトルを含むならば，P に含まれる整数ベクトルの凸包 PI = P ∩ Zn は P に一致する．
√
ここで有理多面体という条件は必要である．例えば，P = {(x1 , x2 ) | x1 − 2x2 ≥ 0}√とすると，P は唯一の極小面 F = {(x1 , x2 ) | x1 − 2x2 = 0} をもち，F は整数ベク√
トル (0, 0) を含む．しかし，PI = {(0, 0)} ∪ {(x1 , x2 ) | x1 − 2x2 > 0} となり，P に一致しない（そもそも PI は多面体ですらない）．
一方，P が有理多面体のときには，PI は多面体になることが知られている．また，任意のベクトル c ∈ Rn に対して，

max{⟨c, x⟩ | x ∈ PI } が有界 =⇒ max{⟨c, x⟩ | x ∈ P } が有界
6(E1)が成り立つ．なお，この二つの事実については，B. Korte and J. Vygen: CombinatorialOptimization: Theory and Algorithms, Springer-Verlag, Berlin, 2000; 3rd ed., 2006;
4th ed., 2008, の Theorem 5.7 と Proposition 5.1 に証明とともに記述があります．
命題の証明 背理法で証明するために，仮に PI が P に一致しないとすると，あるy ∈ P \ PI が存在する．このとき，あるベクトル a ∈ Rn と実数 β が存在して，⟨a, y⟩ > β かつ ⟨a, x⟩ ≤ β (∀x ∈ PI ) が成り立つ．
［細かいことを言えば，(a, β) の存在を主張する際に，PI が多面体（したがって閉集合）であることを使っている．
］したがって，max{⟨a, x⟩ | x ∈ P } ≥ ⟨a, y⟩ > β,max{⟨a, x⟩ | x ∈ PI } ≤ β(E2)である．式 (E1) より，線形計画問題

max{⟨a, x⟩ | x ∈ P }は有界であるから，最適解をもつ．最適解の全体 F は P の面を成すので，仮定より，
F は整数ベクトルを含む（F に含まれる極小面が整数ベクトルを含むから）．しかし，これは式 (E2) に矛盾する．これで，命題の証明ができたことになる．

• 奥付 著者紹介 著書「数値計算法の整理」=⇒ 「数値計算法の数理」

7

3

初版 1 刷 (2001), 2 刷 (2003) に該当する項目（3 刷 (2010) 以降では訂正済)• 82 頁 7 行

誤: 4 min(λj , λk )• 82 頁 9 行

誤: 4/N

=⇒

正: 2 min(λj , λk )=⇒正: 2/N• 126 頁 定理 4.20 の証明
B が M 凸多面体であることから，B が M 凸集合であることを導くには，B に穴がないことを示しておく必要がある（多少面倒であるが，それは可能である）．
• 233 頁 9 行 誤：Du = {v ∈ V | (u, v) ∈ Ax }=⇒正: Du = {v ∈ V | (v, u) ∈ Ax }• 284 頁 [40] 追加情報：2nd ed., Annals of Discrete Mathematics, 58, Elsevier, 2005.
• 284 頁 [41]to appear.

=⇒ 280 (2004), 13–27.

• 284 頁 [44]to appear.

=⇒ 28 (2003), 463–469.

• 287 頁 [73]to appear.

=⇒ 131 (2003), 433–448.

• 289 頁 [109]to appear.

=⇒ 131 (2003), 467–494.

• 290 頁 [110]RIMS Preprint 1326, Kyoto University, July 2001.
=⇒ Advances in Applied Mathematics, 33 (2004), 318–341.
• 290 頁 [112]to appear.

=⇒ 131 (2003), 495–512.

• 290 頁 [113]

to appear.

=⇒ 20 (2003), 257–277.

• 293 頁 [153]
RIMS Preprint 1401, Kyoto University, February 2003.
=⇒ Discrete Applied Mathematics, 154 (2006), 950–970.
• 293 頁 [154]
METR 2003-23, University of Tokyo, July, 2003.
=⇒ Japan Journal of Industrial and Applied Mathematics, 21 (2004), 391–403.
• 293 頁 [157]

to appear.

=⇒ 14 (2003), 699–707.

• 293 頁 [158]to appear.

=⇒ 101 (2004), 415–433.

• 293 頁 [159]
RIMS Preprint 1382, Kyoto University, October 2002.
=⇒ Discrete Optimization, 2 (2005), 256–268.
• 293 頁 [160]to appear.

• 294 頁 [162]追加情報：Mathematical Programming, 102 (2005), 339–354.

=⇒ 134 (2003), 303–316.

8

4

初版第 1 刷 (2001) のみ該当する項目（第 2 刷 (2003) 以降では訂正済)• 28 頁 6 行(2.45) の上：

誤：n 次元ベクトル b=⇒

正：m 次元ベクトル b

誤：m 次元ベクトル c=⇒

正：n 次元ベクトル c• 53 頁 9, 10 行 誤：p, q• 53 頁 16 行

誤: g(η∨ ) + g(η∧ )• 115 頁 5 行

誤：（4.8）• 145 頁 定理 5.1• 177 頁 5 行

正：p̃, q̃=⇒

正：(4.9)=⇒g ≡ +∞ も含める

脚注：

誤: ∂R g(p0 ) は整 M 凸多面体である• 177 頁 8 行

正: g(p ∨ q) + g(p ∧ q)=⇒誤：複合同順

正: ∂R g(p0 ) は整 M♮ 凸多面体である=⇒

正：複号同順=⇒• 195 頁 7 行 命題 6.30 の証明: argmin = argmin + argmin が成り立つためには g1 ,g2 をうまく選んでおく必要がある．詳しくは，A. Tamura: On convolution of Lconvex functions, Optimization Methods and Software, 18 (2003), 231–245, あるいは A. Tamura: Deconvolution of an L2 -convex function, RIMS Preprint 1369, Kyoto
University, July 2002 を参照のこと．
• 196 頁 定理 6.32: Z → R 型の場合には，g1 , g2 を取り直す必要がある．詳しく
は，A. Tamura: On convolution of L-convex functions, Optimization Methods andSoftware, 18 (2003), 231–245, あるいは A. Tamura: Deconvolution of an L2 -convexfunction, RIMS Preprint 1369, Kyoto University, July 2002 を参照のこと．
• 197 頁 5 行

誤： M0 [Z|R]

定理 6.32 の証明の最後:=⇒♮

正：M0 [Z|R]• 204 頁 −6 行 式 (7.27)： x(V ) = 0 が抜けている• 216 頁 10 行 式 (7.61) の３行目

誤: ∆f (x; v, u)• 239 頁 6 行=⇒誤：のアルゴリズムを• 239 頁 −2 行 L♮ 凸関数 g の最小化 (降下法)
誤: g(p) = g(p + αχX ) ならば=⇒正: ∆f (∂ξ; v, u)

正：のアルゴリズムの原形をの S2:
正: g(p) ≤ g(p + αχX ) ならば• 239 頁 −2 行 L♮ 凸関数 g の最小化 (降下法) の S3:
誤: p := p + χX=⇒
正: p := p + αχX9=⇒• 250 頁 命題 8.13 の証明（1）下から３行目 誤: (8.32) が保持される
下から２行目 誤: (8.33) が保持される• 274 頁，例 9.12 の直前の行• 274 頁，例 9.12 の１行目=⇒=⇒

正: (8.32), (8.33) が保持される
正: 条件が保持される

誤: 前節

=⇒

正: 第２節誤: （前節）=⇒正: （第２節）• 284 頁 [44]preprint, 2000.
(2003), 463–469.

=⇒ Mathematics of Operations Research, 28• 286 頁 [67]to appear.

=⇒ 84 (2002), 203–212.

• 286 頁 [68]to appear.

=⇒ 48 (2001), 761–777.

• 286 頁 [69]to appear.

=⇒ 13 (2002), 204–211.

287 頁 [73]Discrete Mathematics and Systems Science Research Report, No.
00-10, Division of Systems Science, Osaka University, July 2000.
=⇒ Discrete
Applied Mathematics, 131 (2003), 433–448.
• 289 頁 [108]to appear.

=⇒ 115 (2001), 151–176.

• 289 頁 [109]RIMS Preprint 1306, Kyoto University, December 2000.
Discrete Applied Mathematics, 131 (2003), 467–494.

=⇒• 290 頁 [113]Computation of competitive equilibria of indivisible commodities via
M-convex submodular flow problem, RIMS Preprint 1316, Kyoto University, March2001. =⇒ Application of M-convex submodular flow problem to mathematical
economics, Japan Journal of Industrial and Applied Mathematics, 20 (2003), 257–277.
• 291 頁 [121]鈴木=⇒鈴村(以上)

10