実験的評価 - M 凸関数の連続緩和と最小化 59 - 離散凸最適化のアルゴリズムとソフトウェアの研究

第 4 章 M 凸関数の連続緩和と最小化 59

4.5 実験的評価

表4.1.実装したM^♮凸関数最小化アルゴリズム

表記アルゴリズム

SD 最急降下法(第4.2.1節) SD2 修正最急降下法 [52]

SCALING スケーリング法(第4.3.3節) RELAX 提案する連続緩和法(第4.4.3節)

注意 4.1. 実際には，(MC)の連続緩和の厳密な最適解を求める必要はなく，(MC)の最適解の

「近似値」xa∈Rⁿが求まれば十分である．「近似値」とは，(MC)のある最適解x_∗∈Rⁿ^に対して∥xa−x_∗∥∞≤nを満たすことを意味する．このような解を求めるのに必要な計算時間を Trelax-apxで表すと，通常の場合Trelax-apxはTrelaxよりも小さい．また、定理4.21より(MC) の最適解y_∗∈Zⁿの中に，∥y_∗−xa∥∞ ≤ ∥y_∗−x_∗∥∞+∥x_∗−xa∥∞ ≤2nを満たすものがあることがわかる. この限界値を用いると，定理4.23の計算量をO(Trelax-apx+Tround+n³Tfunc) に改善できる。

(MC)の計算は、第4.2.2節で述べたように、実用上は準ニュートン法のようなアルゴリズムで高速に行えるが、理論的な計算量を解析すると次のようになる。(MC) の最適解の近似値 xa は，(MC)と同様の手法で効率的に求められる．例えば，[88]の(MC)に対するスケーリング手法を(MC)に適用することで，

O((n³+n²log(K_∞/n))(log(K_∞/n)/logn)Tfunc)

の計算時間のアルゴリズムが得られる。ただし，目的関数f の方向微分の計算にO(Tfunc)かかるものとする．この計算時間がTrelax-apxに対応するので、我々の連続緩和法の計算時間は

O((n³+n²log(K_∞/n))(log(K_∞/n)/logn)Tfunc)

となる. これは，先行研究における(MC)に対する結果[52, 87, 88, 91]の最良のものと同じである．従って，最悪計算量の理論的上界という意味においては、連続緩和手法は一般の(MC) に対する計算時間を改善するわけではない．しかし、第4.5節で述べるように、実際上の計算時間を大きく改善する。

• Nocedal による ‘L-BFGS’ ^*3 と，工藤によるC++ 言語用インタフェース ^*4 は準ニュートン法の実装で，連続関数最適化を行う [44]．このルーチンには目的関数の勾配が必要であるので，差分で近似した．1つの差分を得るのにn+ 1回の関数評価が必要である．このライブラリはRELAX（提案する連続緩和法）でのみ用いた．

• ^{斎藤・松本による}‘SIMD-oriented Fast Mersenne Twister’^*5 は擬似乱数を生成する．

問題例を生成するのに利用した．

問題例に用いた離散M^♮凸関数は f(x) = ∑

X∈T

{aXx(X)²+bXx(X) +cX} (x∈Zⁿ)

と表されるものである．ただしT は層族である。連続緩和法では，連続緩和のM^♮ 凸関数として

F(x) = ∑

X∈T

{aXx(X)²+bXx(X) +cX} (x∈Rⁿ)

を用いた．1つのnにつき10問の問題例を生成した．整数の係数は、X ∈ T ^について 0< aX ≤1000,

−1000≤bX ≤ 1000,

−1000≤cX≤ 1000 の範囲から一様ランダムに選んだ．初期解は，各問題例ごとに

−10n≤p0(i)≤10n を満たす整数格子点からランダムに選んだ．

計算機環境はHP dx5150 SF/CT, AMD Athlon 64 3200+ processor (2.0GHz, 512KB L2 cache), 4GB memory, Vine Linux 4.1 (kernel 2.6.16), gcc 3.3.6である．

ここで実装した4種類のアルゴリズム（SD, SD2, SCALING, RELAX）では，どれも最小化したいM^♮ 凸関数の値のみを用いており、関数の内部構造は利用していない．そして問題ごとに，最小化に必要となった関数評価回数と計算時間を測定した．数値計算の結果は図4.1にまとめた．図4.1の上のグラフは両対数グラフであり，縦軸は関数評価回数C，横軸は関数の次元nである．図4.1の下のグラフも両対数グラフであり，縦軸は計算時間T，横軸は関数の次元nである．これより，関数評価回数Cについて、すべてのアルゴリズムでlogCとlogn が比例していることが読み取れる．つまり，あるlを用いてC= O(n^l)と表せることになる．

計算時間T についても同様にT = O(n^l)と表せる．lを最小二乗法であてはめて求めた値を、

表4.2にまとめた．RELAXがオーダーとしてもっとも小さいことがわかる．

以上のように，計算機実験によって，ランダムなテスト問題に対して，連続緩和法は先行手法よりも高速にM^♮凸関数を最小化できることが確かめられた．

*3http://www.ece.northwestern.edu/~nocedal/lbfgs.html

*4http://chasen.org/~taku/software/misc/lbfgs/

*5http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/

10³ 10⁴ 10⁵ 10⁶

10 100

関数評価回数

, C

変数の次元数

, n SD (an^3.9) SD2 (bn^2.8) SCALING (cn^2.5) RELAX (dn^1.8)

0.01 0.1 1 10

10 100

計算時間

, T(

秒

)

変数の次元数, n

SD (an^4.5) SD2 (bn^3.8) SCALING (cn^3.8) RELAX (dn^3.0)

図4.1.M^♮凸関数最小化に必要な目的関数の評価回数と計算時間

表4.2.M^♮凸関数最小化にかかった計算量（測定値）

アルゴリズム SD SD2 SCALING RELAX 関数評価回数 C n^3.9 n^2.8 n^2.5 n^1.8

計算時間T n^4.5 n^3.8 n^3.8 n^3.0

ドキュメント内離散凸最適化のアルゴリズムとソフトウェアの研究 (ページ 81-84)