(57)【要約】      （修正有）【課題】拘束条件付き最適化問題の解を簡単な手順で求められるようにする。【解決手段】拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、（１）点ｒの初期値設定、（２）超曲面Ｓ（ｒ）＝０への直線的接近、（３）単位法線ベクトルの計算、（４）実関数Ｅ（ｒ）の勾配ベクトル−▽Ｅ（ｒ）の接平面への射影、（５）収束判定、の過程により点ｒを通る超曲面Ｓ（r）＝ｃの測地線に対して２次の接触をする曲線に沿った極小値探索過程とを用いて拘束条件付き最適化問題を解く。【選択図】図８
2005259061.tif 000002
【特許請求の範囲】
【請求項１】
拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、点ｒを通る超曲面Ｓ（r）＝ｃの測地線に対して２次の接触をする曲線に沿った極小値探索過程とを含むことを特徴とする拘束条件付き最適化方法。
【請求項２】
前記超曲面Ｓ（r）＝０への直線的接近過程において拘束条件を与える関数Ｓ（r）に対し、∇を勾配を与える微分演算子として、点ｒの更新を
【数１】
2005259061.tif 000074
で与えられる式に従って行うことを特徴とする請求項１に記載の最適化方法。
【請求項３】
前記２次の接触をする曲線に沿った極小値探索過程において、極小値を探索する実関数をＥ（ｒ）とし、拘束条件をＳ（ｒ）＝０とする際、ｉ，ｊを座標成分、ｄを適当に選ばれる実数、＜，＞をベクトル空間の内積とし、
【数２】
2005259061.tif 000075
として、点ｒの更新を
【数３】
2005259061.tif 000076
で与えられる式に従って行うことを特徴とする請求項１又は２に記載の最適化方法。
【請求項４】
請求項１〜３の何れかに記載の最適化方法を実行する手段を有することを特徴とする最適化装置。
【請求項５】
請求項１〜３の何れかに記載の最適化方法をコンピュータに実行させるコンピュータ読取可能なプログラム。
【請求項６】
超曲面Ｓ（ｒ）への直線的接近過程と、次元数回、各座標系に対する単位ベクトルの超曲面Ｓ（ｒ）＝ｃへの射影方向に２次の接触をする曲線に沿った極値探索過程とを含むことを特徴とする最適化方法。
【請求項７】
前記超曲面Ｓ（r）＝０への直線的接近過程において拘束条件を与える関数Ｓ（r）に対し、∇を勾配を与える微分演算子として、点ｒの更新を
【数４】
2005259061.tif 000077
で与えられる式に従って行うことを特徴とする請求項６に記載の最適化方法。
【請求項８】
前記２次の接触をする曲線に沿った極値探索過程において、極値を探索する実関数をＥ（ｒ）とし、拘束条件をＳ（ｒ）＝０とする際、ｉ，ｊを座標成分、ｄを適当に選ばれる実数、＜，＞をベクトル空間の内積とし、
【数５】
2005259061.tif 000078
として、点ｒの更新を
【数６】
2005259061.tif 000079
で与えられる式に従って行うことを特徴とする請求項６又は７に記載の最適化方法。
【請求項９】
請求項６〜８の何れかに記載の最適化方法を実行する手段を有することを特徴とする最適化装置。
【請求項１０】
請求項６〜８の何れかに記載の最適化方法をコンピュータに実行させるコンピュータ読取可能なプログラム。
【請求項１１】
∇を勾配を与える微分演算子、ｉ，ｊを座標成分、ｄを適当に選ばれる実数、＜，＞をベクトル空間の内積とし、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的漸近過程
【数７】
2005259061.tif 000080
と、超曲面Ｓ（ｒ）＝ｃに対する接平面に射影した方向への極値探索過程
【数８】
2005259061.tif 000081
とを含むことを特徴とする最適化方法。
【請求項１２】
請求項１１に記載の最適化方法を実行する手段を有することを特徴とする最適化装置。
【請求項１３】
請求項１１に記載の最適化方法をコンピュータに実行させるコンピュータ読取可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、拘束（制約）条件付き最適化問題の解法に関するものである。
【背景技術】
【０００２】
近年、各種の産業分野で最適化問題を解決することが要望されている。この最適化問題は、厳密に定義すれば、或る空間において、与えられた幾つかの制約条件を満足する点からなる部分集合の中で、目的とする関数の値を最大あるいは最小にする点を求める問題であり、要するに、対象とする問題について定式化し、その式の中から最適な解を求めるものである。
【０００３】
このような最適化問題は、例えば、所望の仕様を得るための設計パラメータを決定する所謂自動設計、具体的にはエネルギーが最小となるような分子構成の探索、容器の中に液体と気体、或いは２種類の液体があって、体積一定の条件の下で界面形状の決定、所望の光学特性を得るためのレンズ形状の決定やレンズ間隔及び材質の決定等に用いられるものである。
【０００４】
一般に、拘束条件Ｓ（ｒ）＝０のもとで、実関数Ｅ（ｒ）＝０の値を極小化する問題について考える。ここで、ｒはｎ次元実ベクトルであり、
【０００５】
【数９】
2005259061.tif 000003
であるとする。実関数を極大化する問題は、関数の符号を逆にすることにより、上述の問題に帰着する。
【０００６】
拘束条件の無い場合、このような問題を解くためのアルゴリズムとしては、適当な初期ベクトルｒ(0)から出発し、勾配ベクトルＴ＝−∇Ｅ（ｒ）に関する情報を用いて、関数Ｅ（ｒ）が極小になる点ｒを探索するものが一般的である。
【０００７】
拘束条件が加わる場合は、このような単純なアルゴリズムではうまくいかないので、種々の工夫がなされてきた。代表的なものとしては、ペナルティ法（罰金法）と乗数法（ラグランジュの未定乗数法）がよく知られている（非特許文献１参照）。
【０００８】
ペナルティ法は、拘束条件を表現するために、拘束条件が成り立つときには０となり、成り立たなければ非常に大きな値になるようなペナルティ関数（罰金関数）Ｐ（ｒ）を導入し、新たな関数、すなわち問題を解決するために定式化された関数Ω（ｒ）＝Ｅ（ｒ）＋Ｐ（ｘ）を極小化するものである。ペナルティ関数の具体的な形としては、Ｐ（ｒ）＝ωＳ（ｒ）2などが考えられる。ここで、ωは正の数であり、極小値探索の過程で適当な値に調整される。
【０００９】
乗数法は、未定乗数λを導入し、ｒとλの新たな関数Ω（ｒ，λ）＝Ｅ（ｒ）
＋λＳ（ｒ）を停留化するものである。拘束条件は、λに対するΩ（ｒ）の停留条件
【００１０】
【数１０】
2005259061.tif 000004
として実現される。
【非特許文献１】大野豊・磯田和男監修「新版数値計算ハンドブック」（オーム社、１９９０）の第９章
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、従来の方法には、次のような問題がある。すなわち、ペナルティ法の場合は、ペナルティ関数の選び方に問題がある。例えば、Ｐ（ｒ）＝ωＳ（ｒ）2の場合、ωの値の調整をうまく行わないと、計算結果が正しい値に収束しなくなる。
【００１２】
また、ラグランジュの未定乗数法の場合は、探索すべき点はＥ（ｒ）の極小値であるはずなのに、一般には、探索された点はΩ（ｒ）の極小値ではなく、鞍点になってしまう。なお、鞍点の探索には、種々のアルゴリズムが考案されているが、極小値探索ほど簡単ではない。
【００１３】
本発明は、このような従来の技術的背景の下になされたもので、その課題は、拘束条件付き最適化問題の解を簡単な手順で求められるようにすることにある。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明は、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、点ｒを通る超曲面（多様体）Ｓ（ｒ）＝ｃの測地線に対して２次の接触をする曲線に沿った極小値探索過程とを用いている。
【００１５】
具体的には、図１に示したような手順を用いる。
（Ｓ１１）  点ｒの初期値設定：
r0を点ｒの初期値として、ｒ：＝r0とする。なお、本明細書において、：＝はこの：＝の左側に記載された変数（コンピュータプログラム中で値を変えることのできるデータ項目）に：＝の右側に記載された内容（数式の場合はその数式で得られる値）を格納することを意味するものとする。
（Ｓ１２）  超曲面Ｓ（ｒ）＝０への直線的接近：
超曲面Ｓ（ｒ）の勾配方向の直線は、ｔを媒介変数として、ｒ（ｔ）＝ｒ−
ｔ∇Ｓ（ｒ）と表わされる。点ｒの近傍では、Ｓ（ｒ−ｔ∇Ｓ（ｒ））＝
Ｓ（ｒ）−ｔ＜∇Ｓ（ｒ），∇Ｓ（ｒ）＞＋ｏ（ｔ）であるから、
【００１６】
【数１１】
2005259061.tif 000005
（Ｓ１３）  単位法線ベクトル：
点ｒを通る超曲面Ｓ（ｒ）＝ｃに垂直な単位法線ベクトルｎを、
【００１７】
【数１２】
2005259061.tif 000006
によって計算する。
（Ｓ１４）  実関数Ｅ（ｒ）の勾配ベクトル−∇Ｅ（ｒ）の接平面への射影：
実関数Ｅ（ｒ）の勾配ベクトル−∇Ｅ（ｒ）を点ｒを通る超曲面Ｓ（ｒ）＝ｃに対する接平面に射影した方向Ｇを、Ｇ：＝−∇Ｅ（ｒ）＋＜ｎ，∇Ｅ（ｒ）＞ｎによって計算する。
（Ｓ１５）  収束判定：
Ｇの大きさが判定基準となる数εより小さければ、極小に到達したものとみなして終了する。
（Ｓ１６）  測地線：
超曲面Ｓ（ｒ）＝ｃ上で、点ｒを通り、Ｇの方向に進む測地線は、ｔを媒介変数として、
ｒ（ｔ）＝ｒ＋ｔＧ＋ｔ2λｎ＋ｏ（ｔ2）の形に書ける。ここに、λは定数であり、次のように決定される。すなわち、点ｒの近傍では、
【００１８】
【数１３】
2005259061.tif 000007
が成り立つ。数式１３では、＜Ｇ，∇Ｓ（ｒ）＞＝０であることを用いた。ここに、Ｊはｉｊ成分が    
【００１９】
【数１４】
2005259061.tif 000008
で表わされる行列である。数式１３で、ｔ2の係数が０になるようにλの値を定めると、
【００２０】
【数１５】
2005259061.tif 000009
となる。
【００２１】
（Ｓ１７）  ２次曲線に沿っての点ｒの更新：
実関数Ｅ（ｒ）では、点ｒを通り、Ｇの方向に進む測地線に対して２次の接触をする２次曲線ｒ（ｔ）＝ｒ＋ｔＧ＋ｔ2λｎに沿った値は、
【００２２】
【数１６】
2005259061.tif 000010
となる。ここに、Ｋはｉｊ成分が
【００２３】
【数１７】
2005259061.tif 000011
で表わされる行列であり、ａ，ｂは、
【００２４】
【数１８】
2005259061.tif 000012
によって計算される数である。従って、ａ＞０の場合には、実関数Ｅ（ｒ（ｔ））の値は、ｔ＝−ｂ／２ａにおいて極小となる。点ｒの更新は、ｔが大きくなりすぎない範囲で、上記の極小に接近させるのがよい。すなわち、
【００２５】
【数１９】
2005259061.tif 000013
【００２６】
【数２０】
2005259061.tif 000014
【００２７】
【数２１】
2005259061.tif 000015
【００２８】
【数２２】
2005259061.tif 000016
であるから、
【００２９】
【数２３】
2005259061.tif 000017
とすることにより、点ｒを超曲面Ｓ（ｒ）＝０に接近させることができる。ここに、＜，＞はベクトル空間における内積、｜｜は内積によって誘導されるノルムを表す。
（Ｓ２３）  単位法線ベクトル：
点ｒを通る超曲面Ｓ（ｒ）＝ｃに垂直な単位法線ベクトルｎを、
【００３０】
【数２４】
2005259061.tif 000018
【数２５】
2005259061.tif 000019
が成り立つ。なお、数式２５では、＜Ｇi，∇Ｓ（ｒ）＞＝０であることを用いた。また、Ｊはｉｊ成分が
【００３１】
【数２６】
2005259061.tif 000020
【００３２】
【数２７】
2005259061.tif 000021
【００３３】
【数２８】
2005259061.tif 000022
となる。ここに、Ｋはｉｊ成分が
【００３４】
【数２９】
2005259061.tif 000023
で表わされる行列であり、ａ，ｂは、
【００３５】
【数３０】
2005259061.tif 000024
によって計算される数である。
【００３６】
従って、ａ＞０の場合には、実関数Ｅ（ｒ（ｔi））の値は、ｔi＝−ｂ／２ａにおいて極小となる。点ｒの更新は、ｔiが大きくなりすぎない範囲で、上記の極小に接近させるのがよい。すなわち、
【００３７】
【数３１】
2005259061.tif 000025
【００３８】
また、本発明に係る最適化方法は、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的漸近過程と、超曲面Ｓ（ｒ）＝ｃに対する接平面に射影した方向への極値探索過程とを含むものである。
【００３９】
なお、本発明は、例えば、容器の中に液体と気体、或いは２種類の液体があって、体積一定の条件のもとで界面形状を決定するような問題を解くのに特に有用である。
【００４０】
この問題の場合は、表面エネルギーと重力エネルギーの和を極小化する問題として定式化されるが、このような拘束条件付き最適化問題は、一般化すると、拘束条件Ｓ（ｒ）＝０の下で、定式化された実関数Ｅ（ｒ）を解く問題となる。
【００４１】
そこで、本発明に係る上記の直線的漸近過程、極値探索過程を含む最適化方法では、具体的には、図４、図５のような手順を用いている。
（Ｓ３１）  点ｒの初期値設定：
点ｒの初期値としてｒ0を設定する（ｒ：＝ｒ0）。
（Ｓ３２）  超曲面Ｓ（ｒ）への直線的接近：
超曲面Ｓ（ｒ）の勾配方向の直線は、ｔを媒介変数として、ｒ（ｔ）＝
ｒ−ｔ∇Ｓ（ｒ）となる。点ｒの近傍では、
【００４２】
【数３２】
2005259061.tif 000026
であるから、
【００４３】
【数３３】
2005259061.tif 000027
【数３４】
2005259061.tif 000028
によって計算する。
（Ｓ３４）  実関数Ｅ（ｒ）の勾配ベクトル−∇Ｅ（ｒ）の接平面への射影：
実関数Ｅ（ｒ）の勾配ベクトル−∇Ｅ（ｒ）を、点ｒを通る超曲面Ｓ（ｒ）＝ｃに対する接平面に射影した方向Ｇを、Ｇ：＝−∇Ｅ（ｒ）＋＜ｒ，∇Ｅ（ｒ）＞ｎによって計算する。
（Ｓ３５）  測地線：
超曲面Ｓ（ｒ）＝ｃ上で、点ｒを通り、Ｇの方向に進む測地線は、ｔを媒介変数として、ｒ（ｔ）＝ｒ＋ｔＧの形に書ける。この測値線に沿った場合の実関数Ｅ（ｒ）の値は、
【００４４】
【数３５】
2005259061.tif 000029
となる。ここに、Ｋはｉｊ成分が
【００４５】
【数３６】
2005259061.tif 000030
で表わされる行列である。数式３５で、＜Ｇ，ＫＧ＞  ＞０のとき、実関数Ｅ（ｒ）の値は、
【００４６】
【数３７】
2005259061.tif 000031
で極小となる。点ｒの更新は、ｔが大きくなり過ぎない範囲で、上記の極小に接近させるのがよい。すなわち、
【００４７】
【数３８】
2005259061.tif 000032
とすればよい。＜Ｇ，ＫＧ＞  ＜０のときには、実関数Ｅ（ｒ）に極小は無いので、移動量が大きくならない範囲で、この実関数が減少する方向に点ｒを移動させればよい。すなわち、
【００４８】
【数３９】
2005259061.tif 000033
【００４９】
【数４０】
2005259061.tif 000034
【発明の効果】
【００５０】
本発明によれば、拘束条件付き最適化問題の解を簡単な手順で求めることが可能となる。
【発明を実施するための最良の形態】
【００５１】
以下、本発明の実施の形態を図面に基づいて説明する。
【００５２】
図６は、本発明に係る最適化方法を適用したコンピュータシステムのシステム構成図である。
【００５３】
すなわち、本発明に係る最適化方法（アルゴリズム）は、図６に示したようなコンピュータシステムにより実行されるものである。
【００５４】
図６において、２２は汎用コンピュータの本体であり、ＣＰＵ、ＲＯＭ、ＲＡＭの他、フロッピー（登録商標）ディスク・ドライバ２６、ＣＤ−ＲＯＭドライバ２７、ハードディスク装置２８等を搭載している。また、本体２２は、モニタ装置２３、キーボード２４、マウス２５等の入出力装置とケーブルで接続されており、本体２２に対して各種のデータを入出力できるように構成されている。
【００５５】
本実施形態では、本発明に係る最適化アルゴリズムを含む最適化問題解法用のプログラムは、フロッピー（登録商標）ディスク２９に記録されている。このフロッピー（登録商標）ディスク２９に記録されている上記最適化問題解法用のプログラムは、フロッピー（登録商標）ディスク・ドライバ２６に装着し、フロッピー（登録商標）ディスク２９等に記録されている上記最適化問題解法用のプログラムを本体２２内にダウンロードし、ＲＡＭに展開して実行される。
【００５６】
上記最適化問題解法用のプログラムを実行中には、一定の探索間隔毎に極小値がモニタ２３に表示され、探索された極小値をリアルタイムに認識できるように構成されている。
【００５７】
図７は、図６に示したコンピュータシステムにより本発明に特有な処理を行うための機能を示す機能ブロック図である。
【００５８】
図７において、３０は演算処理装置であり、演算部３０ａ、演算処理手順記憶部３０ｂ、中間データ記憶部３０ｃ、データ出力部３０ｄ、及び上記最適化問題解法用のプログラムを演算部３０に入力するための入力部３０ｅにより横成されている。この演算部３０には入力装置３１、印刷装置３２、モニタ装置２６、及び外部記憶装置３３が接続されている。
【００５９】
図７に示した演算処理装置３０は、図６に示したコンピュータ本体２２に搭載されており、演算部３０ａは、少なくとも上記のＣＰＵを有している。演算処理手順記憶部３０ｂは、上記のＲＡＭにより構成され、上記のフロッピー（登録商標）ディスク・ドライバ２６、ＣＤ−ＲＯＭドライバ２７、ハードディスク装置２８等の外部記憶装置３３から読出された上記最適化問題解法用のプログラムが展開される。
【００６０】
演算部３０ａは、演算処理手順記憶部３０ｂに展開された最適化問題解法用のプログラムを実行する。その際、演算部３０ａは、中間の演算結果、及び最終的な演算結果を中間データ記憶都３０ｃに格納すると共に、最終的な演算結果を外部部記憶装置３３に保存する。また、演算部３０ａは、中間データ記憶都３０ｃに格納された最終的な演算結果を、データ出力部３０ｄを介してプリンタ３２により印刷させると共に、中間データ記憶都３０ｃに格納された中間の演算結果、及び最終的な演算結果を、データ出力部３０ｄを介してモニタ装置２６にリアルタイムに表示させる。
【００６１】
入力装置２３は、図６に示したキーボード２４、マウス２５等により構成され、本発明に係る最適化問題解法用のプログラム等の各種のアプリケーションプログラムの実行を指示したり、各種のコマンドやデータを入力したりするために用いられ、それらコマンド、データは、データ入力部３０ｅを介して演算処理装置３０に入力される。
【００６２】
［第１の実施形態］
次に、本発明の第１の実施形態を説明する。
【００６３】
第１の実施形態に係る拘束条件付き最適化アルゴリズムは、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、点ｒを通る超曲面Ｓ（r）＝ｃの測地線に対して２次の接触をする曲線に沿った極小値探索過程とを含むものであり、ここでは、２次元実ベクトル
【００６４】
【数４１】
2005259061.tif 000035
に対して、拘束条件Ｓ（ｒ）＝０のもとで実関数Ｅ（ｒ）を極小化する問題の例として、
【００６５】
【数４２】
2005259061.tif 000036
の場合について考える。この問題は、次のような手順（Ｓ１１１〜Ｓ１１８）で解くことができる。
（Ｓ１１１）  点ｒの初期値設定：
初期値ｘ(0)，ｙ(0)を用いてｘ：＝ｘ(0)，ｙ：＝ｙ(0)とする。
（Ｓ１１２）  超曲面Ｓ（ｒ）＝０への直線的接近：
【００６６】
【数４３】
2005259061.tif 000037
（Ｓ１１３）  点ｒを通る超曲面Ｓ（ｒ）＝ｃに対する単位法線ベクトルｎ：
【００６７】
【数４４】
2005259061.tif 000038
（Ｓ１１４）  実関数Ｅ（ｒ）の勾配ベクトルの接平面への射影：
【００６８】
【数４５】
2005259061.tif 000039
【００６９】
【数４６】
2005259061.tif 000040
（Ｓ１１７）  ２次曲線に沿っての点ｒの更新：
【００７０】
【数４７】
2005259061.tif 000041
（Ｓ１１８）  手順（Ｓ１１２）に戻る。
【００７１】
なお、計算例として、ａ＝２、ｂ＝１、ｘ0＝２．５、ｙ0＝０．５、ｄ＝０．５、ε＝１０-8の場合に、上記の手順を実行した結果を図８に示す。
【００７２】
図８に示したように、初期位置（２．５，０．５）から出発し、実関数Ｅ（ｘ，ｙ）を極小にする位置（０．０，１．０）に収束することとなる。
【００７３】
［第２の実施形態］
第２の実施形態に係る拘束条件付き最適化アルゴリズムは、第１の実施形態と同様に、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、点ｒを通る超曲面Ｓ（r）＝ｃの測地線に対して２次の接触をする曲線に沿った極小値探索過程とを含むものであり、ここでは、拘束条件Ｓ（ρ）＝０のもとで、実関数
【００７４】
【数４８】
2005259061.tif 000042
【００７５】
【数４９】
2005259061.tif 000043
で定義される関数であり、Ｔrは対和角を表すものとする。この問題は、ハミルトン行列Ｈで記述される独立Ｎｅ電子系の基底状態を求める問題を、密度行列を用いて定式化したものである（Ｘ−Ｐ．Ｌｉ，Ｒ．Ｗ．Ｎｕｅｓ  ａｎｄ  Ｄ．Ｖａｎｄｅｒｂｉｌｔ，Ｐｈｙｓｉｃａｌ  Ｒｅｖｉｅｗ  Ｂ，Ｖｏｌ．４７，ｐ．１０８９１，１９９３）。
【００７６】
この問題の解法としては、化学ポテンシャルを用いる方法（乗数法の一種とみなせる）が知られている（Ｓ−Ｙ．Ｑｉｕ，Ｃ．Ｚ．Ｗａｎｇ,Ｋ．Ｍ．Ｈｏ  ａｎｄ  Ｃ．Ｔ．Ｃｈａｎ，Ｊｏｕｒｎａｌ  ｏｆ  Ｐｈｙｓｉｃｓ：Ｃｏｎｄｅｎｓｅｄ  Ｍａｓｔｅｒ，Ｖｏｌ．６，ｐ．９１５３，１９９４）。
【００７７】
実対称行列ρをｍ（ｍ−１）／２個の独立な成分を持つベクトルと考え、２個の実対称行列ρ1とρ2の内積を＜ρ1，ρ2＞＝Ｔr（ρ1ρ2）で定義すると、この問題は、本発明に係る最適化アルゴリズムでは、次のような手順（Ｓ１２１〜Ｓ１２８）で解くことができる。
（Ｓ１２１）  実対称行列ρの初期値設定
初期値行列ρ(0)を用いて、ρ：＝ρ(0)とする。
（Ｓ１２２）  超曲面Ｓ（ρ）＝０への直線的接近：
【００７８】
【数５０】
2005259061.tif 000044
（Ｓ１２３）  点ρを通る超曲面Ｓ（ρ）＝ｃに対する単位法線ベクトル（ｍ×ｍ実対称行列）Ｎ：
【００７９】
【数５１】
2005259061.tif 000045
【００８０】
【数５２】
2005259061.tif 000046
（Ｓ１２８）  手順（Ｓ１２２）に戻る。
【００８１】
このように、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、点ｒを通る超曲面Ｓ（r）＝ｃの測地線に対して２次の接触をする曲線に沿った極小値探索過程とを含む最適化アルゴリズムを用いることにより、簡単な計算手順で拘束条件付き最適化問題の解を求めることができる。
【００８２】
［第３の実施形態］
第３の実施形態に係る最適化アルゴリズムは、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、次元数回、各座標系に対する単位ベクトルの超曲面Ｓ（ｒ）＝ｃへの射影方向に２次の接触をする曲線に沿った極値探索過程とを含むものであり、ここでは、２次元実ベクトル
【００８３】
【数５３】
2005259061.tif 000047
に対して、拘束条件Ｓ（ｒ）＝０のもとで実関数Ｅ（ｒ）を極小化する問題の例として、
【００８４】
【数５４】
2005259061.tif 000048
の場合について考える。この問題は、次のような手順（Ｓ１３１〜Ｓ１３８）で解くことができる。
（Ｓ１３１）  点ｒの初期値設定：
初期値ｘ(0)，ｙ(0)を用いてｘ：＝ｘ(0)，ｙ：＝ｙ(0)とする。
（Ｓ１３２）  超曲面Ｓ（ｒ）＝０への直線的接近：
【００８５】
【数５５】
2005259061.tif 000049
（Ｓ１３３）  点ｒを通る超曲面Ｓ（ｒ）＝ｃに対する単位法線ベクトルｎ：
【００８６】
【数５６】
2005259061.tif 000050
（Ｓ１３４）  方向ｉの単位ベクトルの接平面への射影（ｉ＝１，２）：
【００８７】
【数５７】
2005259061.tif 000051
（Ｓ１３５）  未知パラメータλ1の決定：
【００８８】
【数５８】
2005259061.tif 000052
（Ｓ１３６）  点ｒ（ｉ＝１，２）の更新：
【００８９】
【数５９】
2005259061.tif 000053
【００９０】
ａ＝２、ｂ＝１、ｘ0＝２．５、ｙ0＝０．５、ｄ＝０．１、ε＝１０-7として本手順を実行すると、第１の実施形態と同様に、図９のように、初期位置（２．５，０．５）から出発し、実関数Ｅ（ｘ，ｙ）を極小にする位置（０．０，１．０）に収束することとなる。
【００９１】
［第４の実施形態］
第４の実施形態に係る最適化アルゴリズムは、第３の実施形態と同様に、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、次元数回、各座標系に対する単位ベクトルの超曲面Ｓ（ｒ）＝ｃへの射影方向に２次の接触をする曲線に沿った極値探索過程とを含むものであり、ここでは、３次元実ベクトル
【００９２】
【数６０】
2005259061.tif 000054
に対して、拘束条件Ｓ（ｒ）＝０のもとで実関数Ｅ（ｒ）を極小化することを考える。
【００９３】
【数６１】
2005259061.tif 000055
【００９４】
【数６２】
2005259061.tif 000056
（Ｓ１４３）  単位法線ベクトル：
【００９５】
【数６３】
2005259061.tif 000057
【００９６】
【数６４】
2005259061.tif 000058
【００９７】
【数６５】
2005259061.tif 000059
【００９８】
【数６６】
2005259061.tif 000060
【００９９】
ａ＝３、ｂ＝２、ｃ＝１、ｘ0＝２．５、ｙ0＝２．５、ｚ0＝２．５、ｄ＝０．１、ε＝１０-7として本手順を実行すると、図１０のようになり、初期位置（２．５，２．５，２．５）から出発し、実関数Ｅ（ｘ，ｙ，ｚ）を極小にする位置（０，０，１）に収束することとなる。
【０１００】
このように、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的接近過程と、次元数回、各座標系に対する単位ベクトルの超曲面Ｓ（ｒ）＝ｃへの射影方向に２次の接触をする曲線に沿った極値探索過程とを含む最適化アルゴリズムを用いることにより、簡単な計算手順で拘束条件付き最適化問題の解を求めることができる。
【０１０１】
［第５の実施形態］
第５の実施形態に係る最適化アルゴリズムは、拘束条件としての超曲面Ｓ（ｒ）＝０への直線的漸近過程
【０１０２】
【数６７】
2005259061.tif 000061
と、超曲面Ｓ（ｒ）＝ｃに対する接平面に射影した方向への極値探索過程
【０１０３】
【数６８】
2005259061.tif 000062
とを含むものであり、ここでは、２次元ベクトルｒ＝（ｘ，ｙ）に対して、拘束条件Ｓ（ｒ）＝０のもとで、実関数Ｅ（ｒ）を極小化する問題について考える。
【０１０４】
【数６９】
2005259061.tif 000063
【０１０５】
【数７０】
2005259061.tif 000064
とすると、この問題は、次のような手順（Ｓ１５１〜Ｓ１５７）で解くことができる。
（Ｓ１５１）  点ｒの初期値設定：
初期値ｘ(0)，ｙ(0)を用いてｘ：＝ｘ(0)，ｙ：＝ｙ(0)とする。
（Ｓ１５２）  超曲面Ｓ（ｒ）＝０への直線的接近：
【０１０６】
【数７１】
2005259061.tif 000065
（Ｓ１５３）  点ｒを通る超曲面Ｓ（ｒ）＝ｃに対する単位法線ベクトルｎ：
【０１０７】
【数７２】
2005259061.tif 000066
（Ｓ１５４）  実関数Ｅ（ｒ）の勾配ベクトルの接平面への射影：
【０１０８】
【数７３】
2005259061.tif 000067
【０１０９】
【数７４】
2005259061.tif 000068
（Ｓ１５７）  手順（Ｓ１５２）に戻る。
【０１１０】
なお、計算例として、ａ＝２、ｂ＝１、ｘ0＝１．５、ｙ0＝１．８、ε＝１０-8の場合に、上記の手順を実行した結果を図１１に示す。
【０１１１】
図１１に示したように、初期位置（１．５，１．８）から出発し、実関数Ｅ（ｘ，ｙ）を極小にする位置（０．４，０．２）に収束している。
【０１１２】
［第６の実施形態］
第６の実施形態は、第５の実施形態と同様の最適化アルゴリズムを用いるものであり、ここでは、３次元ベクトルｒ＝（ｘ，ｙ，ｚ）に対して、拘束条件Ｓ（ｒ）＝０のもとで実関数Ｅ（ｒ）を極小化する問題の例として、
【０１１３】
【数７５】
2005259061.tif 000069
【０１１４】
【数７６】
2005259061.tif 000070
（Ｓ１６３）  単位法線ベクトル：
【０１１５】
【数７７】
2005259061.tif 000071
（Ｓ１６４）  実関数Ｅ（ｒ）の勾配ベクトルの接平面への射影：
【０１１６】
【数７８】
2005259061.tif 000072
【０１１７】
【数７９】
2005259061.tif 000073
【０１１８】
ａ＝２、ｂ＝２、ｃ＝１、ｘ0＝１．５、ｙ0＝１．８、ｚ0＝０．８、ε＝１０-8として本手順を実行すると、図１２のようになり、初期位置（１．５，１．８，０．８）から出発し、実関数Ｅ（ｘ，ｙ，ｚ）を極小にする位置（１／３，１／６，１／６）に収束することとなる。
【０１１９】
このように、第５，第６の実施形態においても、簡単な計算手順で拘束条件付き最適化問題を解くことができる。
【０１２０】
なお、本発明は、上記の実施形態に限定されることなく、例えば、パーソナルコンピュータ、大型コンピュータ（メインフレーム）など、科学技術計算、事務処理、制御用など、ソフトウェア次第で各種の用途に利用できる汎用コンピュータだけでなく、本発明に係る最適化アルゴリズムを搭載して最適化問題を専ら解く専用のコンピュータにも適用できるものである。
【０１２１】
また、請求項で示した機能、又は、実施形態の構成が持つ機能が達成できるものであればどのようなものであっても適用できるものである。例えば、以上の実施形態のソフト構成とハード構成は、適宜置き換えることができるものである。
【０１２２】
また、本発明の課題は、上記実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体（または記録媒体）を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、解決されることは言うまでもない。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム(ＯＳ)などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１２３】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。本発明を上記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【０１２４】
【図１】第１の発明における最適化方法（極小値探索処理）を示すフローチャートである。
【図２】第２の発明における最適化方法（極小値探索処理）を示すフローチャートである。
【図３】図２の続きのフローチャートである。
【図４】第３の発明における最適化方法（極小値探索処理）を示すフローチャートである。
【図５】図４の続きのフローチャートである。
【図６】本発明に係る最適化方法を適用したコンピュータシステムのシステム構成図である。
【図７】図６に示したコンピュータシステムにより本発明に特有な処理を行うための機能を示す機能ブロック図である。
【図８】第１の実施の形態における計算結果例を示した図である。
【図９】第３の実施の形態における計算結果例を示した図である。
【図１０】第４の実施の形態における計算結果例を示した図である。
【図１１】第５の実施の形態における計算結果例を示した図である。
【図１２】第６の実施の形態における計算結果例を示した図である。
【符号の説明】
【０１２５】
２２：コンピュータ本体
２３：モニタ装置
２４：キーボード
２５：マウス
２６：フロッピー（登録商標）ディスク・ドライバ
２７：ＣＤ−ＲＯＭドライバ
２８：ハードディスク装置
３０：演算処理装置
３０ａ：演算部
３０ｂ：演算処理手順記憶部
３０ｃ：中間データ記憶部
３０ｄ：データ出力部
３０ｅ：入力部
３１：入力装置
３２：印刷装置
３３：外部記憶装置
【図１】
2005259061.tif 000082
【図２】
2005259061.tif 000083
【図３】
2005259061.tif 000084
【図４】
2005259061.tif 000085
【図５】
2005259061.tif 000086
【図６】
2005259061.tif 000087
【図７】
2005259061.tif 000088
【図８】
2005259061.tif 000089
【図９】
2005259061.tif 000090
【図１０】
2005259061.tif 000091
【図１１】
2005259061.tif 000092
【図１２】
2005259061.tif 000093