(57)【要約】【課題】確実に鞍点を見つけることが可能な鞍点探索装置、鞍点探索方法および該方法を実現するためのプログラムを提供する。【解決手段】たとえば、与えられた２つの極小点を結ぶ経路を与え、その経路上に現在の点、すなわち着目点を与え、その着目点が境界上にあるかどうかを判別し、境界上にあればその点を境界上の点として生成するというようにして、境界上の点を生成し（ステップＳ１）、生成された点からなる境界上で目的の関数の極小点を検索する（ステップＳ２）。そして、極小点が検索されると、その点を鞍点として出力する。【選択図】    図３
2005031888.tif 000002
【特許請求の範囲】
【請求項１】
ｎ次元ユークリッド空間において定義され、座標で必要な回数だけ微分可能な、下に有界で一価の実数関数の鞍点を求める鞍点探索装置において、
ｎ−１次元曲面であって、該曲面の一方の側にある点から前記関数の勾配方向に進んで到達する極小点と、該曲面のもう一方の側にある点から前記関数の勾配方向に進んで到達する極小点とが常に異なるものである境界上の点を生成する境界上点生成手段と、
前記生成された点からなる境界上で前記関数の極小点を探す極小化手段と、
着目点が前記境界上で極小であることを判定する極小判定手段と、
該極小判定手段によって判定された極小点を鞍点として出力する鞍点出力手段と
を備えることを特徴とする鞍点探索装置。
【請求項２】
前記境界上点生成手段は、
与えられた２つの極小点を結ぶ経路を生成する経路生成手段と、
該生成された経路上に前記着目点を逐次与える経路上点更新手段と、
前記着目点が境界上にあることを判定する境界上点判定手段と
からなることを特徴とする請求項１に記載の鞍点探索装置。
【請求項３】
前記生成される経路は直線であることを特徴とする請求項２に記載の鞍点探索装置。
【請求項４】
前記境界上点判定手段は、
前記着目点におけるＨｅｓｓｅ行列の負の固有値を持つ固有ベクトルのそれぞれと前記着目点における勾配の余弦を求め、該余弦の値の１つが“０”である場合に、前記境界上にあると判定し、
余弦の値が“０”となる固有ベクトルを前記境界に垂直なベクトルとして出力する
ことを特徴とする請求項２に記載の鞍点探索装置。
【請求項５】
前記極小化手段は、
前記境界に近づかせる境界漸近手段と、
前記関数の値を減少させる減少手段と
からなることを特徴とする請求項１に記載の鞍点探索装置。
【請求項６】
前記境界漸近手段は、前記境界に垂直なＨｅｓｓｅ行列の固有ベクトルに平行である、勾配成分を用いて前記境界に近づかせることを特徴とする請求項５に記載の鞍点探索装置。
【請求項７】
前記減少手段は、前記勾配を用いて前記関数の値を減少させることを特徴とする請求項５に記載の鞍点探索装置。
【請求項８】
ｎ次元ユークリッド空間において定義され、座標で必要な回数だけ微分可能な、下に有界で一価の実数関数の鞍点を求める鞍点探索方法において、
ｎ−１次元曲面であって、該曲面の一方の側にある点から前記関数の勾配方向に進んで到達する極小点と、該曲面のもう一方の側にある点から前記関数の勾配方向に進んで到達する極小点とが常に異なるものである境界上の点を生成し、
前記生成された点からなる境界上で前記関数の極小点を探し、
着目点が前記境界上で極小であることを判定し、
該判定された極小点を鞍点として出力する
ことを特徴とする鞍点探索方法。
【請求項９】
ｎ次元ユークリッド空間において定義され、座標で必要な回数だけ微分可能な、下に有界で一価の実数関数の鞍点を求める鞍点探索方法をコンピュータに実現させるためのプログラムであって、
前記鞍点探索方法は、
ｎ−１次元曲面であって、該曲面の一方の側にある点から前記関数の勾配方向に進んで到達する極小点と、該曲面のもう一方の側にある点から前記関数の勾配方向に進んで到達する極小点とが常に異なるものである境界上の点を生成し、
前記生成された点からなる境界上で前記関数の極小点を探し、
着目点が前記境界上で極小であることを判定し、
該判定された極小点を鞍点として出力する
ことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ｎ次元ユークリッド空間において定義され、座標で必要な回数だけ微分可能な、下に有界で一価の実数関数の鞍点を求める鞍点探索装置、鞍点探索方法および該方法を実現するためのプログラムに関するものである。
【０００２】
【従来の技術】
鞍点とは、ユークリッド空間で定義された関数のＨｅｓｓｅ行列の負の固有値の数が“１”で、勾配が“０”となる点である。したがって、始点と終点を与え、この始点と終点を結ぶ経路を変化させて、経路上の関数の極大値を極小にすることを考えると、鞍点では、経路上の関数の極大値が極小となる。化学反応は、エネルギーの極小をとる点から、他のエネルギーが極小となる点に進み、その速度は、鞍点でのエネルギーの関数であることが知られている。
【０００３】
図６に示すように、極小となる点を２つ求める。座標の１つを反応座標に設定する。反応座標に設定した座標の値を、一方の点の相当する座標の値から、もう一方の相当する座標の値に徐々に近づけながら、他の座標の値を変化させて関数の値の極小化を行う。この過程で関数の極小値が反応座標に対して極大になった点が鞍点である。この方法を反応座標の方法と言う。
また、他の方法として、考えている点の近傍で曲面を２次近似し、曲面を特徴づけるヘス行列、勾配ベクトルに基づく固有方程式を解き、特定の固有値に対応した固有ベクトルの方向へ２次近似が成り立つ範囲の量だけ点の移動を繰り返すことによって、平衡点（鞍点および安定点）を求める手法が開発されている（たとえば、特許文献１を参照）。
【０００４】
【特許文献１】
特開平６−１６１９９１号公報
【０００５】
【発明が解決しようとする課題】
ところが、反応座標の方法は、反応座標の選び方によっては、鞍点を見つけられないという問題があった。他の方法も、同様に鞍点を見つけられないことがあった。
【０００６】
本発明は、この点に着目してなされたものであり、確実に鞍点を見つけることが可能な鞍点探索装置、鞍点探索方法および該方法を実現するためのプログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
上記目的を達成するため、本発明の鞍点探索装置は、ｎ次元ユークリッド空間において定義され、座標で必要な回数だけ微分可能な、下に有界で一価の実数関数の鞍点を求める鞍点探索装置において、ｎ−１次元曲面であって、該曲面の一方の側にある点から前記関数の勾配方向に進んで到達する極小点と、該曲面のもう一方の側にある点から前記関数の勾配方向に進んで到達する極小点とが常に異なるものである境界上の点を生成する境界上点生成手段と、前記生成された点からなる境界上で前記関数の極小点を探す極小化手段と、着目点が前記境界上で極小であることを判定する極小判定手段と、該極小判定手段によって判定された極小点を鞍点として出力する鞍点出力手段とを備えることを特徴とする。
【０００８】
上記目的を達成するため、本発明の鞍点探索方法は、ｎ次元ユークリッド空間において定義され、座標で必要な回数だけ微分可能な、下に有界で一価の実数関数の鞍点を求める鞍点探索方法において、ｎ−１次元曲面であって、該曲面の一方の側にある点から前記関数の勾配方向に進んで到達する極小点と、該曲面のもう一方の側にある点から前記関数の勾配方向に進んで到達する極小点とが常に異なるものである境界上の点を生成し、前記生成された点からなる境界上で前記関数の極小点を探し、着目点が前記境界上で極小であることを判定し、該判定された極小点を鞍点として出力することを特徴とする。
【０００９】
上記目的を達成するため、本発明のプログラムは、ｎ次元ユークリッド空間において定義され、座標で必要な回数だけ微分可能な、下に有界で一価の実数関数の鞍点を求める鞍点探索方法をコンピュータに実現させるためのプログラムであって、前記鞍点探索方法は、ｎ−１次元曲面であって、該曲面の一方の側にある点から前記関数の勾配方向に進んで到達する極小点と、該曲面のもう一方の側にある点から前記関数の勾配方向に進んで到達する極小点とが常に異なるものである境界上の点を生成し、前記生成された点からなる境界上で前記関数の極小点を探し、着目点が前記境界上で極小であることを判定し、該判定された極小点を鞍点として出力することを特徴とする。
【００１０】
【発明の実施の形態】
まず、本発明の根幹となる思想を説明する。
【００１１】
各点で関数の勾配と接する線を勾配線と呼ぶことにし、その向きは、関数の勾配の向きと平行であるとする。
【００１２】
簡単な考察から、以下のことが分かる。
【００１３】
すなわち、勾配線は、勾配の大きさが“０”でない全ての点で定義され、お互いに交わらない。極小点の近傍では、勾配は極小点を向いていて、勾配線は極小点に集まる。極大点の近傍では、勾配は極大点と反対方向を向いていて、勾配線は極大点から湧き出す。
【００１４】
また、境界を以下のように定義する。
【００１５】
境界とは、その一方の側の点から勾配線を伝って降りたときに到達する極小点と、もう一方の側の点から勾配線を伝って降りたときに到達する極小点とが常に異なるｎ−１次元の曲面である。
【００１６】
簡単な考察から、以下のことが分かる。
【００１７】
すなわち、境界上の点では、境界に垂直なベクトルはＨｅｓｓｅ行列の固有ベクトルの１つと平行で、その固有値は負である。また、境界近傍にある点における勾配の、境界に垂直な成分は、境界と反対方向を向く。
【００１８】
鞍点の境界上の近傍では、勾配線は、鞍点に向かうものと、鞍点から湧き出すものとの２本がある。鞍点の近傍で境界上にない領域では、勾配線は鞍点を避ける。
【００１９】
境界上の点における勾配は、境界に垂直なベクトルに垂直である。つまり、境界上の点から勾配線に沿って勾配の方向に進むと境界上にいることが分かる。
【００２０】
以上のことから、境界上の点から勾配線に沿って勾配の方向に進むと、境界上で関数の値が極小となる点にいくらでも近づき、簡単な考察から、この点が鞍点であることが分かる。
【００２１】
つまり、境界上で関数を極小にする点は、鞍点である。
【００２２】
なお、鞍点では、Ｈｅｓｓｅ行列の負の固有値の数は“１”であるので、境界に垂直なベクトルは、Ｈｅｓｓｅ行列の負の固有値に対応する。
【００２３】
本発明を実現するには、Ｈｅｓｓｅ行列のある固有ベクトルと勾配が垂直であるという拘束条件のもとに関数を最小化する方法が考えられる。しかし、拘束条件下の最小化法として良く知られているＬａｇｒａｎｇｅの未定乗数法や罰金法を用いてこの問題を解くと、関数の、座標による３回偏微分を用いる必要がある。３回偏微分は、一般に計算量が膨大になるので、好ましくない。
【００２４】
そこで、Ｈｅｓｓｅ行列と勾配を用いて本発明を実現する方法として、以下の方法を見い出した。
【００２５】
つまり、拘束条件のもとに関数を最小化するのではなく、関数を最小化させる方法と、拘束条件を満たすように点を動かす方法を組み合わせることによって、境界上で関数を最小化する方法である。
【００２６】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【００２７】
図１は、本発明の一実施の形態に係る鞍点探索装置の概略構成を示すブロック図である。
【００２８】
同図に示すように、本実施の形態の鞍点探索装置は、各種情報を入力するための入力デバイス１と、装置全体の制御を司るＣＰＵ２と、該ＣＰＵ２が実行する制御プログラムや、各種テーブルデータ等を記憶するＲＯＭ３と、各種入力情報および演算結果等を一時的に記憶するＲＡＭ４と、たとえば液晶ディスプレイ（ＬＣＤ）等からなり、各種情報等を表示するための表示デバイス５と、たとえばハードディスクドライブ（ＨＤＤ）等からなり、入力デバイス１から入力された情報や、ＣＰＵ２が実行する制御プログラム等を記憶するストレージデバイス６と、上記各構成要素１〜６を相互に接続するバス７とによって構成されている。
【００２９】
図１を見れば分かるように、本実施の形態の鞍点探索装置は、汎用コンピュータによって構成されている。
【００３０】
図２は、図１の鞍点探索装置の機能構成を示すブロック図である。
【００３１】
同図に示すように、本実施の形態の鞍点探索装置は、処理対象の関数のデータを読み込み、境界上の点を生成するのに必要なデータを読み込むデータ入力部１１と、境界上の点を生成する境界上点生成部１２と、生成された点のデータを格納する点データ格納部１３と、境界上で関数の極小点を探す極小化部１４と、極小化されたかどうかを判定する極小判定部１５と、極小点を鞍点として出力する鞍点出力部１６とによって構成されている。
【００３２】
図３は、本実施の形態の鞍点探索装置、特にＣＰＵ２が実行する鞍点探索処理の手順を示すフローチャートである。
【００３３】
同図において、ステップＳ１では、境界上の点を生成する境界上点生成処理サブルーチンを実行する。
【００３４】
続くステップＳ２では、境界上で関数の極小点を探す極小点探索処理サブルーチンを実行する。
【００３５】
そして、ステップＳ３では、極小であるかどうかを判定し、勾配が十分小さく、鞍点に十分近いと判定される場合には、本処理を終了する一方、鞍点に十分近いと判定されない場合には、ステップＳ２に戻る。
【００３６】
図４は、上記ステップＳ１の境界上点生成処理サブルーチンの詳細な手順を示すフローチャートである。
【００３７】
同図において、まず、ステップＳ１１では、与えられた２つの極小点を結ぶ経路を与える。
【００３８】
なお、ステップＳ１１で与える経路は、本実施の形態のような直線に限らず、曲線でもよい。また、ステップＳ１１で与える経路は、本実施の形態のような２つの極小点を結ぶものに限らず、境界をまたぐものであれば何でもよい。但し、経路が境界をまたぐかどうかを前もって判定することは一般的に難しく、確実に境界をまたぐ経路を作る方法は、２つの極小点を結ぶ方法以外には発明者は知らない。
【００３９】
次に、ステップＳ１２では、上記経路上に現在の点、すなわち着目点を与える。ここで、経路上に現在の点を与える方法はどのようなものを用いても良いが、例えば、経路の一端から始め、微小距離進みながら、Ｈｅｓｓｅ行列の負の固有値を持つ固有ベクトルのそれぞれと勾配の余弦を求め、余弦の内の１つの符号が反転したら、前の点と今の点との間で、符号が反転した余弦について、余弦が“０”となる場所を２分探索する方法が挙げられる。また、余弦の値が“０”となる固有ベクトルを境界に垂直なベクトルとして出力する。
【００４０】
そして、ステップＳ１３では、着目点が境界上にあるかどうかを判定し、着目点が境界上にあると判定した場合には、本処理を終了する一方、そうでないと判定した場合には、ステップＳ１２に戻る。
【００４１】
上記ステップＳ１３では、現在の点におけるＨｅｓｓｅ行列の負の固有値を持つ固有ベクトルのそれぞれと現在の点における勾配の余弦を求め、余弦の値の１つが“０”である場合に、境界上にあると判定する。大抵の場合は、この判断方法を用いるだけでよいが、関数が複雑な場合には、この方法だけでは不十分である。さらに、境界の候補の両側に１つずつ点を取り、その両点を始点として、最小化を行い、到達した２点が異なることを確認する必要がある。
【００４２】
図５は、前記ステップＳ２の極小点探索処理サブルーチンの詳細な手順を示すフローチャートである。
【００４３】
同図において、まず、ステップＳ２１では、境界に垂直なＨｅｓｓｅ行列の固有ベクトルに平行である、勾配成分を用いて境界に近づく。例えば、境界に垂直なＨｅｓｓｅ行列の固有ベクトルに平行である、勾配成分だけ、現在の点を逐次移動させ、境界に垂直なＨｅｓｓｅ行列の固有ベクトルに平行である、勾配成分が“０”と見なされるまでこの処理を繰り返す。
【００４４】
ステップＳ２２では、関数の値が減少するように、勾配を用いて現在の点を移動する。勾配だけを用いる方法、例えば急速緩和法を用いてもよいし、Ｈｅｓｓｅ行列を用いてもよい。このときに、点の移動が大き過ぎると、境界から大きく離れる可能性があるので、点の移動は大き過ぎてはいけない。
【００４５】
本極小点探索処理は、これに限らず、例えば、勾配の大きさを計算し、予め与えられた設定値より小さければ、極小であると判断する方法でもよい。大抵の場合には、この判断方法を用いるだけでよいが、２次以上の鞍点（勾配が“０”で、Ｈｅｓｓｅ行列の負の固有値の数が２個以上の点）が存在し、その近くから鞍点探索を行った場合には、２次以上の鞍点に達することがある。さらに、Ｈｅｓｓｅ行列の負の固有値の数を調べ、２個以上あれば、境界に垂直な固有ベクトル以外の、負の固有値を持つ固有ベクトルの適当な線形和だけ、現在の点をずらす必要がある。この処理によって２次以上の鞍点から脱出することができる。
【００４６】
なお、上述した実施の形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムまたは装置に供給し、そのシステムまたは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、本発明の目的が達成されることは言うまでもない。
【００４７】
この場合、記憶媒体から読出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００４８】
プログラムコードを供給するための記憶媒体としては、たとえば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。また、通信ネットワークを介してサーバコンピュータからプログラムコードが供給されるようにしてもよい。
【００４９】
また、コンピュータが読出したプログラムコードを実行することにより、上述した実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳなどが実際の処理の一部または全部を行い、その処理によって上述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【００５０】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって上述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【００５１】
【発明の効果】
以上説明したように、本発明によれば、境界上で極小点として鞍点を探すようにしたので、確実に鞍点を探索することができる。
【００５２】
また、本発明によれば、Ｈｅｓｓｅ行列の固有値および勾配を用いて鞍点を探索するようにしたので、計算量を減少させることができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係る鞍点探索装置の概略構成を示すブロック図である。
【図２】図１の鞍点探索装置の機能構成を示すブロック図である。
【図３】図１の鞍点探索装置、特にＣＰＵが実行する鞍点探索処理の手順を示すフローチャートである。
【図４】図３の境界上点生成処理サブルーチンの詳細な手順を示すフローチャートである。
【図５】図３の極小点探索処理サブルーチンの詳細な手順を示すフローチャートである。
【図６】鞍点を探索する従来の方法を説明するための図である。
【符号の説明】
１  入力デバイス
２  ＣＰＵ
３  ＲＯＭ
４  ＲＡＭ
５  表示デバイス
６  ストレージデバイス
１１  データ入力部
１２  境界上点生成部
１３  点データ格納部
１４  極小化部
１５  極小判定部
１６  鞍点出力部
【図１】
2005031888.tif 000003
【図２】
2005031888.tif 000004
【図３】
2005031888.tif 000005
【図４】
2005031888.tif 000006
【図５】
2005031888.tif 000007
【図６】
2005031888.tif 000008