数理解析研究所講究録1020 巻 1997 年 72-84

72

離散凸解析 (Discrete Convex Analysis)
京都大学数理解析研究所1

室田-雄 (Kazuo Murota)

はじめに
連続変数に関する最適化の分野では, 凸解析的なコアとなっている [13, 17, 38, 39].

–

項関数の理論–がその理論

その-番簡単で有用な例が, 線形計画の双対定理である. 他方, 離散変数に関する最適化 (組合せ最適化) の分野を見てみると, 凸解析のような統- 的な視点は存在しない. しかし, マトロイド$(\mathrm{L}\mathrm{P})$

ネットワークフロー問題や最小木問題に共通する組合せ構造
良い性質と認知されている [10, 16, 19].

的な構造

–

–

が

ここで解説する 「離散凸解析」 は, 凸解析とマトロイド理論の両方の視点か
ら最適化の世界を眺めようとする試みである. 連続の側から見るとマトロイド性をもつ凸関数 $f$ :散関数 $f$ :論 $+$$\mathrm{R}^{n}arrow \mathrm{R}$の理論であり, 離散の側から見ると凸性をもつ離の理論といえる. 標語的には, 「離散凸解析 $=$ マトロイド理
凸解析」である. さらにより -般的には, 「凸性 $+$ 組合せ論」 という数理$\mathrm{Z}^{n}arrow \mathrm{Z}$的構造を考察するのが「離散凸解析」 の主題である.
組合せ最適化の分野においては, 既に 60 年代の終わりからマトロイド性と自性との類似性が (漠然とした形で) 議論されていた. 実際, 両者は次の 2 点で似ている.
$\bullet$$\bullet$

局所最適条件が大域的最適性を特徴づける. したがって, 局所的な降下法によって最適化が達成される.
最大・最小定理のような双対性が成り立つ. 、これによって, 双対変数を利淫した算法が構成できる.

Frank [7], 藤重 $[8, 9]$ , Lov\’asz [20] らの研究により, . マ
トロイド性と凸性の関係が明確になった. その結果, 現在では, 「マトロイドの80 年代はじめになると,$\cdot$双対性 $=$ 陣解析における双対性 $+$ 整数性」 という図式が広く受け入れられている.

実は, 「凸性 $+$ 組合せ論」 という数理的構造は, マトロイドというような抽象的な枠組み以前に, 非線形抵抗から成る電気回路として実在している. 例えば, 伊理 [14] は, 凸解析とネットワークフロー理論の黎明期において既にその方向性を示しているし,

Rockafellar [40] は, 精密な凸解析の理論を踏まえて,

有向マトロイド的な組合せ構造と凸解析の接点を論じている.
通常の凸解析では集合や関数の凸性を議論するが, 「離散凸解析」 では凸性の上に互いに共役な 2 種類の組合せ構造を区別し, それらを$\mathrm{M}$凸性,$\mathrm{L}$

凸性と

73

表 1: 歴史 (マトロイド性と凸性)

凸集合があり,なお, この用語によれば, 80 年代の呼ぶ. すなわち, 「離散凸解析」 で扱う凸集合には
凸関数には
議論は

$\mathrm{M}$$.\mathrm{M}$凸関数と$\mathrm{L}$

凸関数がある.

凸集合の話であると位置づけられる.

$\mathrm{M}$凸集合と$\mathrm{L}$

表 1 に, マトロイド研究の歴史のなかで凸性と関係する出来事を抜きだして, この分野が進展してきた時間ス
ケールを示してみた.

74$v=f(x1$

図 1: 分離定理

2離散凸解析に向けて

2.1

凸解析の基本事項

非線形計画問題は通常
関数 $f$ :$\mathrm{R}^{n}arrow \mathrm{R}$$\mathrm{r}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{Z}\mathrm{e}f(x)$は目的関数, 集合

subject to$D\subseteq \mathrm{R}^{n}$$x\in D$ 」 の形に書かれ,は実行可能領域と呼ばれる. とくに, $D$ が凸集合, $f$ が凸関数のときは凸計画問題と呼ばれ, 理論的にも実際的にも扱い易い対象である.

凸関数の性質のうち, 最適化の立場から最も基本的なものを挙げるとすれば次の二つであろう. (1) 局所最適条件が大域的最適性を特徴づける. したがって, 降
下法に基づく算法によって最適化が達成される. (2) 凸関数と凹関数の間に分離定理や Fenchel 双対定理のような双対性が成り立つ. これから Lagrange 双対理論が導かれ, 双対変数を用いた算法などが構成される. 線形計画法における双対性もこの特殊ケースと見なせる.

双対性について具体的に述べよう. $f$ :$.\backslash$$\mathrm{R}\mathrm{U}\{-\infty\}$$\mathrm{R}^{n}arrow$$\{+\infty\}$$\mathrm{R}\cup$.

.

を凹関数とする. 分離定理は, 図 1 のように, $f$ と1 次関数の存在を主張する. なお,

定理 1(分離定理 [38])$f(x)(\forall x\in \mathrm{R}^{n})$$f$$\langle p^{*}, x\rangle=\sum_{i}n=1P^{*}i^{X}i$を凸関数,ならば, ある$g$$\alpha^{*}\in \mathrm{R},$$g(x)\leq\alpha^{*}+\langle px\rangle*,\leq f(x)$を凸関数 ,$g$$g:\mathrm{R}^{n}arrow$を分離するようなである. aeを凹関数とし, 適当な仮定をおく. $g(x)\leq$$p^{*}\in \mathrm{R}^{n}$が存在して,$(\forall x\in \mathrm{R}^{n})$.

口Fenchel 双対定理を述べるには, 共役関数の概念が必要である. 関数$f \cdot(p)=\sup\{\langle p, x\rangle-f(X)|x\in \mathrm{R}^{n}\}$$(p\in \mathrm{R}^{n})$

$f$

に対し,

(1)

75

図 2: 共役関数 (Fenchel-Legendre transform).

.

を の (凸) 共役関数と呼ぶ.
:
は1次関数の最大値として定義されているから凸関数である. 写像 $f\mapsto f$ は, 理工学のあらゆる分野に登場する Legendre 変換に他ならない. 実際, が滑らかな凸関数で各 に対して $\sup$ を達成する $x=x(p)$ が存在する場合には, $x=x(p)$ は方程式 $f’(x)=p$ の解として定まり, $f\cdot(p)=’\langle p, x(p)\rangle-f(x(p))$ と表現される.
共役関数の意味は図形的にも理解しやすく, $n=1$ の場合, $-f\cdot(p)$ は, $y=f(x)$で定義される関数$f\cdot$$\mathrm{R}^{n}arrow \mathrm{R}\cup\{+\infty\}$

$f$

$f$

$f$

$P$

の傾き

$P$

の接線が

ae 同様に,$g$$y$軸と交わる点のの (凹) 共役関数$g^{\mathrm{O}}$:$y$座標である (図 2).

$\mathrm{R}^{n}arrow \mathrm{R}\cup\{-\infty\}$$g^{\mathrm{o}}(p)= \inf\{\langle p, x\rangle-g(x)|x\in \mathrm{R}^{n}\}$を(2)$(p\in \mathrm{R}^{n})$と定義するとき, Fenchel 双対定理は次のように述べられる.
定理 2(Fenchel 双対定理 [38]) $f$ を凸関数,$g$を導関数とし, 適当な仮定をおくと,.

$\inf\{f(x)-g(x)|x\in \mathrm{R}^{n}\}=\sup\{g^{\mathrm{o}}(P)-f\cdot(_{P},)|p.\in \mathrm{R}^{n}\}$口

分離定理や Fenchel 双対定理の形に表現される双対性が凸計画問題に対する主問題と双対問題の間の双対性を導くことは, その詳細を知らなくとも, 想像に難くないであろう. 例えば, Fenchel 双対定理において, 左辺が主問題, 右辺が双対問題に対応する. しかし, 凸解析の諸定理が非凸計画問題に対する双対理論の枠組みの基礎にもなっていることは, 必ずしも広く認識されていない. 例えば,
拡張 Lagrange 関数による乗数法などは, 摂動方向に凸性をもった摂動関数の中

76に原問題を埋め込むことによって導かれている (詳細は [39] 参照). このように,凸解析は, 非線形計画法全体の基礎を成しているのである.
他方, 離散最適化の分野を見てみると, 凸解析のような統– 的な視点はまだ存在しない. 離散最適化と非線形最適化は, 本質的に異なる部分も多いことは確か
しかし, 凸解析の離散版 — 上記の議論でである.

$\mathrm{R}$を$\mathrm{Z}$で置き換えた理論–ができれば, 離散最適化全体の役に立つに違いない. 例えば, 離散最適化問題に対しても拡張 Lagrange 関数による双対理論ができることになるので, 離散最適化の理論が整理されるだけでなく, 離散最適化を連続最適化に埋め込んで解くタ
イプのアルゴリズムが設計しやすくなるだろう.
節を改めて, 「離散凸解析」’ の可能性を探ってみよう.

2.2

目標定理と凸拡張に基づく試み

本稿では 「離散凸解析」 の目標を, 整数格子点の上で定義された整数値関数$f$に対して 「凸関数」 の概念をうまく定義し, 通常の凸解:$- \mathrm{Z}^{n}arrow \mathrm{Z}\mathrm{U}\{+\infty\}$析における諸定理の離散版を確立することとする. このとき, 分離定理の離散版としては, 1 次関数が整数ベクトルで定義されることを要請して,[離散分離定理]$(\forall x\in \mathrm{Z}^{n})$$f$が「凸関数」,

ならば, ある$\alpha^{*}\in \mathrm{Z},$$g$が「凹関数」 で, $g(x)\leq f(x)$$p^{*}\in \mathrm{Z}^{n}$$g(x)\leq\alpha^{*}+\langle p^{*}, X\rangle\leq f(x)$が存在して,$(\forall x\in \mathrm{Z}^{n})$を考えるのが自然であり, また最適化との関連で有用でもある. われわれの目標
は, この定理が成り立つような関数のクラスを見出し, それを離散世界の凸関数
概念と認識し, さらに, 離散最適化の算法を体系的に構成することである.

辛く自然な考えとして,「凸関数」 と定義してみよう$\mathrm{R}^{n}$上の凸関数に拡張可能な$\uparrow 1$$f$:$\mathrm{Z}^{n}arrow \mathrm{Z}\mathrm{U}\{+\infty\}$を. 1 次元 $(n=1)$ の場合には, これは$f(x-1)+f(x+1)\geq 2f(x)$$.(3)$$(\forall x-\in \mathrm{Z})$と同値であり, この定義の下で離散分離定理が成立する. しかし, 多次元 $(n\geq 2)$になると, 事情はそう単純でない.
例 1 $n=2$ として, $f(x_{1}, x2)= \max(0, X_{1}+x_{2}),$ $g(x1, X2)= \min(X_{12}, X)$ を考え
る.

(

$f,$

$\overline{f},$$\overline{g}$

して

$g$

ともに

の表式は $f,$と同じ). さらに,

$g$

:

$g$

$\mathrm{R}^{2}$上の凸関数 , 円関数 -g に拡張できる$\overline{f}$であり, $p^{*}=(1/2,1/2)$ に対とはを分離が成立するので, この$\overline{f}(x)\geq\overline{g}(x)$$\overline{f}(x)\geq\langle p^{*}, x\rangle\geq\overline{g}(x)(x\in \mathrm{R}^{2})$する. しかし, $f$ と$\uparrow 1f$

上で整数値をとり,$\mathrm{Z}^{2}$$p^{*}$$f$$g$

を分離する整数ベクトルは存在しない.

.
$\mathrm{Z}^{n}arrow \mathrm{Z}\mathrm{U}\{+\infty\}$が凸関数に拡張可能とは, ある凸関数て $\overline{f}(x)=f(X)(x\in \mathrm{Z}^{n})$ が成り立つことを言う.

$\overline{f}$:$\mathrm{R}^{n}arrow \mathrm{R}\mathrm{U}\{+\infty\}$

口

が存在し

77

この例の示すように, 凸拡張可能性による離散凸性の定義は不満足であり, より深い組合せ論的な考察が必要である. これは, 離散最適化問題を単に連続問題に埋め込む (緩和する) だけでは済まないという当然の事実に対応している.

3

マトロイド性と油性組合せ最適化の分野ではマトロイド的な構造が良い性質と認知されているので,これを手がかりに離散凸性に迫ろう.

有限集合 $V$ の上の集合関数.

$\rho$:$2^{V}arrow \mathrm{Z}\cup\{+\infty\}$は, 不等式(X,$\rho(X)+\rho(\mathrm{Y})\geq\rho(X\mathrm{u}Y)+\rho(X\cap \mathrm{Y})$$\mathrm{Y}\subseteq V$)

を満たすとき, 劣モジュラ関数と呼ばれる $(\rho(\emptyset)=0, \rho(V)<+\infty$ を仮定する).
劣モジュラ性と凸性には似ているところがある. 既に触れたが, 60 年代終わりにはその類似性が着目され, 80 年代はじめにはその関係が明らかになった. 例えに対して Lov\’asz 拡張と呼ばれる正斉次
ば, 一般の集合関数 :な\dagger 2 関数 :が劣モジュラが凸」がが定義され,$2^{V}arrow \mathrm{Z}\cup\{+\infty\}$$\rho$$\hat{\rho}$$\mathrm{R}^{V}arrow \mathrm{R}\mathrm{U}\{+\infty\}$$\lceil_{\rho}$$\Leftrightarrow\hat{\rho}$成り立つ. また, 劣モジュラ関数に関して, 次の形の離散分離定理が成り立つ.

定理 3(Frank [7])が優モジュラ$\uparrow 3$$\rho$:$2^{V}arrow \mathrm{Z}\cup\{+\infty\}$が劣モジュラ,で, $\mu(X)\leq\rho(X)(\forall.X\subseteq V)$ ならば, ある$\mu(X)\leq x^{*}(X)\leq\rho(X)$$(\forall X\subseteq V)$

$\mu$

:

$2^{V}arrow \mathrm{Z}\cup\{-\infty\}$$x^{*}\in \mathrm{Z}^{V}$.

が存在して,

口

これらの事実に基づき, 現在では, 「劣モジュラ関数の双対性
整数性」 という図式が広く受け入れられている.
双対性

$=$

凸解析における$+$

方, 整数格子点の (非空) 集合$B\subseteq \mathrm{Z}^{V}$( -EXC) 任意の $x,$ $y\in B$ と任意の$\mathrm{B}$る$v\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}-(x-y)$

は, 交換公理$u\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{+}(x-y)$に対して, あが存在して $x-\chi_{u}+xv\in B$ かつ $y+\chi_{u}-\chi_{v}\in B$

を満たすとき, 整基集合と呼ばれる$\dagger 4.$.

ここで$\chi_{u}\in$.

$\{0,1.\}^{V}|$は $u\in.V$ の特性ベク

トルを表わし, $\mathrm{S}\mathrm{u}\mathrm{P}\mathrm{p}^{+}(x-y)=\{u\in V|\dot{x}(u)>y(u)\},$$V|x(v)<y(v)\}$ である. 条件 ( -EXC) の趣旨は, B. が 2 点 $x,$$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{-}(X -y)=\{v\in$$\mathrm{B}$$y$を含めば, より近い 2 点 $x-\chi_{u}+\chi_{v},$ $y+\chi_{u}-xv$ を含むということであり, 通常の凸集合の条件に似ている.
$\uparrow 2\hat{\rho}$が成り立つことを言う.
に対してが正斉次とは, 任意の $\lambda>0$ とが劣モジュラのとき, は優モジュラであるという. ここで, $\rho(\emptyset)=\mu(\emptyset)=0,$ $\rho(V)<$$p\in \mathrm{R}^{n}$$\uparrow 3-\mu$$+\infty,$$\hat{\rho}(\lambda p)=\lambda\hat{\rho}(p)$$\mu$$\mu(V)>-\infty$ は暗黙の仮定である.

$\uparrow 4B\subseteq\{0,1\}^{V}$のとき, マトロイドの基族に対応する.

78

交換公理と劣モジュラ性は次の意味で同等である.
$x(X)= \sum v\in xX(v)$に対して,$x\in \mathrm{Z}^{V-},X\subseteq V$

とおく.

定理 4([10] 参照) 対応 (写像)$B$$\rho:\rho(X)=\sup\{x(X)|x\in B\}$$\mapsto$$(X\subseteq V)$,$B=\{x\in \mathrm{Z}^{V}|x(X)\leq\rho(X)(\forall X\subset V), x(V)=\rho(V)\}$$\rho\mapsto$

は, 整基集合 $B$ と劣モジュラ関数$\rho$の間の 1 対 1 対応を与える.

口

通常の凸解析では, 集合の凸性と関数の凸性が登場する. 集合
し, 標示関数$\delta_{D}$:$\mathrm{R}^{n}arrow \mathrm{R}\mathrm{U}\{+\infty\}$

定義すると, 「 $D$ が凸集合$\Leftrightarrow\delta_{D}$$D\subseteq \mathrm{R}^{n}$に対を $\delta_{D}(x)=0(x\in D),$ $=+\infty(x\not\in D)$ でが凸関数」 が成り立つ. 標示関数$\delta_{D}$の共役は正斉次な凸関数であり, $D$ の支持関数と呼ばれる.
このことを思い出しながら 「離散凸解析」 の立場から定理 4 を見直すと, その関数$\delta_{D}$

本質が凸集合とその支持関数の間の共役関係であることに気づく. すなわち, 「整骨集合 : 劣モジュラ関数の Lov\’asz 拡張 $=$ 凸集合 : 支持関数」 という対応関係である. この意味で, 従来のマトロイド理論が対象としていたものは, 離散世界の凸集合であると言える. これを拡張して 「凸関数」 の概念を導入しよう.

4

離散世界の凸関数–

凸集合から凸関数へに対して, 成分毎に最大値, 最小値をとって得られる格子点を $p\vee q,$ $p\wedge q$ と表す (すなわち $(p \vee q)..(v)=\max(p(v), q(v.).),$ $(p\wedge q)(v)=$
格子点 $p,$$q\in \mathrm{Z}^{V}$.

$\min(p(v), q(v))(v\in \mathrm{Z}^{V})$である). 関数$g.:\mathrm{Z}^{V}arrow \mathrm{Z}.\cup\{+\infty\}$が, 2 条件.

[劣モジュラ性] $g(p)+g(q)\geq g(p\vee q)+g(p\wedge q)$$\forall p\in \mathrm{Z}^{V}:.g(p+1)=g(p)+7^{\cdot}$[1 方向の線形性](ただし $1=(1,1,$)$(p, q\in \mathrm{Z}^{V})$,$\exists r\in \mathrm{Z},$$1)\in \mathrm{Z}^{V}$$\ldots,$を満たすとき,$g$を$\mathrm{L}$凸関数と定義する.

ここで, $\mathrm{d}\mathrm{o}\mathrm{m}g=\{x\in \mathrm{Z}^{V}|g(x)<$(実効定義域) は空でないとする. 劣モジュラ母数の Lov\’asz 拡張を格子点上に制限したものは正斉次な 凸関数であり, この逆も成り立つ.
方, 関数 :
が, 交換公理$+\infty\}$$\mathrm{L}$$f$($\mathrm{M}$$\mathrm{Z}^{V}arrow \mathrm{Z}\mathrm{U}\{+\infty\}$-EXC) 任意の $x,$て, ある$y\in \mathrm{d}\mathrm{o}\mathrm{m}f$$v\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{-}(x-y)$と任意の$u\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{+}(x-y)$が存在して-$f(x)+f(y)\geq f(_{X}-\chi u+xv)+f(y+x_{u}-\chi_{v})$

に対し

79

凸関数と定義する (を満たすとき, $f$ をは前提). 条件 (M-EXC)の趣旨は, 2 点 $x,$ における関数値の和は, より近い 2 点 $x-\chi_{u}+\chi_{v},$ $y+xu-x_{v}$$\uparrow 5$$\mathrm{M}$$\mathrm{d}\mathrm{o}\mathrm{m}f\neq\emptyset$$y$に移ると減る方向にあるということであり, 通常の凸関数の条件に似ている. 次の (i), (ii) が成り立つことから, ( -EXC) は ( -EXC) の定量的拡張と見なすこ$\mathrm{M}$$\mathrm{B}$とができる:(i)(ii)$\mathrm{M}$

凸関数の実効定義域は整基集合,$B\subseteq \mathrm{Z}^{V}$

が整基集合

離散システムには,$\mathrm{M}$$\Leftrightarrow B$

凸関数や例 2(行列式の次数) 変数.

の標示関数 (の$\mathrm{L}$$\mathrm{Z}^{V}$への制限) が$\mathrm{M}$

凸関数.

凸関数が自然な形で現れる.

に関する多項式を要素とするような行列 $A(s)$ を考$s$

える. $A(s)$ は階数が $m$ の $m\cross n$ 行列であるとし, その列番号の集合を $V$ と表す.

例えば,$\mathrm{A}$

2 3 4
1
1 1 1

1
$A(s)=$$s+1$

1$m=2,$ $n=4,$ $V=\{1,2,3,4\}$ である.

$0$

$s$

,

$A(s)$ の列べクトルの基底に対応する$V$の部分集合の族を $B(\subseteq 2^{V}),$ $B$ の元の特性ベクトルの全体を $B(\subseteq\{0,1\}^{V})$ とす
は $J$ の特性ベクトル). $B$ が整基集
すなわち, $B=\{\chi_{J}|J\in B\}$ である (合の公理 ( -EXC) を満たすことは, よく知られた事実である. 上の例では, $A(s)$る.

$\chi_{J}$$\mathrm{B}$のどの 2 列も $A(s)$ の基底であるから,$B=\{(1,1,0,0), (0,0,1,1), (1,0,1, \mathrm{o}), (1,0,0,1), (0,1,1,0), (0,1,0,1)\}$である.

( $m$ 次正方行列) を $A[J]$ と表すとき,に関する ( でない) 多項式であり, その次数 $\deg_{s}\det A[J]$$J\in B$ に対応する $A(s)$ の部分行列

その行列式 $\det A[J]$ は

$s$

$0$

を考えることができる.
$f(x)=\{$

で定義される関数 $f$ :$-\deg_{S}\det \mathrm{A}[J]$$(x=\chi_{J}, J\in B)$$+\infty$(otherwise)$\mathrm{Z}^{V}arrow \mathrm{Z}\mathrm{U}\{+\infty\}$は$\mathrm{M}$

凸関数である [2].

$B_{0}=\{(1,1,0,0), (0,0,1,1)\}$ として, $f(x)–0(x\in B_{0}),$$=+\infty(x\in \mathrm{Z}^{V}\backslash B)$$\mathrm{L}$となる.

凸関数も多項式行列から生ずる.

とする

$n$

上の例では,$=-1(x\in B\backslash B_{0})$.

.

$P\in \mathrm{Z}^{V}$に対して, $s^{p_{v}}(v\in V)$ を対角要素次対角行列を $D(p)$ と表し, $A$ と $D(p)$ の行列積の部分行列でする列からなるものを $(A\cdot D(p))[J]$ と書き表す. 関数$g:\mathrm{Z}^{V}arrow \mathrm{Z}$$g(p)= \max\{\deg_{s}\det(A\cdot D(p))[J]|J\in B\}$$\uparrow 5\mathrm{d}\mathrm{o}\mathrm{m}f\subseteq\{0,1\}^{V}$のときが$\mathrm{D}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}-\mathrm{w}\mathrm{e}\mathrm{n}\mathrm{z}\mathrm{e}\iota[2]$,の付値マトロイドに対応する.

を

$J$

に対応

80

$\text{と定義すると}$, これは$\mathrm{L}$

凸関数である. 上の例では,$g(p)= \max(p_{1}+p_{2},p3+p4, p1+p3+1, p_{1}+p_{4}+1, p_{2}+p_{3}+1, p_{2}+p4+1)$となる .

$\square$

この他にも, 最小費用流問題に関連して,

凸関数,$\mathrm{M}$$\mathrm{L}$凸関数が現れる [30,32, 35].

5離散凸解析の基本諸定理

雨性,
定理は,
$\mathrm{M}$$\mathrm{L}$$\mathrm{M}$

凸性の概念の重要性は, 以下の諸定理に示されている. まず最初の凸関数,$\mathrm{L}$

凸関数が確かに凸関数と呼ぶにふさわしいものであることを示している.

定理 5(拡張定理 [30])$\mathrm{M}$

離散世界での共役関数

凸関数,$f\cdot$:

凸関数は凸関数に拡張可能である.

$\mathrm{L}$を, 式 (1) に倣って,$\mathrm{Z}^{V}arrow \mathrm{Z}\mathrm{U}\{+\infty\}$$f \cdot(p)--\sup\{\langle p, X\rangle-f(_{X)}|x\in \mathrm{z}^{V}\}$と定義する. 次の定理は,$\mathrm{M}$凸関数と$\mathrm{L}$凸関数の間の共役関係を示しており, 定

定理 6 $(..[30].)$ ‘対応 (写像) $f\mapsto g=f\cdot,$ $g.-f=g$ は,.

の間の 1 対 1 対応を与える. さらに,

通常の連続世界では, 凸関数の概念に(4)$(p\in \mathrm{Z}^{V})$理 4(交換公理と劣モジュラ性の同等性) の–般化である. 例 2 の意味の共役関係にある.

$g$口$f\cdot\cdot=f,$$\mathrm{M}$とか$\mathrm{L}$$\mathrm{M}$

$f$

と

$g$

凸関数 $f$ とは,$\mathrm{L}$

この

凸関数

$=g$ が成り立つ.

$g$

口とかの区別はなく, 凸関数の共.

役は再び凸関数である. . これに対して, 離散世界では, 2 種類の凸性が区別され, それらが $f\mapsto f$ によって移り合うという状況になっている.

最後に双対定理を与える.

$(\mathrm{M}, \mathrm{L})$凹関数$\mathrm{d}\mathrm{o}\mathrm{m}g=\{x\in \mathrm{Z}^{V}|g(x)>-\infty\}$と定義する. なお,

定理 7($\emptyset$または$\mathrm{M}$

会離定理 [28, 30])ならば, ある$\alpha^{*}\in \mathrm{Z},$$p^{*}\in \mathrm{Z}^{V}$$f$を$\mathrm{M}$に対して,$g^{\mathrm{o}}(p)= \inf\{\langle p, x)-g(x)|x\in \mathrm{Z}^{V}\}$

凹関数とは, $-g$ が$g\text{が}(\mathrm{M}, \mathrm{L})$$\mathrm{d}\mathrm{o}\mathrm{m}f\cdot\cap \mathrm{d}\mathrm{o}\mathrm{m}g^{\mathrm{o}}\neq\emptyset$,$g:\mathrm{Z}^{V}arrow \mathrm{Z}\mathrm{U}\{-\infty\}$

凸関数,

$g$

$(\mathrm{M}, \mathrm{L})$を$\mathrm{M}$

凸関数のことである.

凹関数とし,$\mathrm{d}\mathrm{o}\mathrm{m}f\cap \mathrm{d}\mathrm{o}\mathrm{m}g\neq$が成り立つと仮定する. $g(x)\leq f(x)(\forall x\in \mathrm{Z}^{V})$が存在して,$g(x)\leq\alpha+\langle*px*,\rangle\leq f(X)$$(\forall x\in \mathrm{Z}^{V})$

.

口

81

定理 8(
または

$\mathrm{L}$

分離定理 [30]) $f$ を$\mathrm{d}\mathrm{o}\mathrm{m}f\cdot\cap \mathrm{d}\mathrm{o}\mathrm{m}g^{\mathrm{o}}\neq\emptyset$

らば, ある$\beta^{*}\in \mathrm{Z},$$x^{*}\in \mathrm{Z}^{V}$

凸関数,

凹関数とし,
が成り立つと仮定する. $g(p)\leq f(p)(\forall p\in \mathrm{Z}^{V})$ な$\mathrm{L}$) $\leq f(p)$定理 9(Fenchel 型双対定理 [28, 30])
またはを$\mathrm{d}\mathrm{o}\mathrm{m}f\cap \mathrm{d}_{0}\mathrm{m}g\neq\emptyset$$\mathrm{L}$が存在して,$g(p)\leq\beta^{*}+\langle p,$ $x^{*}$$\mathrm{d}\mathrm{o}\mathrm{m}g\neq\emptyset$$g$$\mathrm{d}\mathrm{o}\mathrm{m}f\cdot\cap \mathrm{d}\mathrm{o}\mathrm{m}g^{\mathrm{o}}\neq\emptyset$$(\forall p\in \mathrm{Z}^{V})$$f$を$\mathrm{M}$

.

口

凸関数,

$g$

を

$\mathrm{M}$が成り立つと仮定すると,$\inf\{f(x)-g(x)|x\in \mathrm{z}^{V}\}=\sup\{g^{\circ}(p)-f\cdot(P)|p\in \mathrm{z}^{V}\}$$\mathrm{M}$分離定理とある. また,$\mathrm{L}$$\mathrm{L}$

凹関数とし, dom

口分離定理は共役関係にあり, Fenchel 型双対定理は自己共役で分離定理は劣モジュラ関数に関する離散分離定理の–般化である.

これらの離散双対定理は, 見かけは通常の凸解析における双対定理と向じであるが, その本質は組合せ論的に深い内容を含んでいる. 拡張定理 (定理 5) と通常の分離定理 (定理 1) や Fenchel 双対定理 (定理 2) を合わせても上の離散双対定理は導かれない (例 1 参照).

以上の諸定理を基礎として, 劣勾配や双共役関数などの離散版が定義され, さらに離散最適化に対する Lagrange 双対理論が展開される [30]. 離散凸解析の現状は,[35] に整理されている.

参考文献[1] Dress, A. W. M., and Wenzel, W., Valuated matroid: A new look at thegreedy algorithm, Applied Mathematics Letters, 3 (1990) 33-35.
[2] Dress, A. W. M., and Wenzel, W., Valuated matroids, Advances in Mathematics, 93 (1992) 214-250.

[3] Edmonds, J., Submodular functions, matroids and certain polyhedra, in:, Combinatorial StrucR. Guy, H. Hanani, N. Sauer and J. Sch\"onheim,tures and Their Applications, Gordon and Breach, New York, 1970, 69-87.
$\mathrm{e}\mathrm{d}\mathrm{s}.$[4] Edmonds, J., Matroid intersection, Annals of Discrete Mathematics, 14(1979) 39-49.
[5] Favati, P., and Tardella, F., Convexity in nonlinear integer programming,
Ricerca Operativa, 53 (1990) 3-44.
[6] Frank, A., A weighted matroid intersection algorithm, Journal of Algorithms, 2 (1981) 328-336.

$f\cap$

82[7] Frank, A., An algorithm for submodular functions on graphs, Annals of
Discrete Mathematics, 16 (1982) 97-120.
[8] Fujishige, S., Theory of submodular programs: A Fenchel-type min-max
theorem and subgradients of submodular functions, Mathematical Programming, 29 (1984) 142-155.

[9] Fujishige, S., On the subdifferential of a submodular function, Mathematical Programming, 29 (1984) 348-360.

[10] Fujishige, S., Submodular Functions and Optimization, North-Holland,
Amsterdam, 1991.
[11] Fujishige, S., and Murota, K., On the relationship between -convex functions and submodular integrally convex functions, RIMS Preprint 1152,
Kyoto University (August 1997).
$\mathrm{L}$[12] Fujishige, S., and Murota, K., Short proofs of the separation theorems for
L-convex/concave and M-convex/concave functions, RIMS Preprint 1167,
Kyoto University (October 1997).
[13] 福島雅夫: 非線形最適化の理論, 産業図書, 1980.
[14] Iri, M., Network Flow, Transportation and Scheduling –Theory andAlgorithms, Academic Press, 1969.

[15] Iri, M., and Tomizawa, N., An algorithm for finding an optimal ‘independent assignment’ , Journal of the Operations Research Society of Japan,
19 (1976) 32-57.
[16] 伊理正夫, 藤重悟, 大山達雄, グラフネットワ $-$ クマトロイド, 産業図書,
東京, 1986.
[17] 今野浩, 山下浩: 非線形計画法, 日科技連, 1978.
[18] Lawler, E. L. , Matroid intersection algorithms, Mathematical Programming, 9 (1975) 31-56.

[19] Lawler, E. L. , Combinatorial Optimization: Networks and Matroids,
Holt, Rinehart and Winston, New York, 1976.

83[20] Lov\’asz, L., Submodular functions and convexity, Mathematical Programming The State of the Art (edited by Bachem, A., Gr\"otschel, M., andKorte, B)Springer-Verlag, Berlin, 1983, 235-257.
–[21] 室田–雄, マトロイドとシステム解析, 「離散構造とアルゴリズム火 (藤重面面), 近代科学社, 第 2 章, 57-109,1992.

[22] Murota, K., Valuated matroid intersection, I, II, SIAM Journal on Discrete Maihematics, 9 (1996) 545-561, 562-576.
[23] Murota, K., Structural approach in systems analysis by mixed matrices-An exposition for index of DAE, in ICIAM 95 (Proc. Third Intern.
Congr Indust. Appl. Math., Hamburg, Germany, July 3-7, 1995), K.
Kirchg\"assner, O. Mahrenholtz and R. Mennicken,, Mathematical Research, Vol. 87, Akadeplie Verlag, 1996, pp. 257-279.
$.4^{\backslash }$$\mathrm{e}\mathrm{d}\mathrm{s}.$[24] Murota, K., Fenchel-type duality for matroid valuations, Mathematical
Programming, to appear.
[25] Murota, K., On exchange axioms for valuated matroids and valuateddelta-matroids, Combinatorica, 16 (1996) 591-596.
[26] Murota, K., Matroid valuation on independent sets, Journal of Combinatorial Theory (B), 69 (1997) 59-78.
[27] Murota, K., Submodular flow problem with a nonseparable cost function, Report No. 95843-OR, Forschungsinstitut f\"ur Diskrete Mathematik,
Universit\"at Bonn, March, 1995.
[28] Murota, K., Convexity and Steinitz’s exchange property, Advances inMathematics, 124 (1996) 272-311.
[29] Murota, K., Characterizing a valuated delta-,matroid as a family of deltamatroids, Journal of Operations Research Society of Japan, to appear.

[30] Murota, K., Discrete convex
appear.

$\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{y}\mathrm{s}\mathrm{i}\mathrm{s}\vee$’Mathematical Programming, to[31] Murota, K., On the degree of mixed polynomial matrices, RIMS Preprint
1109, Kyoto University (October 1996).

84[32] Murota, K., Discrete convex analysis –exposition on conjugacy and duality, RIMS Preprint 1117, Kyoto University (December 1996). Presented
at “International Colloquium on Combinatorics and Graph Theory” atBalatonlelle, Hungary, July 1996.

[33] 室田–雄, 離散凸解析, 応用数理, 6(1996) 259-269.
[34] 室田–雄, 離散凸解析 : 組合せ最適化における凸性, オペレーションズリ
サーチ, 42 (1997) 35-40.
[35] 室田–雄, 離散凸解析, 「離散構造とアルゴリズム
学社, 1998.
$\cdot$$\mathrm{V}$」 (藤重悟編), 近代科[36] Murota, K., and Shioura, A., -convex function on generalized polymatroid, Research Reports on Mathematical and Computing Sciences, Tokyo
Institute of Technology, B-320, September, 1996.
$\mathrm{M}$[37] Nemhauser, G. L., and Wolsey, L. A., Integer and Combinatorial Optimization, John Wiley and Sons, New York, 1988.
[38] Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, 1970.

[39] Rockafellar, R. T., Conjugate Duality and Optimization, SIAM, Philadelphia, 1974.
[40] Rockafellar, R. T., Network Flows and Monotropic Optimization, John
Wiley and Sons, New York, 1984.
[41] Shioura, A., A constructive proof for the induction of -convex functions
through networks, Discrete Applied Mathematics, to appear.
$\mathrm{M}$[42] Shioura, A., Minimization of an
Mathematics, to appear.

$\mathrm{M}$-convex function, Discrete Applied[43] Whitney, H., On the abstract properties of linear dependence, Americal
Journal of Mathematics 57 (1935), 509-533.