(57)【要約】【課題】初期推定（ｘf）が実行不可能な場合であっても、開始時に問題を緩和しないアルゴリズムが提供される。【解決手段】従来の方法のかわりに、このアルゴリズムでは、有効制約集合の初期推定を使用して、問題を緩和せずにＥＱＰを解く。この最初のＥＱＰの解が最適ではないが実行可能な場合、これを実行可能な点の推定として使用することができる。これは、初期有効制約集合と一貫性のある実行可能な点であるという利点を有するが、従来の方法で使用される初期推定は、必ずしもそうではない。【選択図】図１
2007226772.tif 000002
【特許請求の範囲】
【請求項１】
多変数システムを制御する方法において、
ａ）前記システムの現在の状態を示す複数のセンサ信号を受けるステップと、
ｂ）複数のコマンドを受けるステップと、
ｃ）前記コマンドおよび前記センサ信号に基づいて、前記システムの所望の動的応答を決定するステップと、
ｄ）複数の時間段階のそれぞれにおいて、前記所望の動的応答を、二次計画問題に対する解として実現するように、前記システムを制御する問題を定式化するステップと、
ｅ）最適化された解で効力をもつ制約の集合を含む最適な有効制約集合を探索する反復アルゴリズムを使用して、各時間段階で前記二次計画問題を解くステップと、
ｆ）前記複数の時間段階の各後時間段階において、
ｇ）ｘfを得るために、前記複数の時間段階の前時間段階の最後の有効制約集合に基づいて、前記二次計画問題を解くステップと、
ｈ）前記複数の時間段階の前時間段階の最後の有効制約集合と、ｘfが実行可能であるという仮定とに基づく、最適な有効制約集合の探索を初期化するステップと、
を含むことを特徴とする方法。
【請求項２】
前記ステップｈ）が、前記有効な制約をどれも緩和せずに実行されることを特徴とする請求項１記載の方法。
【請求項３】
前記ステップｈ）が、複数の前記有効な制約を緩和せずに実行されることを特徴とする請求項１記載の方法。
【請求項４】
前記ステップｆ）の各後時間段階において、
ｉ）前記ステップｇ）の後、ｘfが実行可能であるが、最適ではないと判定し、ｘfが実行可能であるという判定に基づいて、前記ステップｈ）でｘfを使用するステップをさらに含むことを特徴とする請求項３記載の方法。
【請求項５】
前記制約が、複数の重要な制約および複数の重要でない制約を含み、前記ステップｆ）の前記複数の後時間段階の１つにおいて、
ｉ）前記ステップｇ）後、ｘfが実行可能ではないことを判定するステップと、
ｋ）ｘfが実行可能ではないという前記判定に基づいて、前記複数の重要でない制約の少なくとも１つを緩和するステップと、
をさらに含むことを特徴とする請求項１記載の方法。
【請求項６】
ｌ）ｘfが、前記重要な制約に違反していないと判定するステップと、
ｍ）前記ステップｌ）に基づいて、次の実用的な制約の集合を、関連するラグランジュ乗数が負である制約を差し引いて、初期実用制約集合として使用するステップと、
をさらに含むことを特徴とする請求項５記載の方法。
【請求項７】
ｌ）ｘfが、前記重要な制約の少なくとも１つに違反していると判定するステップと、
ｍ）前記ステップｌ）に基づいて、ｘfの前記複数の重要な制約への射影ｘpを、前記解の新しい推定として使用するステップと、
をさらに含むことを特徴とする請求項５記載の方法。
【請求項８】
ｖが、どの制約を緩和すべきかを示すベクトルであり、前記ステップｋ）で、前記複数の重要でない制約が、追加変数ｔを導入することによって緩和され、前記ステップｌ）のｘpが前記重要な制約の少なくとも１つに違反するという前記判定に基づいて、初期有効制約集合でｘpが効力をもつ制約の数を最大にするように、前記ベクトルｖおよび前記ｔの値を変更するステップをさらに含むことを特徴とする請求項７記載の方法。
【請求項９】
所望の軌道を作成する所望の軌道ジェネレータと、
前記所望の軌道について線形化モデルを導出する線形化モジュールと、
複数の時間段階のそれぞれにおいて、前記所望の動的応答を、二次計画問題に対する解として実現するように、前記システムを制御する問題を定式化する二次計画法モジュールと、
最適な制御のプロファイルを生成するために、前記二次計画法モジュールによって確立された最適化問題を解く二次計画法ソルバと、
を含み、前記二次計画法ソルバが、最適な有効制約集合を探索する反復アルゴリズムを使用して、各時間段階で前記二次計画問題を解き、前記複数の時間段階の各後時間段階で、前記複数の時間段階の各後時間段階の前記二次計画法ソルバが、ｘfを得るために、前記複数の時間段階の前時間段階の最後の有効制約集合に基づいて、前記二次計画問題を解き、前記二次計画法ソルバが、前記複数の時間段階の前時間段階の最後の有効制約集合と、ｘfが実行可能であるという仮定とに基づく、最適な有効制約集合の探索を初期化することを特徴とする制御システム。
【請求項１０】
前記二次計画法ソルバが、前記有効な制約をどれも緩和せずに、前記最適な有効制約集合の探索を初期化することを特徴とする請求項９記載のシステム。
【請求項１１】
前記二次計画法ソルバが、各後時間段階において、ｘfが実行可能であるが、最適ではないと判定することを特徴とする請求項９記載のシステム。
【請求項１２】
前記制約が、複数の重要な制約および複数の重要でない制約を含み、前記二次計画法ソルバが、前記複数の後時間段階の１つにおいて、ｘfが実行可能かどうか判定し、ｘfが実行可能でないという前記判定に基づいて、前記複数の重要でない制約の少なくとも１つを緩和するようにプログラムされていることを特徴とする請求項９記載のシステム。
【請求項１３】
前記二次計画法ソルバが、ｘfが前記重要な制約に違反しているかどうか判定し、違反していない場合、次の実用的な制約の集合を、関連するラグランジュ乗数が負である制約を差し引いて、初期実用制約集合として使用するようにプログラムされていることを特徴とする請求項１２記載のシステム。
【請求項１４】
前記二次計画法ソルバが、ｘfが前記重要な制約に違反しているかどうか判定し、違反している場合、ｘfの前記複数の重要な制約への射影ｘpを、前記解の新しい推定として使用するようにプログラムされていることを特徴とする請求項１２記載のシステム。
【請求項１５】
ｖが、どの制約を緩和すべきかを示すベクトルであり、前記複数の重要でない制約が、追加変数ｔを導入することによって緩和され、前記二次計画法ソルバが、ｘpが前記重要な制約の少なくとも１つに違反するという前記判定に基づいて、初期有効制約集合でｘpが効力をもつ制約の数を最大にするように、前記ベクトルｖおよび前記ｔの値を変更するようにプログラムされていることを特徴とする請求項１４記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二次計画問題を実時間で効率的に解く。このような二次計画問題は、力学系の動的逆変換（Ｄｙｎａｍｉｃ  Ｉｎｖｅｒｓｉｏｎ）またはモデル予測制御（Ｍｏｄｅｌ  Ｐｒｅｄｉｃｔｉｖｅ  Ｃｏｎｔｒｏｌ（ＭＰＣ））における制約を満足させながら性能目標を満たすように、最適なアクチュエータコマンドを決定するために解く必要がある。
【０００２】
本発明は、米国海軍契約第Ｎ０００１９−０２−Ｃ−３００３号の履行の際に案出された。米国政府は、本発明において一定の権利を有することができる。
【背景技術】
【０００３】
時変システムは、システムの出力および性能指数を各瞬間ごとの入力と関係付ける線形代数方程式の集合によってモデル化することができる（非線形力学系では、これらの方程式は時間変化する）。これらの入力は正式には制御変数として知られている。というのは、こういった変数の値はオペレータの制御下にあるからである。その目的は、システムの性能指数を最大化する、最良の、時間に関する制御変数列を見つけることである。さらに、重大なシステム故障（ｓｙｓｔｅｍ  ｆａｉｌｕｒｅ）を避けるために、システムの物理的制約は守らなければならない。最良の制御変数列を決定するという問題は、時間に関する最適化問題列を、すなわち各瞬間ごとに新しい最適化問題を解く必要がある。このような最適化問題のそれぞれは、ほとんど瞬時に解かなければならない。高速動力学によるシステムでの動的逆変換の適用例では、これに数ミリ秒しか与えられない。したがって、最適化技法が解を迅速に見つけ出す要件が、これらの用途のかぎである。出願人が本発明の出願人である２つの同時係属の出願、２００２年１２月２日出願の「力学系の制御のための実時間二次計画法（Ｒｅａｌ−Ｔｉｍｅ  Ｑｕａｄｒａｔｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｆｏｒ  Ｃｏｎｔｒｏｌ  Ｏｆ  Ｄｙｎａｍｉｃａｌ  Ｓｙｓｔｅｍｓ）」（米国特許出願第１０／３０８，２８５号）、および２００３年２月１４日出願の「実時間モデル予測制御における二次計画法のための加速された有効制約集合探索のシステムおよび方法（Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｏｆ  Ａｃｃｅｌｅｒａｔｅｄ  Ａｃｔｉｖｅ  Ｓｅｔ  Ｓｅａｒｃｈ  ｆｏｒ  Ｑｕａｄｒａｔｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ  ｉｎ  Ｒｅａｌ−Ｔｉｍｅ  Ｍｏｄｅｌ  Ｐｒｅｄｉｃｔｉｖｅ  Ｃｏｎｔｒｏｌ）」（米国特許出願第１０／３６７，４５８号）には、解を効率的に得るための改善された技法が記載されている。
【０００４】
唯一の最適解が存在し、局所的な最小または最大が存在せず、解を合理的な計算によって確実に見つけることができるように、解は一般に凸形に制限され、時には二次計画法に制限される。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
このアルゴリズムはまた、実時間凸最適化問題を解く有効制約集合法（ａｃｔｉｖｅ  ｓｅｔ  ｍｅｔｈｏｄ）も使用する。このアルゴリズムでは、現在の問題における最良の有効制約集合（ａｃｔｉｖｅ  ｓｅｔ）の探索を初期化するために、前の解の有効制約集合を「フィードバック」する。これは、制御解が、ある更新から次の更新までの変化が微小になるほど十分に高い周波数で周期的に更新される制御システムでの適用を想定している。ただし、解の初期推定（アクチュエータコマンド）が実行不可能であり、かつ／または有効制約集合の初期推定と一貫性がない場合に、一定の困難が存在する。
【０００６】
二次計画問題の初期推定が実行可能ではない場合、従来の技法では追加変数ｔが導入される（ビッグＫ（ｂｉｇ−Ｋ）の定式化）。最適有効制約集合に存在するはずの制約が実行不可能な場合は、それが緩和される。ビッグＫ緩和問題からの最終解は常に、この制約に違反する（これには、線形ペナルティをＭ＞０で設定することで修正することができる）。
【０００７】
反復中に一貫性を保持することを支持する有力な論拠がある。というのは、そうでなければ、ある反復から別の反復まで目的関数が増加することがあり、制約が有効であると示されたときでさえ、右辺を厳密に満たさない可能性があるからである。さらに、一貫性のない状態で開始すると、最初のＥＱＰの解が制約のいずれかに違反する場合、現在の点はＥＱＰ解とｘf（実行可能な解の初期推定）の凸結合になる。現在の反復ｘと有効制約集合の間の一貫性が保持されているとしたら、ｘfが厳密に満たさない最初の有効制約集合における制約はいずれも外されているはずである。この結果、潜在的に期待できる制約が有効制約集合から外され、したがって良好な有効制約集合ホットスタートの利益が失われる。
【課題を解決するための手段】
【０００８】
本発明は、たとえｘfが実行不可能であるとしても、まさにその開始時に問題を緩和しないアルゴリズムを提供する。その代わりに、このアルゴリズムでは、有効制約集合の初期推定を使用して、問題を緩和せずにＥＱＰを解く。この解をｘ＿ｅｑｐ１と呼ぶ。非常に多くの場合、これが最適な解になる。というのは、有効制約集合の初期推定が前の時点からのものであり、ＱＰの大部分で、前の有効制約集合が最適だからである。
【０００９】
この最初のＥＱＰの解、ｘ＿ｅｑｐ1が最適ではないが実行可能な場合、これをｘf、実行可能な点の推定、として使用することができる。このｘ＿ｅｑｐ1は、初期有効制約集合と一貫性のある実行可能な点であるという利点を有するが、従来の方法で使用されるｘfは必ずしもそうではない。
【００１０】
いかなる状況下でもＱＰソルバ（ｓｏｌｖｅｒ）からの解が違反することの「できない」「重要な制約」がある。重要な制約の集合は、実行可能な解が最初から存在するようなものである必要があるのは明らかである。例えば、このような重要な制約の集合は、アクチュエータの下限（ｌｏｗｅｒ  ｌｉｍｉｔ）および上限（ｕｐｐｅｒ  ｌｉｍｉｔ）の集合であってもよく、最適化用語では「変数束縛制約（ｖａｒｉａｂｌｅ  ｂｏｕｎｄ  ｃｏｎｓｔｒａｉｎｔ）」としても知られている。いかなる重要な制約にも違反してはならないことが、初期実行可能な点ｘfの推定に課せられる必要条件である。
【００１１】
最初のＥＱＰの解、ｘ＿ｅｑｐ1が最適でもなく実行可能でもない状況で、それでもその解が重要な制約を満たしている場合、ｘ＿ｅｑｐ1をｘfとして使用し、追加変数ｔを導入することによって、違反される重要でない制約を緩和することができる。このｘfは、重要な制約に違反しないことを保証しながら、初期有効制約集合と一貫性があるという利点を有する。次の実用的な（ｗｏｒｋｉｎｇ）制約の集合は、乗数が負である制約を差し引いて、初期実用制約集合（ｗｏｒｋｉｎｇ  ｓｅｔ）になるように選択される。
【００１２】
ｘ＿ｅｑｐ1が重要な制約に違反する場合は、ｘ＿ｅｑｐ1の重要な制約の集合への射影が計算され（これをｘpと呼ぶ）、これが実行可能な解の新しい推定になる。ここで、ｖ（どの制約を緩和するべきかを示すベクトル）の成分およびｔの値は、点ｘpができるだけ多くの初期有効制約集合の制約に対して効力をもつ（ｂｉｎｄｉｎｇ）ように操作され、それによってｘpが厳密には効力をもたない有効制約集合の推定におけるもとの制約に対して、ｘpの一貫性が保持される。
【００１３】
本発明のその他の利点は、以下の詳細な説明を参照して添付の図面と併せ読むことにより理解が進むにつれ、容易に理解されよう。
【発明を実施するための最良の形態】
【００１４】
図１は、本発明から利益を得るはずのタイプの、モデル予測制御を使用する制御システム１０の一般的なモデルである。制御システム１０は、システム１０の所望の出力プロファイルを生成する所望の軌道ジェネレータ１２（ｔｒａｊｅｃｔｏｒｙ  ｇｅｎｅｒａｔｏｒ）を含む。線形化モジュール１４は、所望の軌道ジェネレータ１２からの所望の軌道に対する線形化モデルを導出する。二次計画法定式化モジュール１６が、制約をいずれも守りながら所望の軌道を最適に得るための制御プロファイルを決定するように、二次計画問題を形成する。二次計画法ソルバ１８が、定式化モジュール１６によって確立された最適化問題を解いて、最適な制御プロファイルを生成する。二次計画法ソルバ１８は、本発明の焦点である。最適な制御プロファイルは、システム１０のプラント２２に作用する作動システム２０に送られる。センサシステム２４が、プラント２２からのフィードバックを所望の軌道ジェネレータ１２に与える。
【００１５】
今回のＭＰＣのための最適化問題の定式化は、完結させる目的のみで本明細書に含まれる。説明をさらに簡単にするために、「１回時間段階を進める（ｏｎｅ−ｔｉｍｅ  ｓｔｅｐ  ａｈｅａｄ）」ＭＰＣのみ、すなわち米国特許第６，８８２，８８９号で詳細に述べられている制約付き動的逆変換問題のみを考慮した。完全なＭＰＣ問題はまた、２００３年２月１４日出願の「実時間モデル予測制御における二次計画法のための加速された有効制約集合探索のシステムおよび方法（Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｏｆ  Ａｃｃｅｌｅｒａｔｅｄ  Ａｃｔｉｖｅ  Ｓｅｔ  Ｓｅａｒｃｈ  ｆｏｒ  Ｑｕａｄｒａｔｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ  ｉｎ  Ｒｅａｌ−Ｔｉｍｅ  Ｍｏｄｅｌ  Ｐｒｅｄｉｃｔｉｖｅ  Ｃｏｎｔｒｏｌ）」（米国特許出願第１０／３６７，４５８号）に記載されている有効制約集合法を使用して定式化し、解くこともできる。次の定式化は、モデル予測制御問題の唯一可能な表現であり、二次計画問題をどのように開始するかを示すためのものであり、二次計画問題を導出する際の革新性を請求するものではない。
【００１６】
下記のように線形化された系によって記述される、状態変数ξ、制御変数ｕ、出力ｙを有する力学系を考える（これは、線形系、または非線形力学系の線形化バージョンであってもよい）：
【００１７】
【数１】
2007226772.tif 000003
【００１８】
所望の出力変化を実現するように、制御の変化を送達する方法を決定したい。この問題は、上記線形系の離散時間バージョンで最もうまく処理される。ここで、下付き文字ｔは、各離散時間点を表す：
【００１９】
【数２】
2007226772.tif 000004
【００２０】
ここでΔｕt＝ｕt−ｕt-1は、所望の出力変化Δｙt＝νの生成に必要な制御変数の変化を表す。
【００２１】
これを実現するために「最小化」できる二次目的は、以下のとおりである。
【００２２】
【数３】
2007226772.tif 000005
【００２３】
最小化は、システム方程式（２）が満たされているとして行われなければならない。ここでＶは、各出力目標に対して正の重みをもつ対角行列を表す。また、状態変数および制御変数のための同様の目標項も追加する。この問題の厳密な凸状を保つために、これらの二次目的は、小さいが常にゼロではない重みを有する。
【００２４】
システム方程式（２）によってもたらされる等式の制約を、（２）の第２式にΔξt＝Ａ1ξt-1＋Ｂ1ｕt-1を代入することによってなくし、それによって、以下を導出することができる。
【００２５】
【数４】
2007226772.tif 000006
【００２６】
以上から、出力の変化を単にΔｕtを用いて表現できることが証明される。
【００２７】
物理的制限および速度制限を含む、出力および入力に関する追加の「不等式の制約」もまた、以下の形で、すべてΔｕtを用いて表すことができる。
【００２８】
【数５】
2007226772.tif 000007
【００２９】
［二次計画問題］
目的と制約を組み合わせると、厳密に凸二次計画問題（ｑｕａｄｒａｔｉｃ  ｐｒｏｇｒａｍ（ＱＰ））に帰着する。扱いにくい表記を避けるために最適化変数Δｕtをｘに置き換えた後、ＱＰを以下のように書くことができる。
【００３０】
Ａｘ≦ｂの下で、
【００３１】
【数６】
2007226772.tif 000008
【００３２】
［最適な有効制約集合を探索するためのアルゴリズム］
有効制約集合アルゴリズムは、通常は有効制約集合と呼ばれる、最適時に効力をもつ制約の集合を反復して探索する。モデル予測制御問題では、現時間段階におけるＭＰＣ問題に対する解が、次の時間段階における最適な有効制約集合のための推定を与える。この特定の推定は、ＱＰを収束まで解くのに必要な反復数の低減に非常に有利に使用され、実時間制御においては事実上不可欠な特徴である。有効制約集合アルゴリズムの大まかなステップの概略を下記に示し、関連する線形代数を以下の段落で詳細に述べる。
【００３３】
・有効制約集合の推定から始める。有効制約集合の制約の添字集合をＷで示し、また、推定される有効制約集合に対応する制約行列Ａの行をＥとする。実行可能な点ｘfが既知、すなわちＡｘf≦ｂであると仮定する。
【００３４】
・反復ｋにおいて、有効な制約に対して推定Ｅが与えられているとして、下記の等式制約付きＱＰ（Ｅｑｕａｌｉｔｙ−Ｃｏｎｓｔｒａｉｎｅｄ  ｑｕａｄｒａｔｉｃ  ｐｒｏｇｒａｍ（ＥＱＰ））を解く。
【００３５】
【数７】
2007226772.tif 000009
【００３６】
ここで、ｒは有効な制約の右辺の部分ベクトルを表す。最適解ｘ*、およびラグランジュ（Ｌａｇｒａｎｇｅ）乗数λ*は、次式によって与えられる。
【００３７】
【数８】
2007226772.tif 000010
【００３８】
「比のテスト（ｒａｔｉｏ  ｔｅｓｔ）」によって、ｘk-1＋αｓが実行可能であるような最大のα∈［０，１］を決める。ここで、ｓ＝ｘ*−ｘk-1であり、ｘk-1は前の反復を示す。つまり、αは、Ａｘk-1＋αＡｓ≦ｂであるような［０，１］内の最大値になるように選択される。有効制約集合内にある制約添字ｉに対しては、制約添字ｉがＡｓi＝０を含み（またはＡｓi≦０（反復１回））、かつ前の反復ｘk-1が実行可能なので、このテストを実行する必要はない。（注記：有効制約集合の外では、Ａｓi＝０を有する退化（ｄｅｇｅｎｅｒａｔｅ）した制約を含むことが可能になり、このような制約全体にわたる比のテストはやはりスキップされるはずである。）したがって、αは次式で与えられる。
【００３９】
【数９】
2007226772.tif 000011
【００４０】
・次の反復で有効制約集合の推定を更新する。
【００４１】
・対応するαが比のテストで最小値を実現する最初の添字ｉBを、Ｗに追加する。ｉBは、次の反復において有効な添字の推定である。これに対応する制約は大雑把に、「最も厳しい制約」と呼ばれる。
【００４２】
・ＥＱＰ（７）のラグランジュ乗数λ*が負である制約が存在する場合は、最も小さな負の乗数を有する制約を有効制約集合から外す。これはいわゆる「最急勾配エッジ（ｓｔｅｅｐｅｓｔ  ｅｄｇｅ）」規則である。退化が有効制約集合内に検出されるときは常に、上記の例では負の乗数を有する最初の制約が外されるときは常に、ブランド（Ｂｌａｎｄ）の規則が活用される。退化の処理および検出の詳細は、本開示において後述する。
【００４３】
・特別な最初の反復の場合では、初期有効制約集合の制約を、その制約がｘfで効力をもつ場合に「一貫性がある」ように定義する。最初の反復でα＜１の場合は、「一貫性のない制約は」、その乗数の符号に関係なく「すべて外される」。これは、Ｅｘf≦ｒ（いくつかの成分に対しては厳密な不等式である）の場合、更新された反復ｘ1＝ｘf＋α（ｘ*−ｘf）が次の反復の有効制約集合のすべての制約に対してＥｘ1＝ｒを満たさず、矛盾することになるからである。以上が、一貫性のある有効制約集合法である（先行特許に記載）。例えば、ｘfが実行可能な集合の厳密な内部に存在する場合、それによってすべての制約が外され、空の有効制約集合から再開することになり、したがって「ホットスタート（ｈｏｔ  ｓｔａｒｔ）」をほとんど利用することができない可能性がある。ただし、ｘfが前時間段階でＭＰＣ問題を解くことによって得られた最適な制御の集合である場合は、通常、ｘfは有効制約集合の初期推定と一貫性を有する。
【００４４】
［一貫性のない有効制約集合法］
いくつかの場合では、既知の実行可能な点が大部分、有効制約集合の開始推定と一貫性をもたない。それによって、多くの一貫性のない制約が、最初の反復の最後で有効制約集合から外されることになる。初期のホットスタート推定が優れたものの場合は、上記の制約を引き戻す際に多くの反復が無駄になる。したがって、別の手法では、有効制約集合内に一貫性のない制約を保持し、たとえ反復と有効制約集合が合致しないとしても引き続き最適解を探索する。任意の反復でα＝１の場合、この一貫性のなさがなくなる。さらに、一貫性のなさの度合いは反復ごとに低減する。この一貫性のない方法は通常、一貫性のある方法よりも、最適解へのはるかに速い収束を可能にする。
【００４５】
反復を更新する。
【００４６】
【数１０】
2007226772.tif 000012
【００４７】
α＝１かつλ*≧０のとき、すなわち、有効制約集合が変化しない場合は、大域的最適解への収束が実現する。
【００４８】
収束に達する前に、実時間間隔内で許可された時間が尽きた場合、最後に更新された反復が解として返される。
【００４９】
本発明は、ホットスタートすると同時に可能な限り多くの一貫性を保持し、かつ反復に対して一貫性のある可能な限り多くの制約を保つために「ビッグＭ（ｂｉｇ−Ｍ）」緩和を利用するという課題を扱う。
【００５０】
反復中の一貫性の保持を支持する有力な論拠がある。というのは、そうでなければ、ある反復から別の反復まで目的関数が増加する可能性があり、制約が有効であると示されたときでさえ、右辺を厳密に満たさないことがあるからである。
【００５１】
さらに、一貫性のない状態で開始すると、最初のＥＱＰの解が制約のいずれかに違反する場合、現在の点はＥＱＰ解とｘf（実行可能な解の初期推定）の凸結合になる。現在の反復ｘと有効制約集合の間の一貫性が保持されているとしたら、ｘfが厳密に満たさない最初の有効制約集合における制約はいずれも外されているはずである。この結果、潜在的に期待できる制約が有効制約集合から外され、したがって良好な「有効制約集合ホットスタート」の利益が失われる。
【００５２】
本発明は、こういった不備を修正する。この革新的な手法について、下記に説明する。
【００５３】
まず、先行特許の一部分として説明した、実行不可能な開始の処理に必要な「ビッグＫ／Ｍ」緩和について説明する。初期推定ｘfが実行可能ではない場合、追加変数ｔを導入することによって問題が緩和される。
【００５４】
ｘ、ｔがＡｘ−ｖｔ＜＝ｂ、ｔ＞＝０（Ｍ＝０の場合不要）の条件の下、０．５ｘTＨｘ＋ｃTｘ＋０．５Ｋｔ2＋Ｍｔを最小にする。
【００５５】
このアルゴリズムは、たとえｘfが実行不可能であるとしても、まさにその開始時に問題を緩和しない。その代わりに、有効制約集合の初期推定を使用して、問題を緩和せずにＥＱＰを解く。この解をｘ＿ｅｑｐ1と呼ぶ。「非常に多くの場合、これが最適な解になる」。というのは、有効制約集合の初期推定が前の時点からのものであり、ＱＰの大部分で、前の有効制約集合が最適だからである。現在実施されている方法は、ｘfが実行不可能な場合、こういった有効な制約の一部を緩和することになり、したがって、有効制約集合の初期推定が実際に最適であるにもかかわらず、真の最適に達しない可能性がある。
【００５６】
この最初のＥＱＰの解、ｘ＿ｅｑｐ1が最適ではないが実行可能な場合、これをｘf、実行可能な点の推定、として使用することができる。このｘ＿ｅｑｐ1は、初期有効制約集合と一貫性のある実行可能な点であるという利点を有するが、従来の方法で使用されるｘfは、必ずしもそうではない。
【００５７】
一貫性を維持しながら、重要な制約を守る：
さらに詳細に述べるために、「重要な制約」という観念を導入する。これはいかなる状況下でもＱＰソルバからの解が違反することの「できない」制約である。重要な制約の集合は、最初から実行可能な解が存在するようなものである必要があるのは明らかである。例えば、このような重要な制約の集合は、アクチュエータの下限および上限の集合であってもよく、最適化用語では「変数束縛制約」としても知られている（いかなる重要な制約にも違反してはならないことが、初期実行可能な点ｘfの推定に課せられる必要条件である。）。
【００５８】
次に、最初のＥＱＰの解、ｘ＿ｅｑｐ1が最適でもなく実行可能でもない場合を考える。その解がまだ重要な制約を満たしている場合、ｘ＿ｅｑｐ1をｘfとして使用し、追加変数ｔを導入することによって、違反される重要でない制約を緩和することができる。このｘfは、重要な制約に違反しないことを保証しながら、初期有効制約集合と一貫性があるという利点を有する。次の実用的な制約の集合は、乗数が負である制約を差し引いて、初期実用制約集合になるように選択される。
【００５９】
ｘ＿ｅｑｐ1が重要な制約に違反する場合は、「ｘ＿ｅｑｐ1の重要な制約の集合への射影」が計算され（これをｘpと呼ぶ）、これが実行可能な解の新しい推定になる。ここで、ｖ（どの制約を緩和するべきかを示すベクトル）の成分およびｔの値は、点ｘpができるだけ多くの初期有効制約集合の制約に対して効力をもつように操作され、「それによってｘpが厳密には効力をもたない有効制約集合の推定におけるもとの制約に対して、ｘpの一貫性が保持される」。
【００６０】
最後のステップの論理を以下のように説明することができる。実施においては、必須ではないが、初期反復でｔ＝ｔf＝１であると仮定する。
【００６１】
・ｘpが初期有効制約集合内にある制約ａi*ｘp＜＝ｂiに違反する場合、ａi*ｘp−ｖi*ｔf＝ｂiであるようにｖi＞０を選択することによってその制約が緩和される。
【００６２】
ｘpが初期有効制約集合内に「ない」制約ａi*ｘp＜＝ｂiに違反する場合、ａi*ｘp−ｖi*ｔf＜ｂiであるようにｖi＞０を選択することによってその制約が緩和される。
【００６３】
ｘpが制約に違反しない場合、その制約は緩和されない。制約がたまたま初期有効制約集合内にあり、まだ効力をもっている場合は有効制約集合内に保持され、そうでない場合は外される。
【００６４】
上記の手順後のワーキングセット内の制約の数が、許容最大数よりも大きい場合、最小の実行不可能な制約が有効制約集合から外される。
【００６５】
特許法の条項および法律学によれば、上述の構成の例は、本発明の好ましい実施形態とみなされる。ただし、本発明を、その趣旨または範囲を逸脱することなく、具体的に例示し説明したものとは異なる方法で実施できることに留意されたい。
【図面の簡単な説明】
【００６６】
【図１】本発明の二次計画法を使用するタイプの制御システムを示す図である。
【図１】
2007226772.tif 000013
【外国語明細書】
2007226772000001.pdf