第 4 章 M 凸関数の連続緩和と最小化 59
4.4 連続緩和
4.4.1 M 凸関数に対する離散化と連続化
M♮ 凸/M凸関数が凸拡張可能であることを、定理2.24と定理2.26で次のように述べた。
したがって任意のM♮凸/M凸関数に対して、その連続化が存在する。
定理 4.16.
(1) M♮凸関数f :Zn →R∪ {+∞}は凸拡張可能である. (2) M凸関数f :Zn →R∪ {+∞}は凸拡張可能である.
ここではM♮凸/M凸関数とM♮凸/M凸集合について，離散化と連続化がM♮凸/M凸性を 保つかどうかを考える．結論としては、連続化についてはM♮凸/M凸性は保たれるものの、
離散化については、一般にはM♮凸/M凸性は保たれない。このため、連続緩和法がL♮ 凸/L 凸関数よりも設計しにくい。
まず離散化について詳しく述べる。連続変数のM♮ 凸/M凸関数が、交換公理M-EXC[R], M♮-EXC[R]をα= 1の場合も含めて満たせば、離散化してもM♮凸/M凸関数となるが、一 般にはそうはならない。
命題 4.17.
(1)連続変数のM♮凸関数の離散化(3.9)は，離散変数のM♮凸関数とは限らない．
(2)連続変数のM凸関数の離散化(3.9)は，離散変数のM凸関数とは限らない．
離散化するとM♮凸/M凸性を失う関数の例としては，例2.12に示した2次関数がある．逆 に，条件(2.97), (2.98)を満たす行列で定義される2次関数は離散化してもM♮凸関数であり
（定理2.33），条件(2.99)を満たす行列で定義される2次関数は離散化してもM凸関数である
（定理2.35）．
次に，連続化ついて述べる．次の定理が成り立つ。
定理 4.18.
(1)離散変数のM♮凸関数の連続化(3.10)は，連続変数のM♮凸関数である．
(2)離散変数のM凸関数の連続化(3.10)は，連続変数のM凸関数である．
これらの命題と定理の特殊ケースとして、関数が標示関数である場合を考えると、集合の離 散化に関する命題と、集合の連続化（凸包）に関する定理が導かれる．
命題 4.19.
(1) M♮凸多面体Sに含まれる整数ベクトルの全体S∩Zn は，離散のM♮凸集合とは限ら ない．しかし，S が有界でその頂点がすべて整数ベクトルの場合には，S∩Zn は離散のM♮ 凸集合である*2．
(2) M凸多面体Sに含まれる整数ベクトルの全体S∩Zn は，離散のM凸集合とは限らな
い．しかし，Sが有界でその頂点がすべて整数ベクトルの場合には，S∩Zn は離散のM凸集 合である．
定理 4.20.
(1)離散のM♮凸集合の凸包は，M♮凸多面体である．
(2)離散のM凸集合の凸包は，M凸多面体である．
4.4.2 連続緩和の近接定理
連続緩和に基づくアルゴリズムの効率性は，元の問題の最適解と連続緩和の最適解との距離 に依存するため，この2つの最適解の近さを理論的に保証する「近接定理」が重要になる。本 章における主な成果は，問題(MC)に対する近接定理であり，元の(MC)とその連続緩和問題 (MC)の最適解のL∞距離がn−1以下であると主張するものである[53]．
定理 4.21 ((MC)に対するL∞距離の近接定理). n≥2とする。
(i) (MC) の任意の最適解 y∗ ∈ Zn に対して，(MC) のある最適解 x∗ ∈ Rn が存在して
∥x∗−y∗∥∞< n−1を満たす.
(ii) (MC) の任意の最適解 x∗ ∈ Rn に対して, (MC) のある最適解 y∗ ∈ Zn が存在して
∥y∗−x∗∥∞< n−1を満たす.
この定理の証明は第4.7.1節で与える. この定理は，(MC)の最適解が存在するときに限り (MC)の最適解が存在することも意味している．定理4.21に現れるn−1という限界値は、後
に示す第4.6.3節の例4.3により、これより改善できないことがわかる。
次にL1距離に関する近接定理に関する結果を述べる．定理4.21から，(MC)に関する次の 系が直ちに得られる．
系 4.22 ((MC)に対するL1距離の近接定理). n≥2とする。
(i) (MC) の任意の最適解 y∗ ∈ Zn に対して，(MC) のある最適解 x∗ ∈ Rn が存在して
*2Sが有界でなくても，任意の整数区間[a,b]Zとの共通部分S∩[a,b]Zの頂点がすべて整数ベクトルであれば よい．(2)においても同様．
∥x∗−y∗∥1< n(n−1)を満たす.
(ii) (MC) の任意の最適解 x∗ ∈ Rn に対して，(MC) のある最適解 y∗ ∈ Zn が存在して
∥y∗−x∗∥1< n(n−1)を満たす.
4.4.3 連続緩和法
連続緩和手法に基づくM凸関数最小化問題 (MC)の新しいアルゴリズムを提案する．第
4.2.3節で提案した新しい貪欲法を用いる。
f :Zn →R∪ {+∞}がM凸関数であるとする．F(y) =f(y) (∀y∈Zn)を満たす閉真M 凸関数F :Rn →R∪ {+∞}が与えられていて，domRF がdomZf の閉凸包であると仮定す る．f を最小化するアルゴリズムは次のようになる．
M凸関数の最小化アルゴリズム（連続緩和法）: RELAX(f, F) Input: 閉真M凸関数f と連続緩和のM凸関数F
Output: f の一つの最小解
Step 1: 閉真M凸関数 F の最小解の1つを求め，x∗∈domRF とする．
Step 2: ∥y◦−x∗∥1< nを満たす整数ベクトルを求め，y◦∈domZf とする．
Step 3: y◦を初期解として，アルゴリズムNewGreedyをM凸関数f に対して適用する．
domRFは，M凸集合domZf の閉凸包であるので，整数格子点上の基多面体となる（定理 4.20）．ゆえに，任意のx∈domRFに対して，ある整数ベクトルy∈domRF∩Zn= domZf が存在して，∥y−x∥∞<1を満たし，このベクトルyは∥y−x∗∥1< nも満たす．
第4.4.2節で示した近接定理を用いると，提案手法の計算時間は次の定理のようになる．こ
こでTrelax は(MC)の連続緩和解を求めるのに必要な計算時間を表し，Tround は(MC)の得 られた実行可能解x∈ Rn を(MC)の実行可能解y∈ Znに条件∥y−x∥1 < nを満たしな がら丸めるのに必要な計算時間を表すとする. K∞ を式(3.5)で定義したものとするとき，
Tround = O(n2logK∞)となる [87]．
定理 4.23. 連続緩和による(MC)の最適解を求めるアルゴリズム RELAX の計算時間は O(Trelax+Tround+n3Tfunc)である.
証明. 系4.22より，あるy∗∈argminZf が存在して，∥y∗−x∗∥1< n(n−1)を満たす．ゆ えに，Step 2で求めるベクトルy◦は
∥y∗−y◦∥1≤ ∥y∗−x∗∥1+∥x∗−y◦∥1< n(n−1) +n=n2
を満たす．このことと，定理 4.12 をあわせると，Step 3 のアルゴリズム NewGreedy は O(n3Tfunc)の計算時間で終了する．
Step 1にかかる時間，つまり連続緩和問題(MC)を解くのにかかる時間はTrelax であり，
Step 2にかかる時間はTround であるので、アルゴリズムRELAXで(MC)の最適解を求める には、O(Trelax+Tround+n3Tfunc)だけの時間で済む。
表4.1.実装したM♮凸関数最小化アルゴリズム
表記 アルゴリズム
SD 最急降下法(第4.2.1節) SD2 修正最急降下法 [52]
SCALING スケーリング法(第4.3.3節) RELAX 提案する連続緩和法(第4.4.3節)
注意 4.1. 実際には，(MC)の連続緩和の厳密な最適解を求める必要はなく，(MC)の最適解の
「近似値」xa∈Rnが求まれば十分である．「近似値」とは，(MC)のある最適解x∗∈Rnに対 して∥xa−x∗∥∞≤nを満たすことを意味する．このような解を求めるのに必要な計算時間を Trelax-apxで表すと，通常の場合Trelax-apxはTrelaxよりも小さい．また、定理4.21より(MC) の最適解y∗∈Znの中に，∥y∗−xa∥∞ ≤ ∥y∗−x∗∥∞+∥x∗−xa∥∞ ≤2nを満たすものがあ ることがわかる. この限界値を用いると，定理4.23の計算量をO(Trelax-apx+Tround+n3Tfunc) に改善できる。
(MC)の計算は、第4.2.2節で述べたように、実用上は準ニュートン法のようなアルゴリズ ムで高速に行えるが、理論的な計算量を解析すると次のようになる。(MC) の最適解の近似値 xa は，(MC)と同様の手法で効率的に求められる．例えば，[88]の(MC)に対するスケーリン グ手法を(MC)に適用することで，
O((n3+n2log(K∞/n))(log(K∞/n)/logn)Tfunc)
の計算時間のアルゴリズムが得られる。ただし，目的関数f の方向微分の計算にO(Tfunc)か かるものとする．この計算時間がTrelax-apxに対応するので、我々の連続緩和法の計算時間は
O((n3+n2log(K∞/n))(log(K∞/n)/logn)Tfunc)
となる. これは，先行研究における(MC)に対する結果[52, 87, 88, 91]の最良のものと同じで ある．従って，最悪計算量の理論的上界という意味においては、連続緩和手法は一般の(MC) に対する計算時間を改善するわけではない．しかし、第4.5節で述べるように、実際上の計算 時間を大きく改善する。