研究

区間解析を用いた大域的最適化手法の研究

区間演算による関数値の区間包囲を利用した大域的最適化手法を研究している。

大域的最適化とは

大域的最適化とはある関数の制約条件を満たす範囲内における最小値を見つける手法である。

現在の多くの実用的な関数を最小化する方法には数理計画法や確率的アルゴリズムが用いられている。

数理計画法は高速な計算ができる反面で局所最適解に収束して大域的最適解を見つける能力が低いという欠点がある。

焼きなましや遺伝的アルゴリズムなどの確率的アルゴリズムは大域的最適解を見つける能力に長けている反面で得られた解が大域的最適解であるという保証がない。

研究目的

例として橋を作る場合を考える。橋は重さに耐えなければならない。

橋が指定の重量に耐えながら、橋を作る材料をできるだけ少なくしたい。

このような設計上の問題を関数として定式化し数学的に解くことで、設計を補助することが本研究の目的である。

従来の手法では、一回の計算で最適な橋の構造を一つ得ることができる。

本研究では一回の計算で最適な設計及び最適に近い設計を全て網羅できるアルゴリズムを開発する。

設計者は得られた設計のうちから好きなデザインのものを選ぶことができる。

なぜ区間演算なのか

区間演算にはある区間における関数値の最大値と最小値を含む区間を計算できるという性質があり、これを区間包囲とよぶ。

本研究ではこの区間包囲に着目し、確実に最適解を求めることができ、かつ区間内の全ての最適解を列挙できるアルゴリズムの開発に取り組む。

複数の最適解が存在した場合にその全てを列挙できるということは数理計画法や確率的アルゴリズムでは困難なため、区間演算の有利な点である。

 

区間包囲という性質とその精度

区間演算で関数値を計算すると最大値と最小値を包囲する区間を得ることができる。

    \[f(x)=x^2\]

という関数について考える。

例えば、区間Xにおいて

    \[f(X)=X^2\]

という区間拡張された関数があり、[1,2]における区間演算の結果は

    \[f([1,2])=[2,4]\]

を得る。関数の

    \[1 \le x \le 2\]

という区間における関数値が

    \[2 \le f(x) \le 4\]

であるという意味になる。

この場合は関数の実際の最小値・最大値と得られた区間の上下限が一致している。

しかし[-1,2]という区間を与えると、

    \[f([-1,2])=[-2,4]\]

となる。

実際の最小値は0であるが、区間が広くなっている。

区間演算を繰り返すごとにこの広がりが大きくなり、最適化の妨げとなる。

よりシャープな区間包囲(区間が最小値・最大値により近いことをこう呼ぶ)を得ることが肝要となる。

与えた区間が広いほど区間演算の結果もより広いものとなる。

シャープな区間包囲を得るためには与える区間を狭くすることが一番重要である。

区間演算と二分探索に基づく最適化

初期区間を定め、区間を半分にしながら区間演算で関数値を計算する。

理論的には区間を細かく分割して全ての区間について区間演算を行えば。区間を比較することで最小値を得ることができる。

効率的に区間を分割するために二分探索を用いる。

 

二分探索の限界

二分探索を用いると区間を半分にするという操作を行うことになる。

上の例のように変数がx一つだと簡単に二分探索で最小値を求めることができる。

数直線上を2分割すると右と左の2つの領域ができる。

変数が2つになった場合はどうなるか。

数直線がグラフになるイメージである。

x軸とy軸をそれぞれ2分割すれば4つの領域ができる。

変数が3つになると3次元だ。

x軸とy軸とz軸をそれぞれ2分割すれば8つの領域ができる。

4次元以降はグラフで説明することは難しいが、4次元で4つの軸をそれぞれ2分割すれば16の領域ができる、5次元なら32の領域となる。

関数の変数の数nに対して指数関数的に分割のコストが増えていく。

変数が10000を超えると二分探索を用いたとしても、現在のコンピュータでこれを行うには宇宙が生まれてから今までの時間計算し続けても時間が足りない。