スケーリング

離散関数の最小解を求めるアルゴリズムを高速化する手法の1つに、スケーリング法があ る。ここでは、まずスケーリングの基本的な考え方を述べ、次に離散L^♮凸/L凸関数にどのよ うに適用されるかを述べる。離散L^♮凸/L凸関数にはこの手法が効率的に働き、容易に多項式 時間の最小化アルゴリズムが実現される。

3.3.1 _{スケーリングの考え方}

スケーリングの基本的なアイデアは、離散格子点の格子を間引くことにある。格子を間引く と精密さはなくなるが、関数の実効定義域が実質的に小さくなるので、最小化が高速に行える ことが期待される。最小解の位置は、間引く前後で近いところにあることが多い。離散関数の 性質によっては近さを理論的に解析できる場合があり、この距離を保証するのがスケーリング の近接定理である。

例えば、与えられた離散関数を最小化することを考える。同時に、偶数格子点だけに間引い た関数も考える。つまり、f :Zⁿ→ Rが与えられたとして、偶数格子点上のf を取り出した

0 1 2 3 4 5 6

x

f(x) f2(^x₂)

図3.1.離散変数のスケーリング

関数f2を

f2(x) =f(2x) として作る。

dom_Zf2はdom_Zf に比べると、その要素の個数は1/2ⁿ ほどの大きさである。argmin_Zf2

とargmin_Zf に単純な関係性があれば、比較的容易に求められるargmin_Zf2（に含まれる解）

を利用することで、argmin_Zf（に含まれる解）を効率的に求めることができる。

このことを1変数の場合に描いたのが図3.1である。f :Z→ Rの最小化を次のようにし て行う。まずf2(x)の最小化を行う。f2(⁴₂)で最小となることがわかるので、次にx= 4から f(x)の最小化を行う。すると容易にf(3)で最小化が完了する。更に再帰的に、最初のf2(x) の最小化にも、

f4(x) =f2(2x) と定義したf4の最小化の結果を利用することもできる。

一般に，離散変数の関数f :Zⁿ→R∪ {+∞}^{と正の整数}αおよびb∈Z^{nに対して，}

f^α(x) =f(αx+b) (x∈Zⁿ) (3.6)

で定義される関数f^α:Zⁿ →R∪ {+∞}はスケーリングと呼ばれる。スケーリングを再帰的 に適用するアルゴリズムは，スケーリング法と呼ばれる。

関数f :Zⁿ →R∪ {+∞}をスケーリングした関数f^α の最小点（あるいは極小点）をy^α とするとき，y^αを用いて計算したf の近似最小点

x^α=αy^α+b (3.7)

に関して，真の最小点x^∗との距離の近さを保証する定理は、近接定理と呼ばれる。1変数の 場合は、f が離散凸であれば容易に

x^α−(α−1)≤x^∗≤x^α+ (α−1) (3.8)

が成り立つことがわかる。多変数の場合にも，後述するように、L^♮ 凸/L凸関数とM^♮ 凸/M 凸関数に対して近接定理が成り立つ．

3.3.2 L 凸関数に対するスケーリング

関数g:Zⁿ→R∪ {+∞}と正の整数αおよびb∈Zⁿに対して，gのスケーリング(3.6)を g^α(p) =g(αp+b)

とする．

L^♮凸/L凸関数は、スケーリングを行ってもL^♮凸/L凸性を保持し続ける。これは（後述す る）M^♮凸/M凸関数とは異なる、重要な性質である。

命題 3.3 ([62,定理 7.11(1),定理 7.10(2)]).

(1)関数g:Zⁿ →R∪ {+∞}がL^♮凸関数ならば，g^αもL^♮凸関数である．

(2)関数g:Zⁿ →R∪ {+∞}がL凸関数ならば，g^αもL凸関数である．

L^♮ 凸/L凸集合についても、同様にスケーリングの関係がある。集合S と集合S^αに関し て、ある正の整数αおよびb∈Z^{nが存在して}

S^α={p∈Zⁿ|αp+b∈S}

を満たすとする。このとき、それぞれの標示関数δS : Zⁿ → R∪ {+∞} ^とδS^α : Zⁿ → R∪ {+∞}^{の間には、}

δS^α(p) =δS(αp+b) の関係が成り立つので、次の命題の成り立つことがわかる。

命題 3.4.

(1)集合SがL^♮凸集合ならば，集合S^αもL^♮ 凸集合である．

(2)集合SがL凸集合ならば，集合S^αもL凸集合である．

3.3.3 スケーリングの近接定理

L^♮ 凸/L凸関数に対する近接定理は，スケーリングされた関数g^αの極小点q^αから、(3.7) に従って

p^α=αq^α+b

として計算した点p^αの近くに，gの最小点p^∗が存在することを保証する．なお，命題3.3， 定理3.1により，g^αの極小点はg^αの最小点である．

定理 3.5 ([62,定理 7.18][36]). αを正整数とする．

(1)g:Zⁿ →R∪ {+∞}をL^♮凸関数とし，p^α∈dom_Zgとする．任意のq∈ {0,1}ⁿに対 して

g(p^α)≤min{g(p^α−αq), g(p^α+αq)}

ならば，argmin_Zg̸=∅であって，

p^α−n(α−1)1≤p^∗≤p^α+n(α−1)1 を満たすp^∗∈argmin_Zgが存在する．

(2) g : Zⁿ → R∪ {+∞} ^を g(p) = g(p+1) (∀p ∈ Zⁿ) を満たす L 凸関数とし，

p^α∈dom_Zg とする．任意のq∈ {0,1}ⁿに対して g(p^α)≤g(p^α+αq) ならば，argmin_Zg̸=∅^{であって，}

p^α≤p^∗≤p^α+ (n−1)(α−1)1 を満たすp^∗∈argmin_Zgが存在する．

3.3.4 _{スケーリング法}

上の近接定理を利用してL^♮凸関数gを最小化するアルゴリズム[62, 第10.3.2節]を示す．

L^♮凸関数の最小化アルゴリズム（スケーリング法）: SCALING(g,p) Input: 離散L^♮凸関数gと初期解p∈dom_Zg

Output: gの一つの最小解

Step 0: k:=⌈log₂K_∞⌉,qk+1:=0とおく．

Step 1: αk:= 2^k とおく。

gk(q) :=g(p+αkq), dom_Zgk:={q∈Zⁿ|2qk+1−n1≤q≤2qk+1+n1} として最急降下法SD(gk, 2qk+1)を呼び出し、得られた最小解をqkとする。

Step 2: k= 0ならばp+q0を返す（p+q0はgの最小解の一つ）． Step 3: k:=k−1としてStep 1に戻る.

手順Step 1で呼び出す最急降下法SD(gk, 2qk+1)では、関数の定義域が小さいので、必要 な計算量はO(nSTfunc)ですむ。手順Step 1からStep 3の反復は、ちょうど(⌈log₂K_∞⌉+ 1) 回であるので、全体の計算量はO(nSTfunc⌈log₂K_∞⌉) となり、スケーリング法は多項式時間 で終了することがわかる [62, 第10.3.2節]．