(57)【要約】一般的非線形プログラミング問題の大域最適解を得るための方法は、決定論的に、条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの全ての安定平衡点を最初に求め、次に前記点から大域最適解を求めるステップを備える。大規模システムのための、動的分解点を確実に計算するための実用数値方法は、出口点を初期条件として使用し、検索経路が安定平衡点の安定化境界を抜ける出口点から出発する探索経路に沿って移動し、出口点を検出し、非線形システムを平衡点まで積分し、局所最適解に関する前記動的分解点を計算し、前記探索方向がｅであるステップを備える。【選択図】図１５
2005508026.tif 000002
【特許請求の範囲】
【請求項１】
一般的非線形プログラミング問題の大域最適解を得るための方法であって、
ａ）  決定論的に、全ての局所最適解を最初に求めるステップと、
ｂ）  次に前記局所最適解から大域最適解を求めるステップと、
を備えることを特徴とする方法。
【請求項２】
一般的非線形プログラミング問題の大域最適解を得るための方法であって、
ａ）  決定論的に、条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの全ての安定平衡点を最初に求めるステップと、
ｂ）  次に前記点から大域最適解を求めるステップと、
を備えることを特徴とする方法。
【請求項３】
大規模システムのための、動的分解点を確実に計算するための実用数値方法であって、
ａ）  ｘsから出発する探索経路
【数１】
2005508026.tif 000046
に沿って移動し、前記探索経路φt（ｘs）が安定平衡点ｘsの安定化領域を抜ける出口点ｘexを検出するステップと、
ｂ）  前記出口点ｘsを初期条件として使用して非線形システム（４．２）を平衡点ｘdまで積分するステップと、
ｃ）  局所最適解ｘsに関する前記動的分解点を計算し、前記探索方向がｅ ｘdであるステップと、
を備えることを特徴とする方法。
【請求項４】
前記出口点を計算するための方法が、
ｘsから出発する前記探索経路
【数２】
2005508026.tif 000047
に沿って移動し、前記探索経路φt（ｘs）に沿った、目的関数Ｃ（ｘ）の最初の局所最大である前記出口点ｘexを検出するステップ、
を備えることを特徴とする請求項３に記載の方法。
【請求項５】
最小距離点（ＭＤＰ）を計算するための方法が、
ａ）  前記出口点ｘexを初期条件として使用して非線形システム（４．２）をノルム‖Ｆ（ｘ）‖の最初の局所最小まで積分し、Ｆ（ｘ）がベクトルフィールド（４．２）のベクトルであり、局所最小点がｘ0dであるステップと、
ｂ）  前記ＭＤＰｘi,0d,jを初期推定とし使用して前記ベクトルフィールド（４．２）Ｆ（ｘ）＝０の非線形代数式の組を解き、解がｘd、前記局所最適解ｘsおよび前記探索経路φt（ｘs）に関する動的分解点がｘdであるステップと、
を備えることを特徴とする請求項３に記載の方法。
【請求項６】
前記出口点を計算するための方法が、
ｘsから出発する前記探索経路
【数３】
2005508026.tif 000048
に沿って移動することにより、各タイムステップにおける前記探索ベクトルとベクトルフィールドの内積を計算し、各タイムステップで、内積の符号が正から負に変わる時に前記出口点が検出されるような、前記探索ベクトルｓ＾とベクトルフィールドＦ（ｘ）の内積を計算するステップ、
を備えることを特徴とする請求項３に記載の方法。
【請求項７】
前記出口点を計算するための方法が、
ａ）  間隔［ｔ1,ｔ2］の間で内積の符号が変わるまで前記探索ベクトルに沿って移動するステップと、
ｂ）  線形補間を間隔［ｔ1,ｔ2］に適用して、補間された内積がゼロになると予想される中間時間ｔ0を生成するステップと、
ｃ）  前記値がしきい値より小さい場合に前記出口点が得られるような、ｔ0における正確な内積を計算するステップと、
ｄ）  前記内積が正の場合に、ｔ1をｔ0で置き換え、そうでない場合にはｔ2をｔ0で置き換えてステップｂ）に進むステップと、
を備えることを特徴とする請求項３に記載の方法。
【請求項８】
最小距離点（ＭＤＰ）を計算するための方法が、
ａ）  前記出口点を初期条件として使用して小数のタイムステップの間非線形システムを積分するステップと、
ｂ）  収束基準を検査し、ステップａ）で得られた前記出口点のノルムがしきい値より小さい場合に、前記点を前記ＭＤＰとして宣言し、そうでない場合にはステップｂ）に立ち止まるステップと、
ｃ）  軌跡上の現在点と局所最適解を結ぶ線を引き、前記現在点を、安定平衡点から出発する前記線に沿った、目的関数の最初の局所最大点である、訂正された出口点で置き換え、この点を前記出口点に代入し、ステップａ）に戻るステップと、
を備えることを特徴とする請求項３に記載の方法。
【請求項９】
安定平衡点ｘsおよび探索ベクトルｓ＾に関する前記動的分解点を計算するための方法が、
ａ）  ｘsから出発する前記探索経路
【数４】
2005508026.tif 000049
に沿って移動し、間隔［ｔ1,ｔ2］の間で前記探索ベクトルｓ＾とベクトルフィールドＦ（ｘ）の内積の符号が変化する瞬間を検出し、ｔ1がしきい値より大きい場合にはこのステップに立ち止まってこの探索経路に沿って近傍局所最適解がないことを報告し、そうでない場合にはステップｂ）に進むステップと、
ｂ）  線形補間を前記間隔［ｔ1,ｔ2］に適用して前記補間された内積がゼロになると予想される中間時間ｔ0を生成し、ｔ0における正確な内積を計算し、前記値がしきい値より小さい場合に前記出口点が得られてステップｄ）に進むステップと、
ｃ）  前記内積が正である場合にｔ1をｔ0で置き換え、そうでない場合にはｔ2をｔ0で置き換えてステップｂ）に戻るステップと、
ｄ）  前記出口点を初期条件として使用して小数のタイムステップの間非線形システムを積分するステップと、
ｅ）  収束基準を検査し、ステップｄ）で得られた前記出口点のノルムがしきい値より小さい場合に、前記点を前記ＭＤＰとして宣言してステップｇ）に進み、そうでない場合にはステップｅ）に立ち止まるステップと、
ｆ）  前記軌跡上の現在点と局所最適解を結ぶ線を引き、前記現在点を、安定平衡点から出発する前記線に沿った、目的関数の最初の局所最大点である、訂正された出口点で置き換え、この点を前記出口点に代入してステップｄ）に戻るステップと、
ｇ）  前記ＭＤＰを初期推定とし使用して前記ベクトルフィールド（４．２）Ｆ（ｘ）＝０の非線形代数式の組を解き、局所最適解ｘsおよびベクトルｓ＾に関する前記ＤＤＰがｘdであるような解がｔdであるステップと、
を備えることを特徴とする請求項３に記載の方法。
【請求項１０】
少なくとも一つの有効局所探索方法が、請求項３に記載の前記動的軌跡方法と組み合わされ、
ａ）  初期点を与えられると、条件（Ｃ１）を充足する、(４．２)によって記述された非線形動的システムを初期点から少数のタイムステップの間積分して終点を得、ステップｂ）に進む前に終点を使って前記初期点を更新するステップと、
ｂ）  有効局所オプティマイザをステップａ）における前記終点から適用して前記探索処理を継続し、収束する場合には立ち止まり、そうでない場合にはステップａ）に戻るステップと、
を備えることを特徴とする請求項３に記載の方法。
【請求項１１】
前記方法が、
ａ）  局所最適解から脱出することと、
ｂ）  別の局所最適解の存在を保証することと、
ｃ）  ステップｂ）の局所最適解の再訪を回避することと、
ｄ）  ステップｂ）の局所最適解の探索を支援することと、
ｅ）  探索経路に沿って別の近傍局所最適解が存在しないことを保証することと、
からなるグループから選択された結果を実現するために使用されることを特徴とする請求項３に記載の方法。
【請求項１２】
ある局所最適解から探索して決定論的に別の局所最適解を求める手順を実行するための数値方法が、
ａ）  ｘoptから出発する探索経路に沿って移動し、前記ＤＤＰ探索方法を適用して対応するＤＤＰを計算し、ステップｂ）に戻り、ＤＤＰを求めることができない場合には、別の探索経路を試みてこのステップを繰り返すステップと、
ｂ）  前記ＤＤＰをｘdとして表し、ｘdが前に求められている場合にはステップａ）に戻り、そうでない場合にはステップｃ）に進むステップと、
ｃ）  εが小さい数である、ＤＤＰに基づく初期点ｘ0＝ｘopt＋（１＋ε）（ｘd−ｘopt）を計算し、ｘ0から出発してハイブリッド探索方法を適用し、対応する近傍局所最適解を求めるステップと、
を備えることを特徴とする請求項３に記載の方法。
【請求項１３】
一般的非線形プログラミング問題の大域最適解を得るための方法であって、
ａ）  決定論的に、全ての局所最適解を最初に求めるステップと、
ｂ）  次に前記局所最適解から大域最適解を求めるステップと、
を備えることを特徴とする方法。
【請求項１４】
一般的制約条件なし非線形プログラミング問題の大域最適解を得るための方法であって、
ａ）  決定論的に、条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの全ての安定平衡点を最初に求めるステップと、
ｂ）  次に前記点から大域最適解を求めるステップと、
を備えることを特徴とする方法。
【請求項１５】
大規模非線形システムのための、安定平衡点の動的分解点を確実に計算するための実用数値方法であって、
ａ）安定平衡点ｘsを与えられるステップと、
ｂ）ｘsから出発する探索経路
【数５】
2005508026.tif 000050
に沿って移動し、前記探索経路φt（ｘs）が安定平衡点ｘsの安定化境界を抜ける出口点ｘexを検出するステップと、
ｃ）  前記出口点ｘsを初期条件として使用して非線形システム（４．２）を平衡点ｘdに積分するステップと、
ｄ）  前記安定平衡点ｘsに関する前記動的分解点を計算し、前記探索方向ｓ＾がｅ ｘdであるステップと、
を備えることを特徴とする方法。
【請求項１６】
前記非線形システム（４．３）の前記出口点を計算するための方法が、
ｘsから出発する前記探索経路
【数６】
2005508026.tif 000051
に沿って移動し、前記探索経路φt（ｘs）に沿った、目的関数Ｃ（ｘ）の最初の局所最大である前記出口点ｘexを検出するステップ、
を備えることを特徴とする請求項３に記載の方法。
【請求項１７】
動的分解点を計算するための方法が、
ａ）  前記出口点ｘexを初期条件として使用して前記対応する軌跡に沿った、非線形システム（４．２）をノルム‖Ｆ（ｘ）‖の最初の局所最小まで積分し、Ｆ（ｘ）が（４．２）のベクトルフィールドであり、‖Ｆ（ｘ）‖の前記最初の局所最小が発生する点をｘ0dとして表し、前記最小距離点（ＭＤＰ）と呼ばれるステップと、
ｂ）  前記ＭＤＰｘ0dを初期推定とし使用して前記ベクトルフィールド（４．２）Ｆ（ｘ）＝０の非線形代数式の組を解き、解がｘd、および前記局所最適解ｘsと前記探索経路φt（ｘs）に関する動的分解点がｘdであるステップと、
を備えることを特徴とする請求項１５に記載の方法。
【請求項１８】
前記非線形システム（４．２）の安定平衡点および探索ベクトルに関する前記出口点を計算するための方法が、
ｘxから出発する前記探索経路
【数７】
2005508026.tif 000052
に沿って移動することにより、各タイムステップにおける前記探索ベクトルとシステム（４．３）の前記ベクトルフィールドの内積を計算し、各タイムステップで、前記内積の符号が正から負に変わる時に前記出口点が検出されるような、前記探索ベクトルｓ＾とベクトルフィールドＦ（ｘ）の内積を計算するステップ、
を備えることを特徴とする請求項１５に記載の方法。
【請求項１９】
安定平衡点および探索ベクトルに関する、非線形システム（４．３）の前記出口点を計算するための方法が、
ａ）  間隔［ｔ1,ｔ2］の間で前記探査ベクトルとシステム（４．３）の前記ベクトルフィールドの内積の符号が変わるまで前記探索ベクトルに沿って前記安定平衡点から移動するステップと、
ｂ）  線形補間を間隔［ｔ1,ｔ2］に適用して、補間された内積がゼロになると予想される中間時間ｔ0を生成するステップと、
ｃ）  前記値がしきい値より小さい場合に前記出口点が得られるような、ｔ0における正確な内積を計算するステップと、
ｄ）  前記内積が正の場合に、ｔ1をｔ0で置き換え、そうでない場合にはｔ2をｔ0に置き換えてステップｂ）に戻るステップと、
を備えることを特徴とする請求項１５に記載の方法。
【請求項２０】
条件（Ｃ１）および（Ｃ２）を充足する前記非線形システム（４．２）の最小距離点（ＭＤＰ）を計算するための方法が、
ａ）  前記出口点を初期条件として使用して小数のタイムステップの間前記非線形システム（４．２）を積分し、前記終点を前記現在出口点として表すステップと、
ｂ）  収束基準を検査し、ステップａ）で得られた前記現在出口点のノルムがしきい値より小さい場合に、前記点を前記ＭＤＰとして宣言し、そうでない場合にはステップｃ）に進むステップと、
ｃ）  軌跡上の現在出口点と局所最適解（すなわち安定平衡点）を結ぶ線を引き、前記現在出口点を、前記安定平衡点から出発する前記線に沿った目的関数の最初の局所最大点である、訂正された出口点で置き換え、この点を前記出口点に代入してステップａ）に戻るステップと、
を備えることを特徴とする請求項１５に記載の方法。
【請求項２１】
安定平衡点ｘsおよび探索ベクトルｓ＾に関する、条件（Ｃ１）および（Ｃ２）を充足する前記非線形システム（４．２）の前記動的分解点を計算するための方法が、
ａ）  ｘxから出発する前記探索経路
【数８】
2005508026.tif 000053
に沿って移動し、間隔［ｔ1,ｔ2］の間で前記探索ベクトルｓ＾と非線形システム（４．２）の前記ベクトルフィールドＦ（ｘ）の内積の符号が変化する瞬間を検出し、ｔ1がしきい値より大きい場合にこのステップに立ち止まって、この探索経路に沿って近傍局所最適解がないことを報告し、そうでない場合にはステップｂ）に戻るステップと、
ｂ）  線形補間を前記間隔［ｔ1,ｔ2］に適用して補間された内積がゼロになると予想される中間時間ｔ0を生成し、ｔ0における正確な内積を計算し、前記値がしきい値より小さい場合に前記出口点が得られてステップｄ）に進むステップと、
ｃ）  前記内積が正である場合に、ｔ1をｔ0で置き換え、そうでない場合にはｔ2をｔ0で置き換えてステップｂ）に戻るステップと、
ｄ）  前記出口点を初期条件として使用して小数のタイムステップの間非線形システム（４．２）を積分し、前記終点を前記現在出口点として表すステップと、
ｅ）  収束基準を検査し、ステップｄ）で得られた前記点のノルムがしきい値より小さい場合に、前記点を前記ＭＤＰとして宣言してステップｇ）に進み、そうでない場合にはステップｅ）に立ち止まるステップと、
ｆ）  前記軌跡上の現在出口点と安定平衡点を結ぶ線を引き、前記現在点を、前記安定平衡点から出発する前記線に沿った、目的関数の最初の局所最大点である、訂正された出口点で置き換え、この点を前記出口点に代入してステップｄ）に戻るステップと、
ｇ）  前記ＭＤＰを初期推定とし使用して前記ベクトルフィールド（４．２）Ｆ（ｘ）＝０の非線形代数式の組を解き、安定平衡点ｘsおよび探索ベクトルｓ＾に関する前記ＤＤＰがｘdであるような解がｔdであるステップと、
を備えることを特徴とする請求項１５に記載の方法。
【請求項２２】
任意の初期点から出発する、研究中の制約条件なし非線形プログラミング問題（４．１）の局所最適解を得るための方法であって、
ａ）  初期点を与えられるステップと、
ｂ）  有効な積分方法を適用して、条件（Ｃ１）および（Ｃ２）を充足する、(４．２)によって記述された非線形動的システムを前記平衡点から積分し、前記非線形動的システム（４．２）の安定平衡点、すなわち研究中の前記制約条件なし非線形プログラミング問題（４．１）の局所最適解に収束する軌跡を得るステップと、
を備えることを特徴とする方法。
【請求項２３】
任意の初期点から出発する、一般的制約条件なし非線形プログラミング問題（４．１）の局所最適解を得るためのハイブリッド探索方法であって、
ａ）  初期点ｘ0を与えられるステップと、
ｂ）  条件（Ｃ１）および（Ｃ２）を充足する、(４．２)によって記述された非線形動的システムを前記初期点ｘ0から積分し、ｎタイムステップ（ｎは整数）の間軌跡φt（ｘ0）を得、最後のタイムステップ点を終点として記録し、局所最適解に収束する場合には立ち止まり、そうでない場合にはステップｃ）に進むステップと、
ｃ）  研究中の目的関数における値の減少率に関して前記軌跡φt（ｘ0）に沿って所望の収束実行基準を監視し、前記所望の基準が充足される場合、軌跡φt（ｘ0）の終点を前記初期点として使ってステップｂ）に進み、そうでない場合にはステップｄ）に進むステップと、
ｄ）  有効局所オプティマイザ（すなわち局所最適解を求める方法）をステップｂ）における前記終点から適用して前記探索処理を継続し、局所最適解が求められれば立ち止まり、そうでない場合には軌跡φt（ｘ0）の前記終点を前記初期点として設定し、ステップｂ）に戻るステップと、
を備えることを特徴とする方法。
【請求項２４】
前記方法が、
ａ）  局所最適解から脱出することと、
ｂ）  別の局所最適解の存在を保証することと、
ｃ）  局所最適解の再訪を回避することと、
ｄ）  局所最適解の探索を支援することと、
ｅ）  探索経路に沿って別の近傍局所最適解が存在しないことを保証することと、
からなるグループから選択された結果を実現するために使用されることを特徴とする請求項１４に記載の方法。
【請求項２５】
局所最適解ｘoptから探索して決定論的に別の局所最適解を求める手順を実行するための数値方法が、
ａ）  ｘoptから出発する探索経路に沿って移動し、ＤＤＰ探索方法を適用して対応するＤＤＰを計算し、ＤＤＰを求めることができる場合にはステップｂ）に戻り、そうでない場合には別の探索経路を試みてこのステップを繰り返すステップと、
ｂ）  前記ＤＤＰをｘdとして表し、ｘdが前に求められている場合はステップａ）に戻り、そうでない場合にはステップｃ）に進むステップと、
ｃ）  εが小さい数であるｘ0＝ｘopt＋（１＋ε）（ｘd−ｘopt）を設定し、ｘ0から出発してハイブリッド探索方法を適用し、対応する近傍局所最適解を求めるステップと、
を備えることを特徴とする請求項１４に記載の方法。
【請求項２６】
制約条件なし非線形最適化問題の大域最適解を得るための方法であって、
ａ）  出発点を選択するステップと、
ｂ）  前記出発点を使用し請求項２３のハイブリッド探索方法を適用して局所最適解ｘ0s  (156)  を求めるステップと、
ｃ）  ｊ＝０，Ｖs＝｛ｘ0s｝，Ｖjnew＝｛ｘ0s｝およびＶd＝｛φ｝を設定するステップと、
ｄ）  設定されたＶj+1new＝｛φ｝およびＶjnew（すなわちｘjs）における各局所最適解に対し、ステップ（ｅ）から（ｋ）を実行するステップと、
ｅ）  探索ベクトルＳji，ｉ＝１，２，．．．，ｍjの集合を定義してｉ＝１を設定するステップと、
ｆ）  ｉ＞ｍjである場合、ステップ（ｌ）に進み、そうでない場合には前記探索ベクトルＳjiに沿ってＤＤＰ探索方法を適用して対応する動的分解点（ＤＤＰ）を求め、ＤＤＰが求められればステップ（ｇ）に進み、そうでない場合にはｉ＝ｉ＋１を設定してステップ（ｆ）に立ち止まるステップと、
ｇ）  前記求められたＤＤＰをｘjd,iとして表し、前記ＤＤＰが前記集合Ｖdに属するかどうか、すなわちＶd，ｉ．ｅ.，ｘjd,i∈Ｖd？を検査し、属する場合にはｉ＝ｉ＋１を設定してステップ（ｆ）に戻り、そうでない場合にはＶd＝Ｖd∪｛ｘjd,i｝を設定してステップ（ｈ）に進むステップと、
ｈ）  前記ＤＤＰｘjd,iに対し、ステップ（ｉ）から（ｊ）を実行して対応する近傍局所最適解を求めるステップと、
ｉ）  εが小さい数であるｘj0,i＝ｘjs＋（１＋ε）（ｘjd,i−ｘjs）とするステップと、
ｊ）  ｘj0,iを前記初期条件として使用し前記ハイブリッド探索方法を適用して対応する局所最適解を求め、それをｘis,jとして表すステップと、
ｋ）  ｘis,jが前に求められているかどうか、すなわちｉ．ｅ.，ｘis,j∈Ｖs？を検査し、既に求められている場合にはｉ＝ｉ＋１を設定してステップ（ｆ）に戻り、そうでない場合にはＶs＝Ｖs∪｛ｘis,j｝及びＶj+1new＝Ｖj+1new∪｛ｘis,j｝を設定し、さらにｉ＝ｉ＋１を設定してステップ（ｆ）に戻るステップと、
ｌ）  新しく計算された全ての局所最適解の集合Ｖj+1newを調査し、Ｖj+1newが空でない場合はｊ＝ｊ＋１を設定してステップ（ｄ）に戻り、そうでない場合には次のステップに進むステップと、
ｍ）  前記局所最適解の集合Ｖsから、集合Ｖsにおけるそれらの対応する目的関数の値を比較することによって大域最適解を識別するステップと、
を備えることを特徴とする方法。
【請求項２７】
（４．５）によって記述された一般的制約条件付き非線形プログラミング問題の大域最適解を得るための方法であって、
ａ）  変換方法を使って制約条件付き最適化問題を制約条件なし最適化問題に変換するステップと、
ｂ）  請求項１４の方法を適用して前記変換された制約条件なし最適化問題を解くステップと、
を備えることを特徴とする方法。
【請求項２８】
制約条件付き非線形プログラミング問題（４．５）の大域最適解を得るための方法であって、
ａ）  フェーズＩ：前記問題の全ての実行可能成分を求め、
ｂ）  フェーズＩＩ：  各実行可能成分における全ての局所最適解を求める、
二つのフェーズを備えることを特徴とする方法。
【請求項２９】
ａ）  制約条件付き最適化問題（４．５）の経路接続された実行可能成分に接近するステップと、
ｂ）  前記経路接続された実行可能成分から脱出し、前記制約条件付き最適化問題（４．５）の経路接続された別の実行可能成分に接近するステップと、
を備えることを特徴とする請求項２８に記載の方法。
【請求項３０】
ａ）  条件（Ｃ１−１）および（Ｃ１−２）を充足する非線形動システム（４．９）の安定平衡多様体に接近するステップと、
ｂ）  前記安定平衡多様体から脱出し、条件（Ｃ１−１）および（Ｃ１−２）を充足する前記非線形動的システム（４．９）の別の安定平衡多様体に接近するステップと、
を備えることを特徴とする請求項２８に記載の方法。
【請求項３１】
ａ）  実行可能成分における点から出発し、最適化問題（４．７）の前記実行可能成分に配置された局所最適解に接近するステップと、
ｂ）  前記局所最適解から脱出し、前記最適化問題（４．７）の前記実行可能成分の別の局所最適解に接近するステップと、
を備えることを特徴とする請求項２８に記載の方法。
【請求項３２】
一般的制約条件付き非線形プログラミング問題の大域最適解を得るための方法であって、
ａ）  決定論的に、条件（Ｃ１−１）および（Ｃ１−２）を充足する非線形動的システムの全ての安定平衡多様体を最初に求めるステップと、
ｂ）  決定論的に、条件（Ｃ２−１）および（Ｃ２−２）を充足する非線形動的システムの全ての安定平衡点を求めるステップと、
ｃ）  次に前記安定平衡点から大域最適解を求めるステップと、
を備えることを特徴とする方法。
【請求項３３】
ａ）  制約条件付き非線形プログラミング問題（４．５）の実行可能解を与えられるステップと、
ｂ）  条件（Ｃ２−１）および（Ｃ２−２）を充足する非線形動的システム（４．１０）の安定平衡点を求めるステップと、
ｃ）  局所最適解から脱出するために、前記安定平衡点から動的分解点に移動するステップと、
ｄ）  経路接続された同じ実行可能成分における、条件（Ｃ２−１）および（Ｃ２−２）を充足する前記非線形動的システム（４．１０）の別の安定平衡点に、前記動的分解点を介して接近するステップと、
を備えることを特徴とする請求項２８に記載の方法。
【請求項３４】
任意の初期点から出発し、研究中の制約条件付き非線形プログラミング問題（４．５）の実行可能点を得るための方法であって、
ａ）  初期点を与えられるステップと、
ｂ）  有効な積分方法を適用して、条件（Ｃ１−１）および（Ｃ１−２）を充足する、（４．９）によって記述された非線形動的システムを前記初期点から積分し、前記問題（４．５）の実行可能解に収束する軌跡を得るステップと、
を備えることを特徴とする方法。
【請求項３５】
実行可能解から出発する、研究中の非線形プログラミング問題（４．５）の局所最適解を得るための方法であって、
ａ）  実行可能解を与えられるステップと、
ｂ）  有効な積分方法を適用して、条件（Ｃ２−１）および（Ｃ２−２）を充足する、（４．１０）によって記述された非線形動的システムを前記実行解から積分し、（４．１０）の安定平衡点、すなわち研究中の前記問題（４．５）の局所最適解に収束する軌跡を得るステップと、
を備えることを特徴とする方法。
【請求項３６】
請求項２８に記載のフェーズＩのためのハイブリッド探索方法であって、一つの有効局所方法が前記動的軌跡方法と組み合わされ、前記制約条件付き最適化問題（４．７）の実行可能解を求めるために、
ａ）  初期点ｘ0を与えられるステップと、
ｂ）  条件（Ｃ１−１）および（Ｃ１−２）を充足する、（４．９）によって記述された非線形動的システムを前記初期点から積分し、ｎタイムステップ（ｎは整数）の間軌跡φt（ｘ0）を得、最後のタイムステップ点を終点として記録し、実行可能解に収束する場合は立ち止まり、そうでない場合はステップｃ）に進むステップと、
ｃ）  目的関数‖Ｈ（ｘ）‖において所望の収束実行基準、すなわち（４．７）におけるＨ（ｘ）のベクトルノルムを監視し、前記所望の基準が充足される場合に、軌跡φt（ｘ0）の前記終点を前記初期点として使ってステップｂ）に戻り、そうでない場合にはステップｄ）に進むステップと、
ｄ）  有効方法をステップｂ）における前記終点から適用して前記探索処理を継続し、（４．７）の実行可能解が求められる場合は立ち止まり、そうでない場合には軌跡φt（ｘ0）の前記終点を前記初期点として設定してステップｂ）に戻るステップと、
を備えることを特徴とする方法。
【請求項３７】
請求項２８に記載のフェーズＩＩのためのハイブリッド探索方法であって、前記制約条件付き最適化問題（４．７）の局所最適解を求めるために、
ａ）  実行可能点ｘ0を与えられるステップと、
ｂ）  条件（Ｃ２−１）および（Ｃ２−２）を充足する、（４．１０）によって記述された非線形動的システムを前記初期点から積分し、ｎタイムステップ（ｎは整数）の間軌跡φt（ｘ0）を得、最後のタイムステップ点を終点として記録し、局所最適解に収束する場合は立ち止まり、そうでない場合はステップ（ｃ）に進むステップと、
ｃ）  （４．５）の目的関数（０）において所望の収束実行基準を監視し、前記所望の基準が充足される場合、軌跡φt（ｘ0）の前記終点を前記初期点として使用してステップｂ）に戻り、そうでない場合にはステップｄ）に進むステップと、
ｄ）  有効方法をステップｂ）における前記終点から適用して前記探索処理を継続し、（４．７）の実行可能解が求められる場合は立ち止まり、そうでない場合には軌跡φt（ｘ0）の前記終点を前記初期点として設定してステップｂ）に進むステップと、
を備えることを特徴とする方法。
【請求項３８】
ａ）  出発点を選択するステップと、
ｂ）  初期化ｊ＝０を行うステップと、
ｃ）  前記出発点を使用しフェーズＩのためのハイブリッド探索方法を適用して（経路接続された）実行可能成分における実行可能点を求め、フェーズＩＩのためのハイブリッド探索方法を適用して局所最適解  ｘjs,0を求めるステップと、
ｄ）  前記初期点ｘjs,0から出発し、フェーズＩＩのための数値方法を適用して前記実行可能成分における全ての局所最適解を求め、それらを集合Ｖjsとして記録し、Ｖs＝Ｖs∪Ｖjsを設定するステップと、
ｅ）  前記局所最適解ｘjs,0に対して、探索ベクトルＳji  ｉ＝１，２，．．．ｋjの集合を定義するステップと、
ｆ）  ｉ＞ｋjである場合、ステップ（ｌ）に進み、そうでない場合にはステップ（ｇ）に進むステップと、
ｇ）  各探索ベクトル（Ｓji）に対し、逆行時間軌跡方法を適用してシステム（４．９）の不安定平衡多様体に存在する点を求め、点が求められた場合には、それをｘid,jとして表してステップ（ｈ）に進み、そうでない場合にはｉ＝ｉ＋１を設定してステップ（ｆ）に戻るステップと、
ｈ）  εが小さい数であり、ｘjsがステップ（ｅ）において選択された局所最適解であるｘj0,i＝ｘjs＋（ｉ＋ε）（ｘid,j−ｘjs）を設定し、ｘj0,iを前記初期
点として使用してフェーズのためのハイブリッド探索方法を適用して、条件（Ｃ１−１）および（Ｃ１−２）を充足するシステム（４．９）の安定平衡多様体に存在する点を求め、前記解をｘ0s,jとして表すステップと、
ｉ）  前記初期点ｘ0s,jから出発してフェーズＩＩのためのハイブリッド探索方法を適用し、前記（経路接続された）実行可能成分ｘj+1s,0における局所最適解を求めるステップと、
ｊ）  ｘj+1s,0が前に求められているかどうか、すなわちｘj+1s,0∈Ｖs？を検査し、前に求められている（すなわち、前記実行可能成分が前に訪問されている）場合は、ｉ＝ｉ＋１を設定してステップ（ｆ）に戻り、そうでない場合にはＶs＝Ｖs∪｛ｘjs,0｝およびＶj+1new＝Ｖj+1new∪｛ｘj+1s,0｝を設定してステップ（ｋ）に進むステップと、
ｋ）  前記初期点ｘj+1s,0から出発し、フェーズＩＩのための数値方法を適用して前記実行可能成分における全ての局所最適解を求め、それらを集合Ｖj+1sに記録し、Ｖs＝Ｖs∪Ｖj+1sを設定し、さらにｉ＝ｉ＋１を設定してステップ（ｆ）に戻るステップと、
ｌ）  新しく計算された全ての局所最適解の集合Ｖj+1newを調査し、Ｖj+1newが空である場合は次のステップに進み、そうでない場合にはｊ＝ｊ＋１を設定してステップ（ｅ）に戻るステップと、
ｍ）  前記局所最適解の集合Ｖsから、それらの目的関数の値を比較することによって前記大域最適解を識別するステップと、
を備えることを特徴とする請求項２８に記載の方法。
【請求項３９】
請求項２８に記載のフェーズＩＩのための数値方法であって、前記経路接続された実行可能成分における全ての局所最適解を求めるために、
ａ）  前記経路接続された実行可能成分に存在する初期点を与えられるステップと、
ｂ）  初期化を行うステップと、
ｃ）  前記初期点を使用しフェーズＩＩのためのハイブリッド探索方法を適用して局所最適解  ｘ0sを求め、ｊ＝０，Ｖs＝｛ｘ0s｝，Ｖjnew,II＝｛ｘ0s｝およびＶd＝｛φ｝を設定するステップと、
ｄ）  Ｖjnewにおける各局所最適解（すなわち Ｘjsに対してステップ（ｅ）から（ｋ）を実行するステップと、
ｅ）  探索ベクトルＳji，ｉ＝１，２，．．．ｍjの集合を定義し、ｉ＝１を設定するステップと、
ｆ）  ｉ＞ｍjである場合ステップ（ｌ）に進み、そうでない場合にはＤＤＰ探索方法を適用し、非線形動的システム（４．１０）が条件（Ｃ２−１）および（Ｃ２−２）を充足して対応する動的分解点（ＤＤＰ）を求め、ＤＤＰが求められた場合はステップ（ｇ）に進み、そうでない場合はｉ＝ｉ＋１を設定してステップ（ｆ）に立ち止まるステップと、
ｇ）  前記求められたＤＤＰをＸjd,iとして表し、前記ＤＤＰが集合Ｖdに属するかどうか、すなわちＸjd,i∈Ｖd？を検査し、属する場合はｉ＝ｉ＋１を設定してステップ（ｆ）に戻り、そうでない場合にはＶd＝Ｖd∪｛ｘjd,i｝を設定してステップ（ｈ）に進むステップと、
ｈ）  前記ＤＤＰｘjd,iに対し、ステップ（ｉ）から（ｊ）を実行して対応する近傍局所最適解を求めるステップと、
ｉ）  εが小さい数であるｘj0,i＝ｘjs＋（１＋ε）（ｘjd,i−ｘjs）を設定するステップと、
ｊ）  ｘj0,iを前記初期条件として使用しハイブリッド探索方法を適用して前記対応する局所最適解を求め、それをｘis,jとして表すステップと、
ｋ）  ｘis,jが前に求められているかどうか、すなわちｘis,j∈Ｖs？を検査し、前に求められている場合は、ｉ＝ｉ＋１を設定してステップ（ｆ）に戻り、そうでない場合にはＶs＝Ｖs∪｛ｘis,j｝およびＶj+1new＝Ｖj+1new∪｛ｘis,j｝を設定し、さらにｉ＝ｉ＋１を設定してステップ（ｆ）に戻るステップと、
ｌ）  新しく計算された全ての局所最適解の集合Ｖj+1new,IIを調査し、Ｖj+1new,IIが空でない場合にはｊ＝ｊ＋１を設定してステップ（ｄ）に戻り、そうでない場合には集合Ｖsに含まれた、前記経路接続された実行可能成分における全ての局所最適解を出力して処理を停止するステップと、
を備えることを特徴とする方法。
【請求項４０】
制約条件付き非線形プログラミング問題の大域最適解を得るための方法であって、
ａ）  変換手法を使用して制約条件付き最適化問題を制約条件なし最適化問題に変換し、前記制約条件なし最適化問題の前記大域最適解を求めるために以下のステップを適用するステップと、
ｂ）  出発点を選択するステップと、
ｃ）  前記出発点を使用しハイブリッド探索方法を適用して局所最適解ｘ0sを求めるステップと、
ｄ）  ｊ＝０、Ｖs＝｛ｘ0s｝，Ｖjnew＝｛ｘ0s｝およびＶd＝｛φ｝を設定するステップと、
ｅ）  Ｖj+1new＝｛φ｝を設定し、Ｖj+1new（すなわちｘjs ）における各局所最適解に対してステップ（ｅ）から（ｋ）を実行するステップと、
ｆ）  探索ベクトルＳji，ｉ＝１，２，．．．ｍjの集合を定義して、ｉ＝１を設定するステップと、
ｇ）  ｉ＞ｍjである場合ステップ（ｌ）に進み、そうでない場合には請求項１５のＤＤＰ探索方法を前記探索ベクトルＳjiに沿って適用して対応する動的分解点（ＤＤＰ）を求め、ＤＤＰが求められた場合にはステップ（ｇ）に立ち止まり、そうでない場合にはｉ＝ｉ＋１を設定してステップ（ｆ）に戻るステップと、
ｈ）  前記求められたＤＤＰをｘjd,iとして表し、前記ＤＤＰが集合Ｖdに属するかどうか、すなわちｘjd,i∈Ｖd？を検査し、属する場合はｉ＝ｉ＋１を設定してステップ（ｆ）に戻り、そうでない場合にはＶd＝Ｖd∪｛ｘjd,i｝を設定してステップ（ｈ）に立ち止まるステップと、
ｉ）  前記ＤＤＰｘjd,iに対し、ステップ（ｉ）から（ｊ）を実行して対応する近傍局所最適解を求めるステップと、
ｊ）  εが小さい数であるｘj0,i＝ｘjs＋（１＋ε）（ｘjd,i−ｘjs）を設定するステップと、
ｋ）  ｘj0,iを前記初期条件として使用しハイブリッド探索方法を適用して前記対応する局所最適解を求め、それをｘis,jとして表すステップと、
ｌ）  ｘis,jが前に求められたかどうか、すなわちｘis,j∈Ｖs？を検査し、以前求められている場合には、ｉ＝ｉ＋１を設定してステップ（ｆ）に戻り、そうでない場合にはＶs＝Ｖs∪｛ｘis,j｝およびＶj+1new＝Ｖj+1new∪｛ｘis,j｝を設定し、さらにｉ＝ｉ＋１を設定してステップ（ｆ）に戻るステップと、
ｍ）  新しく計算された全ての局所最適解の集合Ｖj+1newを調査し、Ｖj+1newが空でない場合にはｊ＝ｊ＋１を設定してステップ（ｄ）に戻り、そうでない場合には次のステップに進むステップと、
ｎ）  前記局所最適解の集合Ｖsから、集合Ｖsにおけるそれらの対応する目的関数の値を比較することにより前記大域最適解を識別するステップと、
を備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、数学的解析とモデリングの分野に係わる。特には、本発明は、一般的非線形プログラミング問題の大域最適解（global optimal solution）を得るための動的方法に関わる。
【背景技術】
【０００２】
科学、エンジニアリング、経済学において発生する様々な定量的決定問題は、制約条件付き非線形最適化問題として認識され、モデル化されることができる。この一般的な記述によって、しばしば実数ベクトルで表される最高決定は、記述された全ての実行可能制約条件を充足し、目的関数の値を最小化（あるいは最大化）する探索空間において求められる。このベクトルは、もしそれが存在するのであれば、“大域最適解”と呼ばれる。一般的に、局所的に最適（局所最適解は探索空間の局所領域において最適である）ではあるが、大域的に最適ではない解が存在する。
【０００３】
一般的に、制約条件付き非線形最適化問題の探索空間は、多数の局所最適解を含む。通常、局所最適解の数は不明であり、非常に大きな数になり得る。さらに、局所最適解と大域最適解における目的関数の値は甚だしく異なる。既存の非線形最適化手法のほとんどは、大域最適解ではなく、局所最適解を通常求める。
【０００４】
制約条件付き非線形最適化問題の大域最適化解を求める作業は、様々なエンジニアリング分野および科学において発生する設計、操作、および計画問題における非常に幅広い適用範囲に対して重要である。エンジニアリング適用領域は、たとえば、構造最適化、エンジニアリング設計、ＶＬＳＩチップ設計およびデータベース問題、画像処理、計算機化学、分子生物学、核および機械設計、化学エンジニアリング設計および制御、電気ネットワークにおける最適パワーフロー、規模の経済、固定料金、割り当ておよび配置問題、二次割り当て、ならびに多数の他の適用を含む。
【０００５】
大域最適化（Global Optimization）（ＧＯ）問題と呼ばれる、大域最適解を求める問題は、大変難しくて取り組み甲斐がある。計算の複雑さの観点から、制約条件付き非線形最適化問題の大域最適解を求める作業は，ＮＰ困難問題のクラスに属する。これは、問題の入力サイズが大きくなるにつれて、問題を解くために必要な計算時間が指数的に増えることを意味する。
【０００６】
ＧＯ問題を解くために提案された既存の方法は、３つのクラスに分類できる。すなわち、決定論的方法、確率的方法、ハイブリッド方法である。決定論的方法は、通常、ある数学的構造に関わる最適化問題のための有限ステップにおいて近似大域最小への収束を数学的に保証する。この方法クラスは、分枝限定法、切除平面法、分解に基づく接近法、カバリング方法、インターバル方法、ホモトピー法、および汎用傾斜法を含む。一方、確率的方法は、大域最適解を求めるために、目的関数のサンプリング、およびおそらくは、それらの導関数を計算する事を必要とする。確率的方法は広い範囲のＧＯ問題に適用することができるが、大域最適解にたどり着くために必要とされるサンプルの数は、高次元問題に関してはしばしば桁外れに大きい。確率的方法のクラスは、正確な大域最適解が必要とされる場合、遅い収束と精度に欠けるといった特徴がある。ランダム探索方法、遺伝的アルゴリズム、焼きなまし法、クラスタリング法、およびベイジアン法はすべて確率的方法のクラスに属する。ＧＯ問題のためのハイブリッド方法は最近提案されたクラスである。この方法クラスは、常にではないが、通常一つの確率的方法、たとえば遺伝的アルゴリズムと準ニュートン法などの伝統的な“山登り（hill-climbing）”法を組み合わせる。二つの異なる方法を、それらの利点を一体化し、欠点を緩和しようとして一つに組み合わせるという考え方はよく知られている。この組み合わせに関する論点は、どの方法をどのように一体化するかということである。ハイブリッド方法のこのクラスは、確率的方法から継承した遅い収束という欠点があるものの、“山登り”法を使ったことで精度が上がる。
【発明の開示】
【０００７】
非線形最適化問題の大域最適解を求める唯一の確実な方法は、全ての局所最適解を最初に求め、次にその中から大域最適解を求めることである。本発明においては、本質的には決定論的である、新しい体系化された方法を展開し、制約条件なしおよび制約条件付き非線形最適化問題両方の全ての局所最適解を求める。次の大域最適化方法の二つのクラスが本発明において展開される。
−  制約条件なし非線形プログラミング問題のための動的軌跡に基づく方法。
−  制約条件付き非線形プログラミング問題のための動的軌跡に基づく方法。
【０００８】
制約条件なし非線形最適化問題に関し、この新しい方法の際だった一つの特徴は、全ての局所最適解を体系的に求めることである。制約条件付き非線形最適化問題に関し、本発明の新しい方法の際だった一つの特徴は、その実行可能領域が接続されていない可能性がある、制約条件付き非線形最適化問題の全ての局所最適解を体系的に求めることである。我々が展開した方法は二つの別個のフェーズから構成される。フェーズＩは、実行可能領域全体の接続された各実行可能領域を体系的に配置する。フェーズIIは、フェーズＩで得られた各実行可能領域に存在する全ての局所最適解を求める。
【０００９】
本発明においては、大域最適解の探索における以下の二つの重要な課題のための方法が展開される。
（ｉ）  局所最適解から有効に移動し（脱出し）、別の局所最適解に移動する方法。
【００１０】
（ii）既知の局所最適解の再訪を回避する方法。
過去、この課題を解決するために多大な努力が払われてきたが、あまり成功しなかった。課題（ｉ）は解決することが難しく、決定論的方法および確率的方法のクラスの両方がこの困難さに直面している。探索中の計算効率に関連する課題（ii）も、解決することが難しく、やはり決定論的方法および確率的方法のクラスの両方がこの困難さに直面している。本発明においては、これらの問題を克服する有効な方法が展開され、動的軌跡に基づく方法に組み込まれる。
【００１１】
制約条件なし大域最適化問題に関連する我々の前の研究は、その完全な開示が記述によってこの明細書中に組み込まれたＨ．Ｄ．Ｃｈiａｎｇ，  Ｃｈｉａ−Ｃｈｉ  Ｃｈｕ，  非線形プログラミング問題の複数局所最適解を求めるための体系的探索方法  ＩＥＥＥ  Ｔｒａｎｓ．  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ，ｖｏｌ．４３，ｐｐ．９９−１０９，１９９６に記述されている。この研究は、特別な非線形動的システムを構築する考え方、および理論的に富んだ概念方法の展開に注目したが、実用的に適用するために数値的に実現することは、不可能ではないにせよ難しい。この研究は、その完全な開示が記述によってこの明細書中に組み込まれたＪａｅｗｏｏｋ  Ｌｅｅ、大域最適化のための経路をたどる方法、Ｐｈ．Ｄ．学位論文、Ｃｏｒｎｅｌｌ  Ｕｎｉｖ．，ＮＹ，１９９９における制約条件付き大域最適化問題に拡張された。とりわけ、この出版物は、理論的には富んでいるが、実用的に適用するために数値的に実現することが、不可能ではないにせよ難しい２フェーズ最適化手順を実行するための二つの特別な非線形動的システム（nonlinear dynamical systems）の構築を提示している。非線形動的システムを構築する考え方は、１９９６年１月９日にＨｓｉａｏ−Ｄｏｎｇ  Ｃｈｉａｎｇに対して発行され、その完全な開示が記述によってこの明細書中に組み込まれた米国特許Ｎｏ．５，４８３，４６２，パワーシステム過渡安定度を決定するためのオンライン方法において、非線形回路およびシステムの複数ＤＣ動作点を求めるための建設的ホモトピー方法を展開するために採用された。
本発明は以下の局面（他も含む）において、従来技術と異なる：
（１）本発明は、非線形動的システム（制約条件なし最適化問題のための条件（Ｃ１）および（Ｃ２）、制約条件付き最適化問題のための条件（Ｃ１−１）、（Ｃ１−２）、（Ｃ２−１）および（Ｃ２−２）を参照）のクラスを展開し、それらのシステム軌跡を、局所最適解および大域最適解の一式を求めるための数値方法を展開するために使うことができることを示す。
（２）前述の出版物における特別な非線形動的システムは、全て本発明において展開される非線形動的システムのクラスに属する。
（３）本発明は、任意の既存局所オプティマイザ（すなわち局所最適解を求める方法）を組み込むことができる、動的軌跡に基づく方法を展開するので、本発明は任意の既存コンピュータパッケージを局所最適解および大域最適解の一式を求めさせるために適用することができる。
（４）本発明は、局所最適解および大域最適解の一式を求めるために、（グラフィカル・ユーザ・インターフェース・データベースを含む）既存のコンピュータパッケージの“環境”を修正せずに、任意の既存コンピュータパッケージを結びつけるようにプログラミングされることができ、特に、本発明では、組み合わされたコンピュータパッケージにおいてユーザに新しい学習を課するものではない。
（５）本発明は、動的分解点探索方法と呼ばれる、探索処理を決定論的に局所最適解の捕捉から脱出させるための数値方法を展開する。
（６）本発明は、前に特許化された方法を拡張し、動的分解点探索方法に組み込まれた、出口点を計算するための数値方法と呼ばれる数値方法を展開する。
（７）本発明は、動的分解点探索方法に組み込まれた、出口点を算出するための改良法と呼ばれる数値方法を展開する。
（８）本発明は、動的分解点探索方法に組み込まれた、最小距離点（ＭＤＰ）を算出するための数値法と呼ばれる数値方法を展開する。
（９）本発明は、動的分解点探索方法に組み込まれた、最小距離点（ＭＤＰ）を算出するための改良法と呼ばれる数値方法を展開する。
（10）本発明は、軌跡に基づく方法および局所最適解を求めるための有効局所最適化方法で構成されたハイブリッド探索方法を展開する。このハイブリッド方法は、前者の方法の信頼性と精度、および後者の方法の精度と計算速度を併せ持つ。
【００１２】
これらの方法の理論的根拠は以下のとおりである。
われわれは、局所最適解から如何に脱出し別の局所最適解に如何に移動するかという問題を、ある制約条件を充足する非線形動的システムの対応する（漸近的）安定平衡点（ｓ．ｅ．ｐ．）の安定化領域から如何に脱出し、非線形動的システムの別の対応するｓ．ｅ．ｐ．の安定化領域に如何に入るかという問題として扱う。必要とされる条件を充足する非線形動的システムを構築するいくつかの方法がある。本発明は、このような非線形動的システムを構築するためのガイドラインを提示する。
【００１３】
大域最適解を探索するための多くの既存の方法の性能を劣化させる一つの共通の問題は、同じ局所最適解を数回にわたって再訪する事である。これは大域最適解の場所に関する新しい情報を得ぬまま、計算リソースを浪費する。計算上の観点から、効率の水準を維持するために、同じ局所最適解の再訪を回避することは重要である。課題（ii）を解決するために、本発明においては、制約条件なしおよび制約条件付き最適化問題両方のための再訪防止探索方法を展開する。再訪防止探索方法の理論的根拠は、本発明において展開される動的分解点に基づく。
【００１４】
本発明は、局所最適解の再訪防止方法を展開し、前に求められた局所最適解を含む領域の探索を回避する。また、本発明は、ＤＤＰ探索方法と組み合わせて、決定論的に別の局所最適解を求めるために局所最適解から探索を行う手順を実行する、ＤＤＰに基づく数値方法を展開する。
【００１５】
実用上の観点から、本発明において展開される動的軌跡に基づく方法は、常微分方程式（ＯＤＥ）の組を積分する必要がある。例えば、従来のニュートンタイプの方法と比べると、ＯＤＥソルバはあまりに大規模で一般的に使用することができないと多くの人に思われていた。しかし、それらソルバの性能は、積分方法の選択およびステップサイズの制御の仕方によって多大な影響を受ける。適切に実現された場合、これらの方法は、最適化アルゴリズム展開の主流として位置付けされる。例えば、その完全な開示がこの明細書中に記述することによって組み込まれたＡ．Ａ．Ｂｒｏｗｎ，Ｍ．Ｃ．Ｂａｒｔｈｏｌｏｍｅｗ−Ｂｉｇｇｓ，常微分方程式システムの解に基づく制約条件なし最適化のためのいくつかの有効方法Ｊｏｕｒｎａｌ  ｏｆ  Ｏｐｔｉｍｉｚａｔｉｏｎ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，ｖｏｌ．６２，ｐｐ．２１１−２２４，１９８９を参照のこと。
【００１６】
本発明は、任意の既存局所オプティマイザ（すなわち局所最適解を求めるための方法）を組み込むことのできる、動的軌跡に基づく方法を展開する。従って、本発明は、任意の既存コンピュータパッケージに局所最適解および大域最適解の一式を求めさせるために適用することができる。本発明は、局所最適解および大域最適解の一式を求めるために（グラフィカル・ユーザ・インターフェース・データベースを含む）既存のコンピュータパッケージの“環境”を修正せずに、任意の既存コンピュータパッケージを結びつけるようにプログラミングすることができる。特に、本発明は、組み合わされたコンピュータパッケージにおいてユーザに新しい学習を課するものではない。
本発明について要約すると、一般的非線形プログラミング問題の大域最適解を得るための方法は、以下のステップを備える。すなわち、最初に、決定論的に条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの全ての安定平衡点を求め、次に、前記点から大域最適解を求めるステップを備える。
【００１７】
本発明の実施例において、大規模システムのための、動的分解点を確実に計算するための実用数値方法は、以下のステップを備える。すなわち、ｘS から出発する探索経路
【００１８】
【数９】
2005508026.tif 000003
【００１９】
に沿って移動し、出口点ｘexを初期条件として使用して前記探索経路φt （ｘs ）が安定平衡点ｘs の安定化境界を抜ける出口点ｘexを検出して非線形システムを平衡点ｘd まで積分し、局所最適解ｘs に関する前記動的分解点を計算するステップを備える。ここで探索方向
2005508026.tif 000004
【００２０】
（以下、Ｓ＾と表記する）はｅ ｘd である。
【発明を実施するための最良の形態】
【００２１】
例１：
制約条件なし非線形プログラミング問題の大域最適方法
一般的制約条件付き非線形最適化問題の形式を考える。
【００２２】
Ｍｉｎｉｍｉｚｅ  Ｃ（ｘ）        （４．１）
ここで
2005508026.tif 000005
【００２３】
は、大域最小解が存在し局所最小解の数が有限であるような、以下のように限定される滑らかな関数である。
目的関数Ｃ（ｘ）の最適解は形式上以下のように定義することができる。Ｍを実行可能領域の集合であるとする（すなわち制約条件を充足する全ての解）。ｘ* ∈Ｍであり、条件ｘ∈Ｍおよび‖ｘ−ｘ* ‖＜εがＣ（ｘ）≧Ｃ（ｘ* ）を意味するようなε＞０が存在する場合に限り、ｘ* は局所最小解であると言う。ｘ* ∈Ｍであり、全ｘ∈Ｍに関してｆ（ｘ）≧ｆ（ｘ* ）である場合に限り、ｘ* が大域最小解であると言う。
【００２４】
大域最適解ではなく、局所最適解を有効に求めることのできる利用可能な（局所）最適化方法が数多く存在する。探索処理の間、これらの方法は通常局所最適解で捕捉され、別の局所最適解に移動することができない。最適化問題（図１参照）の大域最適解を求めるための唯一の確実な方法は、最初に全ての局所最適解を求め、次に、それら局所最適解から大域最適解を求めることであると言える。従って、われわれは以下のステップを提示する。
【００２５】
ステップ１：決定論的に（４．１）の全ての局所最適解を体系的に求める。
このために、本発明においては、動的軌跡に基づく方法を展開し、後で述べる条件を充足する非線形動的システムによって、（４．１）の全ての局所最適解を体系的に計算する。これにより、ステップ１を以下のステップに変換する。
【００２６】
ステップ１：以下に述べる条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの全ての安定平衡点を求める。
動的軌跡に基づく方法の主な作用を示すために、簡単な例を挙げることとする。制約条件なし最適化問題における６つの局所最適解があるとする（図１参照）。これら６つの局所最適解は、条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの安定平衡点となり、各安定平衡点は、それ自身の準安定化領域を持つ（図２参照）。任意の初期条件で出発し（われわれの変換においては、初期条件は安定平衡点の準安定化領域内に存在していなければならない）、動的軌跡に基づく方法に組み込まれたハイブリッド方法は、局所最適解（すなわち安定平衡点）を求める（図３参照）。局所最適解を与えられると、動的軌跡に基づく方法は有効にその局所最適解から脱出し、進行してその対応する準安定化境界がその局所最適解の準安定化境界と空でない交点を持つ全ての近傍局所最適解を求める。上記処理を継続することによって、求められたばかりの局所最適解から出発し、“次”の近傍局所最適解を求め、全ての局所最適解が求められた事を動的軌跡に基づく方法が示すまで処理を継続する。
【００２７】
大域最適解を求めるために与えられた計算時間に関する制約条件を与えられると、その解に近い初期点を適切に選ぶことによって大域最適解を求める事における、我々の発明した方法の信頼性が高まる。従って、初期探索点をどこに取るべきかを決定するための確率的処理の使用に基づき、（その完全な開示がこの明細書中に記述することによって組み込まれたＭｏｃｋｕｓ，Ｊ．（１９９４）大域および確率的最適化の数値方法へのベイジアン法の適用、Ｊｏｕｒｎａｌ  ｏｆ  Ｇｌｏｂａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ，ｖｏｌ．４，ｐｐ．３４７−３６５に述べられた）よく知られている“性能指数”法を採用することを提案することとする。
【００２８】
動的軌跡に基づく方法のもう一つの際だった特徴は、既存の局所最適化方法（すなわち局所オプティマイザ）と協調動作して有効に局所最適解を求めることであり、これにより本発明のコンピュータによる実現と既存の局所オプティマイザコンピュータソフトウェアとを結びつけることが可能になる。
【００２９】
このような非線形動的システムを構築するためのガイドラインが次のセクションで展開される。
非線形動的システム構築ガイドライン
これまで非線形動的システムの関連する概念をいくつか検討してきた。次に、軌跡を上記ステップ１を実行するために使用することのできる非線形動的システムを構築するための一般的ガイドラインを提示する。
【００３０】
一般的非線形動的システム、例えば、以下の常微分方程式の組によって記述されるシステムを考える。
【００３１】
【数１０】
2005508026.tif 000006
【００３２】
ここで
2005508026.tif 000007
【００３３】
は（４．２）の解の存在と一意性のための条件を充足する。ｔ＝０で
2005508026.tif 000008
【００３４】
から出発する（４．２）の解は、
2005508026.tif 000009
【００３５】
で表される“軌跡”と呼ばれる。
Ｆ（ｘ*）＝０である場合に  状態ベクトル
2005508026.tif 000010
【００３６】
はシステム（４．２）の平衡点と呼ばれる。ｘ* におけるＦ（・）のヤコビ行列がゼロ実数部分で固有値を持たない場合に、（４．２）の平衡点
2005508026.tif 000011
【００３７】
は“双曲型”であると言う。双曲型平衡点のヤコビアンが正の実数部分を持つ固有値ｋをまさしく持つ場合、それを“タイプｋ平衡点”と呼ぶこととする。対応するヤコビアンの全ての固有値が負の実数部分を持つ場合、双曲型平衡点は（漸近的）安定平衡点であり、対応するヤコビアンの全ての固有値が正の実数部分を持つ場合には、双曲型平衡点は不安定平衡点であることが分かる。タイプｋ双曲型平衡点ｘ* に関して、その安定および不安定多様体Ｗs （ｘ* ）、Ｗu （ｘ* ）は以下のように定義される。
【００３８】
【数１１】
2005508026.tif 000012
【００３９】
ここでＷu （ｘ* ）、Ｗs （ｘ* ）の次元はそれぞれｋとｎ−ｋである。
全ての
2005508026.tif 000013
【００４０】
に関してＫにおいて出発する（４．２）の各軌跡がＫにとどまる場合に、
2005508026.tif 000014
【００４１】
（以下、「／Ｒn 」と表記する）における集合Ｋは（４．２）の“不変集合”と呼ばれる。システムの各軌跡がその平衡点の一つに収束する場合、動的システムは“完全に安定している”と言われる。
【００４２】
安定平衡点ｘs の安定化領域（あるいは引き込み領域）は、以下のように定義されるべく、軌跡の全てが収束する全ての点の集まりである。
【００４３】
【数１２】
2005508026.tif 000015
【００４４】
安定平衡点ｘs の準安定化領域Ａp （ｘs ）は以下のように定義される。
【００４５】
【数１３】
2005508026.tif 000016
【００４６】
ここで
2005508026.tif 000017
【００４７】
（以下、「Ａ（ｘs ）」と表記する）は、安定化領域Ａ（ｘs ）の閉包であり、Ａ（ｘs ）はＡ（ｘs ）の内部である。位相的観点から、Ａ（ｘs ）およびＡp（ｘs ）は開であり、不変であり、経路接続された集合である。さらに、それらは／Ｒnに微分同相である。
【００４８】
システム軌跡のいくつかをステップ１を実行するために使うことのできるような非線形動的システムを構築するための方法がいくつかある。このような非線形動的システムを構築するための以下の一般的ガイドラインを提案することとする。その軌跡がステップ１を実行するために利用することのできるシステムは、次の二つの条件を充足する必要がある。
（Ｃ１）−  各システム軌跡は収束し、なおかつ平衡点の一つに収束する。
（Ｃ２）−  非線形動的システムの任意のシステム軌跡に沿った、
（４．１）の目的関数Ｃ（ｘ）の導関数は正ではない。すなわち
2005508026.tif 000018
【００４９】
；さらに、導関数が重要な軌跡である（すなわちｘ（ｔ）が平衡点ではない）場合、ｘ（ｔ）に沿った以下の集合
【００５０】
【数１４】
2005508026.tif 000019
【００５１】
は／Ｒにおいて測度ゼロになる。
条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの一例は以下のとおりである。
【００５２】
【数１５】
2005508026.tif 000020
【００５３】
ここで∇Ｃ：／Ｒn→／Ｒnは、式（４．１）における目的関数の勾配ベクトルである。条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの別の例は以下のとおりである。
【００５４】
【数１６】
2005508026.tif 000021
【００５５】
ここでＡ（ｘ）は限定されている、全ｘ∈／Ｒnに対する正定値行列であり、∇Ｃ：／Ｒn→／Ｒnは式（４．１）における目的関数の勾配ベクトルである。
条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムは以下の性質を持つことが分かる。
【００５６】
（Ｐ１）  非線形動的システムは完全に安定しており、このシステムの限界集合は平衡点のみで構成されている。換言すれば、このシステムに関して安定した状態の他の種類は存在しない（これは条件（Ｃ１）から導出される）。
【００５７】
（Ｐ２）  点、例えばｘk s が非線形動的システムの安定平衡点である場合に限り、ｘk s は、非線形最適化問題（４．１）の局所最適解である（この性質は条件（Ｃ１）および（Ｃ２）から導出される）。
【００５８】
我々の動的軌跡に基づく方法において、性質（Ｐ２）は重要な役割を果たし、（４．１）の全ての局所最適解を体系的に計算する。これにより、ステップ１を以下のステップへと変換する。
【００５９】
ステップ１：  条件（Ｃ１）および（Ｃ２）を充足する非線形動的システムの全ての安定平衡点を求める。
解析結果
以下の解析結果は、条件（Ｃ１）を充足する非線形動的システムの準安定化領域および準安定化境界を特徴づける。
定理４−１：
条件（Ｃ１）を充足する、（４．２）に記述された非線形動的システムを考える。Ａ（ｘs ）およびＡp （ｘs ）をそれぞれｘs の安定化領域および準安定化領域であるとする。準安定化境界∂Ａp （ｘs ）上の平衡点が双曲型であり有限数である場合、以下のようになる。
（１）準安定化境界∂Ａp （ｘs ）上に存在するタイプ１平衡点が存在し、それらは有限数である。
（２）ｘi ，ｉ＝１，２，．．．を∂Ａp （ｘs ）上に存在するタイプ１平衡点であるとすると、準安定化境界∂Ａp （ｘs ）はｘi の安定多様体の閉包の和集合である。すなわち
【００６０】
【数１７】
2005508026.tif 000022
【００６１】
さらに∂Ａp （ｘs ）上の平衡点の安定および不安定多様体の間の交点が横断条件を充足する場合、
（３）
2005508026.tif 000023
【００６２】
（以下、「ｘ」と表記する）の不安定多様体間の交点が、準安定化領域および準安定化領域の閉包の補集合の両方に交差する、すなわち
【００６３】
【数１８】
2005508026.tif 000024
【００６４】
である場合に限り、平衡点ｘはｘs の準安定境界上に存在する、すなわち
【００６５】
【数１９】
2005508026.tif 000025
【００６６】
である。
（４）
2005508026.tif 000026
【００６７】
である場合に限り、
2005508026.tif 000027
【００６８】
定理４−１の解析結果（２）によって、準安定化境界上に存在するタイプ１平衡点を、“動的分解点”と呼ぶこととする。さらに、安定平衡点ｘs から出発し、準安定化境界∂Ａp （ｘs ）を指し示す探索経路（すなわち探索ベクトル）を与えられると、その探索経路は準安定化領域∂Ａp （ｘs ）を抜ける前に出口点と呼ばれる一つの点でヒットしなければならない（図５参照）。従って、安定平衡点ｘs および探索経路に関する動的分解点は、不安定平衡点であり、その安定多様体は探索経路の出口点を含む（すなわち動的分解点は、出口点で安定多様体に探索経路がヒットした最初の不安定平衡点である）。安定平衡点ｘs および探索経路に関する動的分解点の一意性と存在の課題は、定理４−１によって確実なものにされる。
【００６９】
次に、動的分解点の動的性質に関する解析結果を展開する。
定理４−２：
条件（Ｃ１）を充足する、（４．２）に記述された非線形動的システムを考える。∂Ａp（ｘs）およびｘd∈∂Ａp（ｘs）をそれぞれｘsの準安定化領域、および動的分解点であるとする。∂Ａp（ｘs）上の平衡点の安定及び不安定多様体の交点が横断条件を充足する場合、別の唯一の安定平衡点、例えば以下のような（４．２）のｘs が存在する。
（１）ｘd ∈∂Ａp （ｘs ）はｘsに関する動的分解点であり、
（２）Ｗu （ｘd ）∩Ａp （ｘs ）≠０およびＷu （ｘd ）∩Ａp （ｘs ）≠０
動的分解点（ＤＤＰ）を求める作業は、概して非常に難しい。この難しさは、一つには以下の複雑さによって生じる。
（１）ＤＤＰは、高次状態空間に組み込まれた特別な不安定平衡点である。
（２）ＤＤＰは、安定多様体に探索経路が（出口点で）ヒットした最初の不安定平衡点である。
ＤＤＰを計算する作業は、その収束領域の大きさと形によってさらに複雑になる。選択された数値方法に関して、各平衡点がそれ自身の収束領域を持つ（すなわち、その領域における点から出発する数値方法によって生成される数列が平衡点に収束する領域）。不安定平衡点の収束領域の小ささといびつな（フラクタルのような）形のために、ＤＤＰを計算する作業は非常に難しい。初期推定がＤＤＰに十分近くない場合、例えばニュートン法によって生成された数列は発散するかあるいは別の平衡点に収束する。悪いことに、ＤＤＰに十分近い初期推定を求めるのは難しい作業である。
ＤＤＰ探索方法
本発明の一つの主要な貢献は、大規模システムのための、動的分解点を確実に計算するための実用的数値方法の展開である。数値方法の前に概念方法をまず提示することとする。
【００７０】
条件（Ｃ１）を充足し、（４．２）に記述された非線形動的システムを考えることとする。安定平衡点ｘs 、および探索ベクトルｓ＾に関するＤＤＰを計算するための概念方法を以下に述べる。
【００７１】
ステップ１ − ｘsから出発する探索経路
2005508026.tif 000028
【００７２】
に沿って移動し、探索経路φt (ｘs )が安定平衡点（すなわち局所最適解）ｘs の安定化境界を抜ける出口点、例えばｘexを検出する。
ステップ２  −  出口点ｘexを初期条件として使用し、非線形システム（４．２）を平衡点まで積分する。その平衡点をｘd とする。
【００７３】
ステップ３  −  局所最適解ｘs および探索方向ｓ＾に関するＤＤＰはｅ ｘd である。
上記概念方法のステップ１は以下のように数値的に実現される。
出口点の計算方法
ステップ１  −  ｘsから出発する探索経路
2005508026.tif 000029
【００７４】
に沿って移動し、探索経路φt (ｘs )に沿った、目的関数Ｃ（ｘ）の最初の局所最大である出口点、例えばｘexを検出する。
既知の方法を拡張した、上記概念方法のステップ２は以下のように数値的に実現される。
ＭＤＰの計算方法
ステップ２．１  −  出口点ｘexを初期条件として使用し、ノルム‖Ｆ（ｘ）‖の最初の局所最小に非線形システム（４．２）を積分する。ここで‖Ｆ（ｘ）‖はベクトルフィールド（４．２）のベクトルである。局所最小点をｘ0 d とする。この点は最小距離点（ＭＤＰ）と呼ばれる。
【００７５】
ステップ２．２  −  ＭＤＰ ｘi,0 d,j を初期推定として使用し、ベクトルフィールド（４．２）の非線形代数式の以下の組を解く。
Ｆ（ｘ）＝０
解をｘdとする。局所最適解ｘs および探索経路φt (ｘs )に関する動的分解点はｘd である。
【００７６】
出口点を検出するための別の数値手法は、各タイムステップにおける探索ベクトルおよびベクトルフィールドの内積を計算することである。内積の符号が正から負に変わる時に出口点が検出される。これにより、出口点を検出するための別の数値方法を提案する。
【００７７】
ｘs から出発する探索経路
2005508026.tif 000030
【００７８】
に沿って移動し、各タイムステップにおいて、探索ベクトルｓ＾およびベクトルフィールドＦ（ｘ）の内積を計算する。内積の符号が正から負に変わる時に出口点が検出される。
しかし、デジタルコンピュータ上の数値シミュレーションの性質上、探索経路に沿った出口点を（縮小された状態のシステムの安定化境界上に存在する点であるとして）正確に計算することは出来ない。その結果、間違いのある軌跡に沿って、計算された出口点の二つの場所が存在しうる。一つは内積の符号が変わる前の点であり、もう一つは符号が変わった後の点である。通常は、どちらか一つをシミュレーションされた出口点として使うことができる。しかし、動的分解点の計算は出口点の精度に非常に影響を受けやすいこともあり、上記方法は数値収束問題に遭遇する可能性がある。この数値問題を克服するために、以下に述べる線形補間手法によって出口点の計算精度を上げるための次の方法を提案することとする。
出口点計算の改良方法
時間ｔ1における内積の値がｄ1（ｄ1＞０）であり、次の時間ステップｔ2が負の内積ｄ2＜０になるとする。線形補間が時間間隔［ｔ1，ｔ2］に一回適用され、その結果補間された時間ｔ0⊂［ｔ1，ｔ2］になる。
【００７９】
【数２０】
2005508026.tif 000031
【００８０】
次に、ｔ0における内積はｄ0として正確に計算される。ｄ0の絶対値が十分に小さい（０に近い）場合、ｔ0は出口点時間の瞬間として扱われる。ｄ0の絶対値が十分に小さくない場合、二つの可能性が起こり得る。
【００８１】
（１）ｄ0＞０である場合、一回あるいはそれ以上の線形補間が時間間隔［ｔ0,ｔ1］に適用される。
（２）ｄ0＜０である場合、一回あるいはそれ以上の線形補間が時間間隔［ｔ1,ｔ0］に適用される。
【００８２】
上記処理は、補間された時間における内積の絶対値が指定された許容値より小さくなるまで繰り返し実行する事ができる。要するに、線形補間方法を使って出口点を正確に検出するための手順は、以下のように実現することができる。
【００８３】
ステップ１  −  内積の符号が変わるまで、例えば間隔［ｔ1,ｔ2］の間まで探索ベクトルに沿って移動する。
ステップ２  −  間隔［ｔ1,ｔ2］に線形補間を適用し、補間された内積がゼロになると予想される中間時間ｔ0を生成する。ｔ0における正確な内積を計算する。その値がしきい値より小さい場合に出口点が得られる。ループを抜ける。
【００８４】
ステップ３  −  内積が正である場合、ｔ1をｔ0で置き換える。そうでない場合、ｔ2をｔ0で置き換え、ステップ２に戻る。
ＭＤＰ計算の改良方法
動的分解点の計算における重要な二つのステップは、出口点（ＥＰ）の計算と最小距離点（ＭＤＰ）の計算である。動的分解点の計算の精度はＭＤＰとＥＰの計算の精度に依存する。出口点の計算における数値エラーはＭＤＰの計算を数値的に困難にする。同様に、ＭＤＰの計算における数値エラーは動的分解点の計算を数値的に困難にするであろう。
【００８５】
ＥＰが、対応する動的分解点からかなり離れた所に存在しうる状況では、以下の数値的問題が発生する可能性がある。
―     ＭＤＰを数値的に求めることができない。
―     求められたＭＤＰが動的分解点に十分近くないので、非線形代数ソルバは発散するかあるいは間違った動的分解点に収束する。
【００８６】
ＭＤＰを、動的分解点を計算するためにニュートン法における初期推定として使用することができる。しかし、ＭＤＰが動的分解点に十分近い場合、そのＭＤＰから出発する、ニュートン法によって生成された数列はその動的分解点に収束する。そうでない場合には、数列は別の平衡点に収束するか発散する。
【００８７】
動的分解点を確実に計算するために適切なＭＤＰを求めるために、ＭＤＰの探索処理を誘導するための有効手順を展開することとする。この手順を以下に述べる（図８−１１参照）。
ＭＤＰ計算のための有効方法
ステップ１  ―  （軌跡生成）  出口点を初期条件として使用し、小数のタイムステップ、例えば、５の間、非線形システムを積分する。
【００８８】
ステップ２  −  （収束検査）  収束基準を検査する。（ステップ１で得られた）点のノルムがしきい値より小さい場合、この点はＭＤＰとして宣言される。そうでない場合は次のステップに進む。
【００８９】
ステップ３  −  （訂正された出口点）  軌跡上の現在点と局所最適解（すなわち安定平衡点）を結ぶ線を引く。現在点を、安定平衡点から出発する線に沿った、目的関数の（最初の）局所最大点である訂正された出口点に置き換える。この点を出口点に代入し、ステップ１に戻る。
【００９０】
ゼロ交差を検査する処理は、探索を安定平衡点から始める代わりに軌跡上の現在点から始めることによって、速度を早くすることができる。現在点における内積の符号は局所最大探索を始める方向を決定する。上記の方法を使って得られたＭＤＰは、非線形代数ソルバに対して動的分解点の収束領域内に存在するようであるので、ソルバは容易に動的分解点を求めることができる（図１２参照）。
ここで、安定平衡点ｘsおよび探索ベクトルｓ＾に関するＤＤＰを計算するための数値ＤＤＰ探索方法を提示することとする。
数値ＤＤＰ探索方法
ステップ１  −  ｘsから出発する探索経路
2005508026.tif 000032
【００９１】
に沿って移動し、探索ベクトルｓ＾とベクトルフィールドＦ（ｘ）の内積の符号が変わる瞬間、例えば間隔［ｔ1,ｔ2］間を検出する。ｔ1がしきい値より大きい場合にはこのステップに立ち止まり、この探索経路に沿って近傍の局所最適解がないことを報告する。そうでない場合にはステップ２に進む。
ステップ２  −  線形補間を間隔［ｔ1,ｔ2］に適用し、補間された内積がゼロになると予想される中間時間ｔ0を生成する。ｔ0における正確な内積を計算する。その値がしきい値より小さい場合には、出口点が得られ、ステップ４に進む。
【００９２】
ステップ３  −  内積が正である場合、ｔ1をｔ0で置き換える。そうでない場合にはｔ2をｔ0で置き換え、ステップ２に戻る。
ステップ４  −  出口点を初期条件として使用し、小数のタイムステップ、例えば、５の間、非線形システムを積分する。
【００９３】
ステップ５  −  収束基準を検査する。（ステップ４で得られた）点のノルムがしきい値より小さい場合、この点はＭＤＰとして宣言され、ステップ７に進む。そうでない場合には次のステップに進む。
【００９４】
ステップ６  −  軌跡上の現在点と局所最適解（すなわち安定平衡点）を結ぶ線を引く。現在点を、安定平衡点から出発する線に沿った、目的関数の（最初の）局所最大点である、訂正された出口点に置き換える。この点を出口点に代入し、ステップ４に戻る。
【００９５】
ステップ７  −  ＭＤＰを初期推定として使用し、ベクトルフィールド（４．２）の非線形代数式の以下の組を解く。
Ｆ（ｘ）＝０
解をｔdとする。局所最適解ｘs およびベクトルｓ＾に関するＤＤＰはｘdである。
ハイブリッド探索方法
利点を一緒にし、欠点を緩和するために二つの異なる方法を一つに組み合わせる考え方はよく知られており、広く受け入れられている。このような組み合わせに固有の大きな問題はどの方法をどのように組み合わせるかということである。本発明において展開され、大域オプティマイザに組み込まれるハイブリッド探索方法は、動的軌跡方法と、準ニュートン法やトラスト領域法（例えば、その完全な開示がこの明細書中に記述する事によって組み込まれたＲ．Ｈ．Ｂｙｒｄ，Ｒ．Ｂ．Ｓｃｈｎａｂｅｌ，Ｇ．Ａ．Ｓｈｕｌｔｚ  非線形的に制約条件が付いた最適化のためのトラスト領域アルゴリズムを参照）などの、局所最適解を求めるための一つの有効局所方法（有効局所オプティマイザとも呼ばれる）を以下に示すように組み合わせる。ハイブリッド法は、前者の方法の信頼性と精度、および後者の方法の計算速度を併せ持つ。
ハイブリッド探索法
初期化：  初期点を与えられる。
【００９６】
ステップ１  ―  条件（Ｃ１）を充足し、（４．２）によって記述された非線形動的システムを初期点から少数のステップ間積分して、終点を獲得し、ステップ２に進む前にその終点を使って初期点を更新する。
【００９７】
ステップ２  ―  ステップ１における終点から出発し、有効局所オプティマイザを適用して探索処理を継続する。収束すれば立ち止まる。そうでない場合にはステップ１に戻る。
【００９８】
準ニュートン法、トラスト領域法、“山登り”法などの有効局所オプティマイザ（すなわち局所最適化方法）は、局所情報（勾配ベクトル、時にはヘシアン行列）を利用して有効に局所最適解を求める。しかし、各“山登り”法はそれ自身の“収束領域”を各局所最適解に対して持っている。初期点が局所最適解の安定化領域内に存在しない場合、この方法では解を求められずに発散する可能性がある。我々の動的軌跡に基づく方法は、局所最適解の収束領域内に初期点を配置することができ、そこから“山登り”法で解を求める。従って、ハイブリッド探索方法は、局所最適解を求める際の計算効率を維持しながら“山登り”法の信頼性を高める。
【００９９】
（ロバスト）理論に基づくハイブリッド探索方法の理論的根拠は以下のとおりである。
探索スペース
2005508026.tif 000033
【０１００】
換言すれば、探索空間は非線形動的システム（４．２）の各安定平衡点の準安定化領域の閉包に等しい。したがって、探索空間の各点は、一般的に安定平衡点の準安定化領域内に存在する。この結果、（４．２）の各軌跡は局所最適解である安定平衡点で収束し、特に、ある有限時間の後の軌跡は、“山登り”法の安定化領域内にとどまり、そこから、その“山登り”法で局所最適解を求める。
別の局所最適解のための決定論的探索
大域最適解の探索における二つの重要な課題は、以下のとおりである。
【０１０１】
（ｉ）局所最適解から有効に移動（脱出）し、別の局所最適解に向かって移動する方法。
（ii）すでに求められた局所最適解の再訪を回避する方法。
【０１０２】
（iii）局所最適解を含まないか、あるいは前に求められた局所最適解を含む領域の探索を回避する方法。
過去においてこれらの課題を解決するために多大な努力が払われてきたが、あまり成功しなかった。本発明においては、これらの課題を克服するための、ＤＤＰに基づいた探索方法および再訪防止探索方法が展開され、動的軌跡に基づく方法に組み込まれる。これらの方法の展開において動的分解点は極めて重要な役割を果たす。次に、以下の作業のための手法の展開において、動的分解点を使うことができることを示すこととする。
【０１０３】
ステップ１  −  局所最適解から脱出する。
ステップ２  −  別の局所最適解の存在を保証する。
ステップ３  −  ステップ２の局所最適解の再訪を回避する。
【０１０４】
ステップ４  −  ステップ２の局所最適解の探索を支援する。
ステップ５  −  探索経路に沿った別の近傍局所最適解が存在しないことを保証する。
上記５つの作業を実行するために、動的分解点がどのように使われることができるかを示すための数値方法を提示することとする。特に、別の局所最適解を決定論的に求めるために局所最適解から探索を行う手順を実行するための数値方法を以下に示す。ｘoptを局所最適解であるとする。
【０１０５】
与えられるもの：  局所最適解、例えばｘopt
目的：  別の局所最適解を求める
ステップ１：  ｘoptから出発する探索経路に沿って移動し、ＤＤＰ探索方法を適用して対応するＤＤＰを計算し、ステップ２に進む。ＤＤＰを求めることができない場合、別の探索経路を試し、このステップを繰り返す。
【０１０６】
ステップ２： （再訪防止探索方法）
ＤＤＰをｘdとして表わすものとする。ｘdが前に求められている場合、ステップ１に進む。そうでない場合にはステップ３に進む。
【０１０７】
ステップ３  −  （ＤＤＰに基づく数値方法）
εが小さい数であるようなＤＤＰに基づく初期点ｘ0＝ｘopt＋（１＋ε）（ｘd−ｘopt）を計算する（ｘ0は、対応する近傍局所解の準安定化領域内に存在する）。ハイブリッド探索方法をｘ0から適用し、対応する近傍局所最適解を求める。
【０１０８】
（定理４−１による）ＤＤＰの存在によってステップ１が首尾よく定義されたことを保証する。
二つの異なる探索経路が同じＤＤＰを持つことができる。ステップ１で求められた動的分解点が既知である場合、定理４−２に従って、ｘoptに加えて、動的分解点ｘdに関連する唯一の局所最適解が存在する。従って、その局所最適解は以前求められたものであるはずなので、他の局所最適解を探索する必要はない。このようにして、ステップ２の手法により既知の局所最適解の再訪防止探索が提供される。
【０１０９】
ｘdの不安定多様体はわずかに二つの平衡点、すなわちｘoptともう一つ、例えばｘanooptに収束するので、これにより二つの局所最適解を同じＤＤＰの不安定多様体を介して接続することが可能になる。ステップ２の手法によって、以前求めた局所最適解の再訪防止探索の機能が再度提供される。
【０１１０】
探索経路を与えられると、ＤＤＰの存在によって、探索経路の方向における別の局所最適解が存在することが保証される。同様に、ＤＤＰが存在しないことによって、探索経路の方向における別の近傍局所最適解が存在しないことが保証される。
【０１１１】
この方法の根拠を以下に述べる。最適化問題（４．１）の局所最適解から如何に脱出して別の局所最適解に如何に移動するかという問題を、（４．２）の対応する（漸近的）安定平衡点（ｓ．ｅ．ｐ．）の準安定化領域から如何に脱出し、（４．２）の別の対応するｓ．ｅ．ｐ．の準安定化領域に如何に入るかという問題として扱うこととする。これら二つのｓ．ｅ．ｐ．の準安定化領域の閉包間の交点は、動的分解点の安定多様体であるということが分かる。さらに、動的分解点の不安定多様体はこれら二つのｓ．ｅ．ｐ．を接続する。システム軌跡がｓ．ｅ．ｐ．の安定化領域内にひとたび存在すれば、次のシステム軌跡は（４．１）の局所最適解であるそのｓ．ｅ．ｐ．に収束する。
制約条件なし非線形プログラミング問題のための大域最適化方法
制約条件なし最適化問題を解くための我々の発明した方法は、以下のように制約条件付き最適化問題を解くために適用することができる。
【０１１２】
ステップ１  ―  制約条件付き最適化問題を制約条件なし最適化問題に変換するために使うことのできる、変換手法を使用する。
ステップ２  −  我々の発明した方法を適用して、変換された制約条件なし最適化問題を解く。
【０１１３】
ここで、任意の初期点から出発し、（４．１）の大域最適解と共に全ての局所最適解を体系的に計算するための動的軌跡に基づく方法を提示することとする。この動的軌跡に基づく方法の構成は図１３に示されており、そのフローチャートが図１４に示されている。
【０１１４】
ステップ１  −  （初期化）
出発点を選択し、動的分解点の集合Ｖ0d＝｛φ｝、および局所最適解の集合Ｖ0s＝｛φ｝を設定する。
【０１１５】
ステップ２  −  （局所最適解を求める）
出発点を使用して上記の理論に基づくハイブリッド探索方法を適用し、局所最適解、例えばｘ0sを求め、ｊ＝０およびＶjnew＝｛φ｝を設定する。
【０１１６】
ステップ３  −  ｊ＝ｊ＋１を設定する。集合Ｖjnewの各局所最適解、例えばｘjsに対して以下のステップ４−６を実行する。
ステップ４  −  （全ての近傍動的分解点を求める。）
探索ベクトルｓji，ｉ＝１，２，．．．，ｍの集合を定義する。
【０１１７】
各探索ベクトルｓjiに関し、上記に提示した数値ＤＤＰ探索方法を適用して対応するＤＤＰを求める。対応するＤＤＰをｘid,jとして表す。Ｖjd＝Ｖjd∪｛ｘid,j｝を設定する。
【０１１８】
ステップ５  −  （動的分解点の評価）
計算された全ての動的分解点の集合Ｖjdを調査し、同じ動的分解点を、一つだけを集合に残して削除する。
【０１１９】
ステップ６  −  （全ての近傍局所最適解を求める）
集合Ｖjdの各動的分解点ｘid,jに対し、以下のステップを行って対応する近傍局所最適解を求める（各動的分解点によって一つだけ局所最適解が求められる）。
【０１２０】
ステップ６．１  −  （有効初期点を計算する）
ｘi0,j＝ｘjs＋（１＋ε）（ｘid,j−ｘjs）を設定する。ここでεは小さい数である。（ｘi0,jは対応する近傍局所最適解の安定化領域内に存在する）。
【０１２１】
ステップ６．２  −  （初期探索）
ｘi0,jを初期条件として使用し、非線形システム（４．２）を積分して少数のタイムステップの間軌跡φt（ｘi0,j）を得る。（軌跡φt（ｘi0,j）は対応する近傍局所最適解に収束する）。
【０１２２】
ステップ６．３  −  （ハイブリッド探索）
近傍局所最適解への探索処理の速度を早くするためには、軌跡φt（ｘi0,j）の収束実行を監視し、早く収束するように有効局所オプティマイザに適切に切り替える。解をｘks,jとする。
【０１２３】
ステップ６．４  −  局所最適解ｘjsおよび動的分解点ｘid,jに関する局所最適解はｘks,jである。Ｖj+1s＝Ｖjs∪｛ｘks,j｝を設定する。
ステップ７  −  （局所最適解の評価）
新しく計算された全ての局所最適解の集合Ｖjnew＝Ｖj+1s−Ｖjsを調査し、冗長なものがあれば、一つを集合に残して削除する。集合Ｖjnewが空でない場合ステップ３に戻る。そうでない場合は次のステップに進む。
【０１２４】
ステップ８  −  （大域最適解を求める）
ステップ７で求められた局所最適解の集合Ｖj+1sから、それらの目的関数の値を比較することによって大域最適解を識別する。
例２：  制約条件付き非線形プログラミング問題のための大域最適方法
一般的制約条件付き非線形最適化問題の形態を考える。
【０１２５】
2005508026.tif 000034
ここで目的関数Ｃ：／Ｒn→／Ｒは以下のように限定された滑らかな関数であり、等式制約条件関数ｈi：／Ｒn→／Ｒ、および不等式制約条件関数ｇj：／Ｒn→／Ｒは共に全ｉ∈Ｉ，ｊ∈Ｊに関して連続している。
【０１２６】
（４．５）の制約条件集合を以下のように定義する。
2005508026.tif 000035
これは／Ｒnの任意の閉じられた部分集合であってよく、その構造は大変複雑になり得る。集合ＣＳは、通常凸ではなく、接続されていない。すなわち、いくつかの（交わらない）接続された実行可能領域から構成される。集合ＣＳの接続された各実行可能領域を配置する作業は、それ自体が難しいことである。
【０１２７】
（４．５）における不等式を、スラック変数ｓjを導入することによって等式ｇj（ｘ）＋ｓ2j，ｊ∈Ｊとして表すことができる。元問題（４．５）を以下の（４．７）のような、不等式制約条件なしの最適化問題に縮小する他の変換手法も使用することができる。従って、汎用性を失うことなく、等式制約条件付きの次の最適化問題を考えることとする。
【０１２８】
2005508026.tif 000036
さらに、次の等式ベクトルを定義する。
【０１２９】
Ｈ（ｘ）：＝（ｈ1（ｘ），．．．ｈm（ｘ））T
いくつかの一般的な条件下では、実行可能集合あるいは実行可能領域とも呼ばれる以下の制約条件集合は、滑らかな多様体であることが分かる。
【０１３０】
2005508026.tif 000037
一般的に、制約条件集合Ｍは、交わらない、経路接続された実行可能成分で大変複雑になり得る。換言すれば、制約条件集合Ｍは、いくつかの交わらない、経路接続された、例えば以下のような実行可能成分に分解することができる。
【０１３１】
【数２１】
2005508026.tif 000038
【０１３２】
ここで各Ｍkは経路接続された実行可能成分である。経路接続された各成分は、最適化問題の局所最適解をいくつか含んでいる可能性がある。
制約条件付き最適化問題（４．５）の局所最適解を有効に求めことのできる利用可能な（局所）最適化方法がいくつかあるが、大域最適解を求めることはできない。探索処理の間、これらの方法は通常局所最適解で捕捉され、別の局所最適解に移動することができなくなる。制約条件付き非線形最適化問題（４．５）の大域最適解を求める唯一の確実な方法は、次の二つの作業によって有効に実行することができる。
【０１３３】
ステップ１  −  全ての実行可能成分Ｍk，ｋ−１，２，．．．を求める。
ステップ２  −  各実行可能成分における全ての局所最適解を求める。
この発明において、（４．５）の全ての局所最適解を体系的に計算するための数値２フェーズ動的軌跡に基づく方法を展開することとする。各フェーズの主要な作用は以下のとおりである。
【０１３４】
フェーズＩ：  任意の初期点から出発し、以下の汎用形式によって記述された、ある動的システムの軌跡に基づく制約条件（実行可能）集合Ｍの全ての実行可能成分Ｍkを体系的に求める。
【０１３５】
【数２２】
2005508026.tif 000039
【０１３６】
フェーズII：  以下の汎用形式によって記述された、別の動的システムの軌跡に基づく制約条件集合Ｍの各実行可能成分における全ての局所最適解を求める。
【０１３７】
【数２３】
2005508026.tif 000040
【０１３８】
非線形動的システムの構築ガイドライン
非線形非双曲型動的システムのいくつかの関連する概念を検討してきた。次に、軌跡をステップ１およびステップ２を実行するために使用することのできる非線形動的システムを構築するための一般的ガイドラインを提示することとする。
数学的予備事項
以下によって記述された非線形非双曲型動的システムを考える。
【０１３９】
【数２４】
2005508026.tif 000041
【０１４０】
ここでＨ：／Ｒn→／ＲmおよびＭ：／Ｒn→／Ｒn×m、ｎ≧ｍは解の存在と一意性のための十分条件を充足する。ゼロ集合ＥF≡Ｆ-1（０）は通常、経路接続された、いくつかの成分から構成される。
【０１４１】
ゼロ集合Ｆ-1（０）、例えばΣの経路接続された（完全連続）成分は、システム（４．１１）の“平衡多様体”と呼ばれる。φ∞:Ｂe（Σ）→ΣがＲnからＲlの射影に対して局所的に同相写像であるようなε＞０が存在する場合、（４．１１）の平衡多様体Σはｌ次元であるという。 各ｘ∈Σに関して  ＪNH（ｘ）で表される、ｘにおけるＮHのヤコビアンが通常空間Ｎx（Σ）、すなわち／ＲnのｘにおけるΣの正接空間Ｔx（Σ）の直交補集合上でゼロ実数部分のある固有値を持たない場合、（４．１１）の平衡多様体Σは双曲型であると言う。各ｘ∈Σに関し、Ｎx（Σ）上の対応するヤコビアンの固有値すべてが負の実数部分を持つ場合に、双曲型平衡多様体Σは（漸近的）安定平衡多様体である。あるいは各ｘ∈Σに関し、Ｎx（Σ）上の対応するヤコビアンの全ての固有値が正の実数部分を持つ場合に、双曲型平衡多様体Σは不安定平衡多様体である。
【０１４２】
双曲型平衡多様体Σに関し、その安定および不安定多様体ＷsF（Σ），ＷuF（Σ）は以下のように定義される。
【０１４３】
【数２５】
2005508026.tif 000042
【０１４４】
安定平衡多様体Σsの安定化領域は次のように定義される。
【０１４５】
【数２６】
2005508026.tif 000043
【０１４６】
ガイドライン
ステップ１およびステップ２を実行するための非線形動的システムを構築する方法はいくつかある。このような非線形動的システムを構築するための以下のガイドラインを提案することとする。ステップ１を実行するための計算手法を展開するために軌跡を使うことのできる非線形動的システムは、以下の二つの条件を充足する必要がある。
【０１４７】
（Ｃ１−１）  各システム軌跡が収束し、なおかつ平衡多様体の一つに収束する。
（Ｃ１−２）  集合が制約条件付き非線形最適化問題（４．７）の経路接続された実行可能成分である場合に限り、その集合は非線形動的システムの安定平衡多様体である。
【０１４８】
条件（Ｃ１−１）は、非線形動的システムの限界集合が平衡多様体のみから構成され、リミットサイクルやカオスなど他の安定状態のタイプはシステムに存在しないことを意味する。条件（Ｃ１−１）および（Ｃ１−２）は共に、非線形動的システムのほぼあらゆる軌跡が、制約条件付き最適化問題（４．７）の経路接続された実行可能成分に収束することを確実にする。
【０１４９】
ステップ２を実行するための計算の手法を展開するために軌跡を使うことのできる非線形動的システムは、以下の二つの条件を充足する必要がある。
（Ｃ２−１）  各システム軌跡が収束し、なおかつ平衡点の一つに収束する。
【０１５０】
（Ｃ２−２）  点、例えばｘks,jが漸近的安定平衡点であり、Ｍkが非線形動的システムの不変集合である場合に限り、ｘks,jは非線形最適化問題の実行可能成分Ｍkに存在する局所最適解である。
【０１５１】
条件（Ｃ２−１）は、作業２を実行するための非線形動的システムの限界集合が平衡点のみで構成され、安定状態の他のタイプは非線形システムに存在し得ないことを意味する。条件（Ｃ２−２）は、別の局所最適解を探索する処理の間、システム軌跡が実行可能成分Ｍkにとどまり、制約条件集合が常に充足されることを確実にする。
【０１５２】
条件（Ｃ１−１）および（Ｃ１−２）を充足する非線形動的システムの一例は以下のとおりである。
【０１５３】
【数２７】
2005508026.tif 000044
【０１５４】
ここでベクトルＨ（ｘ）は実行可能領域を定義する制約条件ベクトルである。
条件（Ｃ２−１）および（Ｃ２−２）を充足する非線形動的システムの一例が以下の動的システムである。
【０１５５】
【数２８】
2005508026.tif 000045
【０１５６】
ここで射影行列
ＰH（ｘ）＝（Ｉ−ＤＨ（ｘ）T（ＤＨ（ｘ）ＤＨ（ｘ）T）-1ＤＨ（ｘ））∈／Ｒn×nは各ｘ∈Ｍに関し、正の準明確行列である。ＰH（ｘ）∇Ｃ（ｘ）は、正接空間ＴxＭに直行する∇Ｃ（ｘ）の射影であり、全ｘ∈Ｍに関してＰH（ｘ）∇Ｃ（ｘ）∈ＴxＭを意味する。なお、ｘ0∈Ｍkから出発する（４．１３）の各軌跡はＭkにとどまる。換言すれば、Ｍkは（４．１３）の不変集合である。射影行列ＰH（ｘ）は、Ｈ（ｘ）によって特徴付けられる制約条件集合に関連する。
２フェーズの動的軌跡に基づく方法
本発明は、制約条件付き（連続）非線形最適化問題（４．７）の全ての局所最適解を体系的に計算するための２フェーズの動的軌跡に基づく方法を展開する。この動的軌跡に基づく方法は２つの別個のフェーズで構成される。すなわち、フェーズＩでは、任意の出発点から出発し、制約条件集合を充足する全ての実行可能成分を体系的に求める。フェーズＩＩでは、動的軌跡に基づく方法のフェーズＩで求められた各実行可能成分における全ての局所最適解を計算する。
フェーズＩ
動的軌跡に基づく方法のフェーズＩでは、非線形動的システムの軌跡をいくつか使って全ての実行可能成分を求める。制約条件集合Ｍの経路接続された各実行可能成分を訪れるために、フェーズＩでは二つの主要ステップがある。
【０１５７】
ステップ１．１  −  制約条件付き最適化問題（４．７）の経路接続された実行可能成分にアプローチする。
ステップ１．２  −  経路接続された実行可能成分から脱出し、制約条件付き最適化問題（４．７）の経路接続された別の実行可能成分に接近する。
【０１５８】
条件（Ｃ１−１）および（Ｃ１−２）を充足する非線形動的システム（４．９）の設計を提案することとする。ステップ１．１およびステップ１．２を実行するための手法を展開するためにいくつかのシステム軌跡を利用する。非線形動的システム（４．９）の設計における中心的考え方は、経路接続された各実行可能成分Ｍkが非線形動的システムの安定平衡多様体に対応するということである。このように、制約条件付き最適化問題（４．７）の経路接続された全ての実行可能成分を求める作業は、条件（Ｃ１−１）および（Ｃ１−２）を充足する非線形動的システム（４．９）の全ての安定平衡多様体を求めることによって実現することができる。
【０１５９】
最適化問題（４．７）の各実行可能成分は、非線形動的システム（４．９）の各安定平衡多様体を使って配置することができることが分かる。
この方法のフェーズＩを数値的に実現するために、次の二つの作業が行われる。
【０１６０】
ステップ１．１  −  非線形動的システム（４．９）の安定平衡多様体に接近する。
ステップ１．２  −  安定平衡多様体から脱出し、非線形動的システム（４．９）の別の安定平衡多様体に接近する。
【０１６１】
非線形動的システム（４．９）の軌跡を、（最適化問題（４．７）の実行不可能点になりうる）任意の初期点から出発して、システム（４．９）の安定平衡多様体に配置される点（すなわち最適化問題（４．７）の実行可能成分に配置された点）の方へたどることによって、ステップ１．１を数値的に実現することができる。また、軌跡をシステム（４．９）の安定多様体における初期点から時間に逆行して、（４．９）の安定平衡多様体の安定化境界上の不安定平衡多様体における点に接近するまでたどり、次に不安定平衡多様体に近いが安定化領域外にある初期点から出発し、最適化問題（４．７）の別の実行可能成分である、（４．９）の別の安定平衡多様体に接近するまで軌跡をたどることによって、ステップ１．２を数値的に実現することができる。
フェーズII
２フェーズの動的軌跡に基づく方法のフェーズIIでは、条件（Ｃ２−１）および（Ｃ２−２）を充足する非線形動的システム（４．１０）の軌跡に基づく各実行可能成分における全ての局所最適解を求める。各実行可能成分に配置されている全ての局所最適解を訪れるために、フェーズＩＩには二つの主要ステップがある。
【０１６２】
ステップ２．１  −  フェーズＩで求められた実行可能成分における点から出発し、最適化問題（４．７）の実行可能成分に配置された局所最適解に接近する。
ステップ２．２  −  局所最適解から脱出し、最適化問題（４．７）の同じ実行可能成分の別の局所最適解に接近する。
【０１６３】
条件（Ｃ２−１）および（Ｃ２−２）を充足する非線形動的システム（４．１０）の設計を提案することとする。そして、ステップ２．１およびステップ２．２を実行するための手法を展開するためにシステム軌跡をいくつか使うこととする。非線形動的システム（４．１０）の設計における重要な考え方は、最適化問題（４．７）の全ての局所最適解が非線形動的システム（４．１０）の全ての安定平衡点に対応するということである。特に、最適化問題（４．７）の各局所最適解は、条件（Ｃ２−１）および（Ｃ２−２）を充足する非線形動的システム（４．１０）の安定平衡点に対応する。このように、条件（Ｃ２−１）および（Ｃ２−２）を充足する非線形動的システム（４．１０）の全ての安定平衡点を求めることによって、制約条件付き最適化問題（４．７）の経路接続された全ての実行可能成分を求める作業を実現することができる。
【０１６４】
この方法のフェーズＩＩを数値的に実現するために、次の３つの作業が提案される。
ステップ２．１  −  非線形動的システム（４．１０）の安定平衡点を求める。
ステップ２．２  −  （局所最適解から脱出するために）安定平衡点から動的分解点に移動する。
【０１６５】
ステップ２．３  −  動的分解点を介して、非線形動的システム（４．１０）（経路接続された同じ実行可能成分における）の別の安定平衡点に接近する。
ステップ２．１を数値的に実現するためにハイブリッド探索方法を実行可能成分に配置された任意の初期点から使用する。ステップ２．２は、この明細書中に提示された（数値）動的分解点方法を適用することによって数値的に実現することができる。ステップ２．３は、ＤＤＰの不安定多様体が収束する別の局所最適解を求めるために、ハイブリッド探索方法と組み合わせて、ＤＤＰに基づく数値方法を適用することによって、数値的に実現することができる。
【０１６６】
経路接続された各実行可能成分は、非線形動的システム（４．１０）の不変集合であるので、成分の任意の点、例えばＭkから出発する各軌跡は正負両方の時間に対してＭkにとどまる。したがって、動的軌跡に基づく方法のフェーズＩＩは、経路接続された他の成分の局所最適解ではなく、経路接続されたその成分の全ての局所最適解を求めるだけである。経路接続された他の実行可能成分に配置される局所最適解を求めるためには、再度フェーズＩを起動して実行可能領域のある実行可能成分から移動し、別の実行可能成分に接近する必要がある。
【０１６７】
要するに、動的軌跡に基づく方法は二つの別個のフェーズで構成される。フェーズＩは、任意の出発点から出発し、制約条件集合を充足する全ての実行可能成分を体系的に求める。フェーズＩＩは、動的軌跡に基づく方法のフェーズＩで求められた各実行可能成分における全ての局所最適解を計算する。動的軌跡に基づく方法のフェーズＩおよびフェーズＩＩを交互に行うことにより（すなわち非線形動的システム（４．９）と非線形動的システム（４．１０）を切り替えることにより）、制約条件付き最適化問題（４．７）の全ての局所最適解を求めることができる。
ハイブリッド探索方法
フェーズＩおよびフェーズIIのためのハイブリッド探索方法が本発明において展開され、大域オプティマイザに組み込まれた。これらの方法は動的軌跡方法と、実行可能成分を求め(フェーズＩ)、局所最適解を求める(フェーズII)ための一つの有効局所方法を組み合わせる。ハイブリッド方法は、前者の方法の信頼性と精度、および後者の方法の計算速度を併せ持つ。
フェーズＩのためのハイブリッド探索方法
初期化：  初期点を与えられる
ステップ１  −  条件（Ｃ１−１）を充足する、（４．９）によって記述された非線形動的システムを、初期点から少数のタイムステップ間積分して終点を獲得し、ステップ２に進む前にその終点を使って初期点を更新する。
【０１６８】
ステップ２  −  ステップ１の終点から出発し、有効局所オプティマイザを適用して実行可能成分を求め、探索処理を継続する。収束する場合は立ち止まる。そうでない場合にはステップＩに戻る。
フェーズIIのためのハイブリッド探索方法
初期化:  実行可能成分に存在する初期点を与えられる。
【０１６９】
ステップ１  −  条件（Ｃ２−１）を充足する、（４．１０）によって記述された非線形動的システムを初期点から少数のタイムステップ間積分して終点を獲得し、ステップ２に進む前にその終点を使って初期点を更新する。
【０１７０】
ステップ２  −  ステップ１における終点から出発し、有効局所オプティマイザを適用して実行可能成分を求め、探索処理を継続する。収束する場合は、立ち止まる。そうでない場合にはステップ１に戻る。
制約条件付き非線形プログラミング問題のための大域最適化方法
ここで、任意の初期点から出発し、（４．７）の大域最適解と共に全ての局所最適解を体系的に計算する２フェーズの動的軌跡に基づく方法を提示することとする。この動的軌跡に基づく方法の構成を図１３に示す。フェーズＩＩの手順は、上記した、制約条件なし非線形プログラミング問題のための大域最適化方法の手順と同様である。さらに、安定平衡多様体の役割が安定平衡点の役割に取って代わり、また不安定平衡多様体の役割が動的分解点の役割に取って代わる以外は、フェーズＩの手順は、制約条件なし非線形プログラミング問題のための大域最適化方法の手順と同様である。
フェーズＩのための数値方法
ステップ１  −  （初期化）
出発点を選択し、動的分解点の集合Ｖ0d＝｛φ｝、および局所最適解の集合Ｖ0s＝｛φ｝を設定する。
【０１７１】
ステップ２  −  （経路接続された実行可能成分を求める）
出発点を使用してハイブリッド探索方法を適用し、経路接続された実行可能成分における点を求める。求められた点を初期点として設定する。
【０１７２】
ステップ３  −  （経路接続された実行可能成分における全ての局所最適解を求める）
初期点から出発して（以下に示す）フェーズＩＩのための数値方法を適用し、経路接続された実行可能成分における全ての局所最適解を求める。
【０１７３】
ステップ４  −  （全ての近傍不安定平衡多様体を求める）
探索ベクトルｓji，ｉ＝１，２，．．．,ｋの集合を定義する。
各探索ベクトルｓjiに対し、逆行時間軌跡方法を適用して不安定平衡多様体に存在する点を求める。点が求められた場合、ｘid,jとして表し、ステップ５に進む。そうでない場合にはステップ６に進む。
ステップ５  −  （全ての近傍安定平衡多様体、すなわち実行可能成分を求める）
ステップ４で求められた各点ｘid,jに対し、以下のステップを実行して（経路接続された）実行可能成分における点を求める。
ステップ５．１  −  （有効初期点を計算する）
Ｓｅｔ ｘi0,j=ｘjs+(1+ε)(ｘid,j-ｘjs)を設定する。ここでεは小さい数であり、ｘjsはステップ３で求められた局所最適解である。（ｘi0,jは対応する近傍安定平衡多様体の安定化領域内に存在する）。
【０１７４】
ステップ５．２  −  （初期探索）
ｘi0,jを初期条件として使用し、非線形システム（４．９）を積分して少数タイムステップの間軌跡φt(ｘi0,j)を得る。（軌跡φt(ｘi0,j)は対応する安定平衡多様体に収束する）。
【０１７５】
ステップ５．３  −  (ハイブリッド探索)
ステップ５．２の終点を初期点として使用してハイブリッド探索方法を適用し、安定平衡多様体に存在する点に早く収束させる。解をｘks,jとし、初期点として設定したらステップ３に戻る。
【０１７６】
ステップ６  −  （大域最適解を求める）
ステップ３で求められた局所最適解の集合から、それらの目的関数の値を比較することによって大域最適解を識別する。
フェーズIIのための数値方法
ステップ１  −  （初期化）
動的分解点の集合Ｖ0d＝｛φ｝、および局所最適解の集合Ｖ0s＝｛φ｝を設定する。
【０１７７】
ステップ２  −（局所最適解を求める）
フェーズＩＩのためのハイブリッド探索方法を初期点から適用し、局所最適解、例えばｘsを求め、ｊ＝０およびＶjnew＝｛ｘs｝を設定する。
【０１７８】
ステップ３  −  ｊ＝ｊ＋１を設定する。集合Ｖjnewにおける各局所最適解、例えばｘjsに対して、以下のステップ４からステップ６を実行する。
ステップ４  −  （全ての近傍動的分解点を求める）。
【０１７９】
探索ベクトルｓji ，ｉ＝１，２，．．．，ｍの集合を定義する。
各探索ベクトルｓjiに対し、非線形動的システム（４．１０）を代わりに使用して対応するＤＤＰを求める以外は、セクション４．１．３で提示された数値ＤＤＰ探索方法を適用する。ＤＤＰをｘid,jとして表す。Ｓｅｔ Ｖjd＝Ｖjd∪｛ｘid,j｝を設定する。
【０１８０】
ステップ５  −  （動的分解点の評価）
計算された全ての動的分解点の集合Ｖjdを調査し、同じ動的分解点を、一つを集合に残して削除する。
【０１８１】
ステップ６  −  （全ての近傍局所最適解を求める）
集合Ｖjdにおける各動的分解点ｘid,jに対し、以下のステップを実行して対応する近傍局所最適解を求める。
【０１８２】
ステップ６．１  −  （有効初期点を計算する）
Ｓｅｔ ｘi0,j=ｘjs+(1+ε)(ｘid,j-ｘjs)を設定する。ここでεは小さい数である。（ｘi0,j）は対応する近隣局所最適解の安定化領域内に存在する）。
【０１８３】
ステップ６．２  −  （初期探索）
ｘi0,jを初期条件として使用し、非線形システム（４．１０）を積分して少数のタイムステップの間、軌跡φt(ｘi0,j)を得る。（軌跡φt(ｘi0,j)は対応する近傍局所最適解に収束する）。
【０１８４】
ステップ６．３  −  （ハイブリッド探索）
ステップ６．２の終点を初期点として使用してハイブリッド探索方法を適用し、局所最適解に素早く収束させる。解をｘks,jとする。
【０１８５】
ステップ６．４  −  局所最適解ｘjsおよび動的分解点ｘid,jに関する局所最適解はｘks,jである。Set Ｖj+1s＝Ｖjs∪｛ｘks,j｝を設定する。
ステップ７  −  （局所最適解の評価）
新しく計算された全ての局所最適解の集合Ｖjnew＝Ｖj+1s−Ｖjsを調査し、冗長な局所最適解がある場合には、一つを集合に残して削除する。集合Ｖjnewが空でない場合ステップ３に戻る。そうでない場合には立ち止まる。
【０１８６】
したがって、この明細書中に述べた本発明の実施形態は、本発明の原理の適用を単に説明したものであるということが理解されるべきである。説明された実施形態の詳細に関するこの明細書中の記載は請求の範囲を限定するものではなく、本発明に必須であるとみなされる特徴を記述するものである。
【図面の簡単な説明】
【０１８７】
【図１】制約条件なし最適化問題における６つの局所最適解の存在を仮定することを示す図である。
【図２】図１の６つの局所最適解が非線形動的システムの安定平衡点になり、各安定平衡点がそれ自身の準安定化領域を持つ事を示す図である。
【図３】ｘ0がｘ3sの準安定化領域内に存在し、動的軌跡に基づく方法に組み込まれたハイブリッド方法が局所最適解ｘ3sを求める事を示す図である。
【図４】局所最適解ｘ3sで出発し、動的軌跡に基づく方法が有効に局所最適解から脱出し、進行してｘ1s，ｘ2s，ｘ6sの準安定化領域内にそれぞれ存在する３つの点ｘ10，ｘ20，ｘ60を求める事を示す図である。
【図５】３つの点ｘ10，ｘ20，ｘ60から出発し、動的軌跡に基づく方法に組み込まれたハイブリッド方法が局所最適解ｘ1s，ｘ2s，ｘ6sそれぞれを求める事を示す図である。
【図６】ｘSから出発する探索経路φt（ｘs）が出口点ｘexで、ｘSの準安定化境界と交差する事を示す図である。
【図７】出口点ｘexが初期条件として使用され、図２の非線形システムが動的分解点ｘ6uまで積分されることを示す図である。
【図８】シミュレーションされた出口点ｘ*が初期条件として使用され、小数のタイムステップ、例えば５の間、非線形システムが積分されることを示す図である。
【図９】軌跡上の現在点と局所最適解ｘsを結ぶ線を示す図である。安定平衡点から出発する線に沿った、目的関数の（最初の）局所最大点である訂正された出口点で現在点を置き換える。この点を出口点に代入する。
【図１０】訂正された出口点が初期条件として使用され、少数のタイムステップ、例えば５の間、非線形システムが積分されることを示す図である。
【図１１】軌跡上の現在点と局所最適解ｘsを結ぶ線を示す図である。安定平衡点から出発する線に沿った、目的関数の（最初の）局所最大点である訂正された出口点で現在点を置き換える。この訂正された出口点はしきい値より小さいので、この点はＭＤＰとして宣言される。
【図１２】非線形代数ソルバに対して、ＭＤＰが動的分解点ｘ6uの収束領域内に存在し、このソルバが容易にｘ6uを計算して求めることができることを示す図である。
【図１３】制約条件なし最適化問題のための本発明の動的軌跡に基づく方法の全体構造のフローチャートを示す図である。初期点を与えられると、局所最適解と大域最適解の一式を生成する。
【図１４】制約条件なし最適化問題のための本発明の動的軌跡に基づく方法のフローチャートを示す図である。
【図１５】制約条件付き最適化問題のための本発明の動的軌跡に基づく方法の全体構造のフローチャートを示す図である。初期点を与えられると、局所最適解と大域最適解の一式を生成する。
【図６】
2005508026.tif 000054
【図１３】
2005508026.tif 000055
【図１４】
2005508026.tif 000056
【図１５】
2005508026.tif 000057
【国際公開パンフレット】
2005508026.tif 000058
2005508026.tif 000059
2005508026.tif 000060
2005508026.tif 000061
2005508026.tif 000062
2005508026.tif 000063
2005508026.tif 000064
2005508026.tif 000065
2005508026.tif 000066
2005508026.tif 000067
2005508026.tif 000068
2005508026.tif 000069
2005508026.tif 000070
2005508026.tif 000071
2005508026.tif 000072
2005508026.tif 000073
2005508026.tif 000074
2005508026.tif 000075
2005508026.tif 000076
2005508026.tif 000077
2005508026.tif 000078
2005508026.tif 000079
2005508026.tif 000080
2005508026.tif 000081
2005508026.tif 000082
2005508026.tif 000083
2005508026.tif 000084
2005508026.tif 000085
2005508026.tif 000086
2005508026.tif 000087
2005508026.tif 000088
2005508026.tif 000089
2005508026.tif 000090
2005508026.tif 000091
2005508026.tif 000092
2005508026.tif 000093
2005508026.tif 000094
2005508026.tif 000095
2005508026.tif 000096
2005508026.tif 000097
2005508026.tif 000098
2005508026.tif 000099
2005508026.tif 000100
2005508026.tif 000101
2005508026.tif 000102
2005508026.tif 000103
2005508026.tif 000104
2005508026.tif 000105
2005508026.tif 000106
2005508026.tif 000107
2005508026.tif 000108
2005508026.tif 000109
2005508026.tif 000110
2005508026.tif 000111
2005508026.tif 000112
2005508026.tif 000113
2005508026.tif 000114
2005508026.tif 000115
2005508026.tif 000116
2005508026.tif 000117
2005508026.tif 000118
2005508026.tif 000119
2005508026.tif 000120
2005508026.tif 000121
2005508026.tif 000122
2005508026.tif 000123
2005508026.tif 000124
2005508026.tif 000125