JP4329933B2 - ２次計画法求解装置 - Google Patents

Description

本発明は、最適な計画を立案する場合、あるいは、最適な制御を行う場合に解く必要が生じる２次計画問題（評価関数が２次式で与えられ、制約式が１次式で与えられる最適化問題）を解くための２次計画法求解装置に関するものである。

等式制約を持つ２次計画問題は、下記のように表現される。
［等式制約付２次計画問題］
Min ｆ(ｘ)
Subject to:
Ｈｘ＝ｂ ただし、ｆ(ｘ)＝ｐ^ｔｘ＋０．５ｘ^ｔＱｘ
Ｑ：対称行列

この問題に対する従来の解法において、最適解に近づくための変数の修正量ｄは、下式（１）の修正方程式を解くことにより与えられる（例えば、非特許文献１参照）。なお、最適化に関する一般的な表現と合わせるため、非特許文献１とは、μ^＊の符号を逆に定義している。

ところで、一般の２次計画問題は、下記のように、不等式制約を含んでいる。
［一般の２次計画問題］
Min ｆ(ｘ)
Subject to:
Ｈ_１ｘ＝ｂ_１
ｂ_２min≦Ｈ_２ｘ≦ｂ_２max
ｘ_min≦ｘ≦ｘ_max

上記の一般の２次計画問題は、スラック変数ｓを導入することにより、等式制約、及び変数に対する上下限制約のみを持つ下記の形に変換できる。
Min ｆ(ｘ)
Subject to:
Ｈ_１ｘ＝ｂ_１
Ｈ_２ｘ−ｓ＝０
ｘ_min≦ｘ≦ｘ_max
ｂ_２min≦ｓ≦ｂ_２max

以上より、本来の変数ｘと導入したスラック変数ｓとを合わせ改めて全体をｘと表現し、本来の等式制約と、スラック変数の導入によって不等式制約から作られた等式制約とを合わせ、改めて全体をＨｘ＝ｂと表現することにより、一般の２次計画問題は、下記の形に変換される。
Min ｆ(ｘ)
Subject to:
Ｈｘ＝ｂ
ｘ_min≦ｘ≦ｘ_max

上記の変換された形の２次計画問題に対して、先述の［等式制約付２次計画問題］の解法を適用するためには、変数ｘの中で、最適解において上下限制約の境界上にあると仮定される変数ｘ_kに対する不等式制約を、ｘ_ｋ＝ｆ_ｋという等式制約に変換し、その他の上下限制約は無いものとする必要がある。

この変換により、最適解に近づくための変数の修正量ｄを与える修正方程式は、下式（２）となり、この方程式を解くことにより、最適解に近づくための変数の修正量ｄから修正方向が求まる。下式（２）において、修正量ｄは、大きさとともに方向を有するデータである。また、太字で表された「１」は、ｋ番目の変数ｘ_kに対する不等式制約を、ｘ_ｋ＝ｆ_ｋという等式制約に変換することにより、ｋ番目の要素だけが１となっている行列を示している。

「最適化ハンドブック」(朝倉書店)１７４ページ(２.７)式

しかしながら、従来技術には次のような課題がある。従来の２次計画問題の解法においては、上述の通り、「変数の次元＋等式制約の数＋上下限制約の境界上にあると仮定する変数の数」で定まる次元の修正方程式を解き、さらに、最適解に近づくための変数の修正量ｄから修正方向を求める必要があり、処理時間が長くなる問題があった。

本発明は上述のような課題を解決するためになされたもので、高速に２次計画問題を解く２次計画法求解装置を得ることを目的とする。

本発明に係る２次計画法求解装置は、関数型不等式制約を含む２次計画問題の方程式を設定する入力手段と、関数型不等式制約を関数型等式制約に変換して生成される修正方程式を記憶する修正方程式記憶ファイル、変数の値の履歴を記憶する変数履歴データ記憶ファイル、及び変数の上下限制約の値を記憶する上下限制約値記憶ファイルを有する記憶部と、関数型不等式制約を含む２次計画問題の方程式に対してスラック変数を導入して、関数型等式制約を含む２次計画問題の方程式及び新たな変数の上下限制約に変換し、上下限制約の値を上下限制約値記憶ファイルに記憶させる変換手段と、上下限制約を有する新たな変数について、上下限制約内の初期値を設定するとともに、２次計画問題の最適解において上下限制約の境界上にあると仮定する変数を特定し、特定した変数の等式制約及び上下限制約に対するラグランジュ乗数を用いて修正方程式を生成し、設定した初期値を変数履歴データ記憶ファイルに記憶させ、生成した修正方程式を修正方程式記憶ファイルに記憶させる修正方程式生成手段と、変数履歴データ記憶ファイルの最新データに基づいて修正方程式記憶ファイルに記憶された修正方程式を解くことにより、最適解に近づくための変数の修正量を算出する修正量算出手段と、修正量算出手段によって算出された修正量及び上下限制約値記憶ファイルに記憶された上下限制約の値に基づいて、上下限制約の範囲内に収まる修正後の新たな変数を求めて記憶部の変数履歴データ記憶ファイルを更新する変数変更手段と、変数履歴データ記憶ファイルに記憶された変数の履歴データ及びあらかじめ決められた収束判定値に基づいて変数の収束状態を判定し、変数が収束していないと判定したときは、修正量算出手段に対して、更新された変数履歴データ記憶ファイルの最新のデータに基づいて修正方程式記憶ファイルに記憶された修正方程式を解くことを再び実行させ、変数が収束したと判定したときは、処理を終了すると判定する繰返し処理判定手段と、繰返し処理判定手段により処理が終了したと判定された場合に、記憶部の変数履歴データ記憶ファイルから最新の変数を最適解として取り出して出力する最適解出力手段とを備え、記憶部は、修正方程式よりも次元の小さい縮小修正方程式を記憶する縮小修正方程式記憶ファイルをさらに有し、修正方程式記憶ファイルに記憶された修正方程式から、上下限制約の境界上にあると仮定された変数、及び上下限制約に対するラグランジュ乗数を消去した次元の小さい縮小修正方程式を生成し、生成した縮小修正方程式を記憶部の縮小修正方程式記憶ファイルに記憶させる縮小修正方程式生成手段をさらに備え、修正量算出手段は、記憶部の変数履歴データ記憶ファイルの最新のデータに基づいて縮小修正方程式記憶ファイルに記憶された縮小修正方程式を解くことにより、最適解に近づくための変数の修正量を算出し、繰返し処理判定手段は、変数履歴データ記憶ファイルに記憶された変数の履歴データ及びあらかじめ決められた収束判定値に基づいて変数の収束状態を判定し、変数が収束していないと判定したときは、縮小修正方程式生成手段に対して、更新された変数履歴データ記憶ファイルの最新のデータ及び修正方程式記憶ファイルに記憶された修正方程式に基づいて縮小修正方程式を再び生成させるものである。

本発明によれば、本来の修正方程式より次元の小さい縮小修正方程式を生成し、生成した縮小修正方程式を解くことにより最適解に近づくための変数の修正量を得ることが可能となり、２次計画問題を高速に解く２次計画法求解装置を得ることができる。

以下、本発明の２次計画法求解装置の好適な実施の形態について、図面を用いて説明する。本発明の２次計画法求解装置は、変数の修正を繰返すことにより２次計画問題の最適解を求める際に、縮小修正方程式を導入することにより演算処理に要する時間を短縮して高速化を図ることを特徴とする。

実施の形態１．
図１は、本発明の実施の形態１における２次計画法求解装置の構成図である。２次計画法求解装置１０は、入力手段１１、変換手段１２、修正方程式生成手段１３、記憶部１４、縮小修正方程式生成手段１５、修正量算出手段１６、変数変更手段１７、繰返し処理判定手段１８、及び最適解出力手段１９で構成される。

入力手段１１は、関数型不等式制約を含む２次計画問題の方程式を２次計画法求解装置１０に読み込むための入力手段である。変換手段１２は、関数型不等式制約にスラック変数を導入することにより、入力手段で設定された２次計画問題の方程式を、関数型等式制約及び新たな変数の上下限制約に変換するための変換手段である。ここで、新たな変数とは、本来の変数とスラック変数とを合わせた変数である。

修正方程式生成手段１３は、上下限制約を有する新たな変数について、最適解において上下限制約の境界上にあると仮定する変数を設定するとともに、２次計画問題の最適解に近づくための変数の修正量を求めるための修正方程式を生成する生成手段である。

記憶部１４は、修正方程式を記憶する修正方程式記憶ファイル、縮小修正方程式を記憶する縮小修正方程式記憶ファイル、変数の値を記憶する変数履歴データ記憶ファイル、及び上下限制約の値を記憶する上下限制約値記憶ファイルを有する記憶部である。

縮小修正方程式生成手段１５は、修正方程式生成手段１３で生成された修正方程式に基づいて、最適解において上下限制約の境界上にあると仮定された変数ならびに該変数に対応するラグランジュ乗数を消去することにより、次元の小さい縮小修正方程式を生成する生成手段である。修正量算出手段１６は、縮小修正方程式を解くことにより、最適解に近づくための変数の修正量を求める算出手段である。

変数変更手段１７は、修正量算出手段１６によって算出された修正量及び上下限制約値記憶ファイルに記憶された上下限制約の値に基づいて、変数の修正及び２次計画問題の最適解において上下限制約の境界上にあると仮定する新たな変数の特定を行い、記憶部１４の変数履歴データ記憶ファイルを更新する手段である。

繰返し処理判定手段１８は、変数履歴データ記憶ファイルに記憶された変数の履歴データに基づいて変数の収束状態を判定し、最適解を算出するための繰返し処理を実行すべきか否かを判定する判定手段である。繰返し処理が必要な場合には、繰返し処理判定手段１８は、縮小修正方程式生成手段１５に対して、更新された変数履歴データ記憶ファイルの最新のデータ及び修正方程式記憶ファイルに記憶された修正方程式に基づいて縮小修正方程式を再び生成させることとなる。

さらに、最適解出力手段１９は、繰返し処理判定手段１８により繰返し処理が必要でないと判定された場合に、記憶部１４の変数履歴データ記憶ファイルから更新された最新の変数を最適解として取り出して出力する手段である。このようにして、繰返し処理判定手段１８により繰返し処理が必要でないと判定されるまで一連の処理を繰り返すことにより、最適解を算出する。

次に、上述した縮小修正方程式に基づく最適解の算出処理について、フローチャートを用いて詳細に説明する。図２は、本発明の実施の形態１の２次計画法求解装置１０における求解処理のフローチャートである。まず始めに、２次計画法求解装置１０の入力手段１１は、最適解を求めるべき問題として、関数型不等式制約を含む２次計画問題の方程式を読み込む（ステップＳ２０１）。

変換手段１２は、読み込んだ２次計画問題の方程式に含まれている関数型不等式制約に対してスラック変数を導入することにより、関数型不等式制約を関数型等式制約に変換するとともに、本来の変数とスラック変数とを合わせた新たな変数に関する上下限制約を設定し、その上下限制約の値を記憶部１４内の上下限制約値記憶ファイルに記憶させる（ステップＳ２０２）。

続いて、修正方程式生成手段１３は、［一般の２次計画問題］において、最適解に近づくための変数の修正量ｄを得るための修正方程式として先に示した式（２）の左上の部分行列Ｊ（Ｑ、Ｈ、Ｈ^ｔから成る行列）を生成する（ステップＳ２０３）。

さらに、修正方程式生成手段１３は、変数の上下限制約を逸脱しない形で変数ｘを初期設定する。この変数の設定において、上下限制約の上限値または下限値に等しい値を設定することにより、「最適解において上下限制約の境界上にあると仮定する変数」として特定することができる（ステップＳ２０４）。なお、対象問題に近い２次計画問題の最適解が既知である等、適切に「最適解において上下限制約の境界上にあると仮定する変数」を設定することが可能な場合を除いては、変数の初期値としては、変数の上下限制約の中間値を設定する。このようにステップＳ２０３、２０４の処理により、修正方程式生成手段１３は、式（２）で示した修正方程式の左上の部分行列を生成し、生成した部分行列を修正方程式記憶ファイルに記憶させる。

次に、縮小修正方程式生成手段１５は、式（２）の修正方程式の右辺、すなわち評価関数のグラディエントｇ及び関数型等式制約の誤差ｃを計算する（ステップＳ２０５）。続いて、縮小修正方程式生成手段１５は、算出された部分行列Ｊ、グラディエントｇ及び関数型等式制約の誤差ｃを用いて、縮小修正方程式を生成し、その縮小修正方程式を記憶部１４内の縮小修正方程式記憶ファイルに記憶させる（ステップＳ２０６）。

ここで、縮小修正方程式の生成及びラグランジュ乗数λ^＊の算出について詳細に説明する。本来の修正方程式は、先に示した式（２）である。この修正方程式の未知数である修正量ｄの中で、変数上下限制約の境界上にあると仮定されている変数ｘ_kに対応する要素は０である（すなわち、修正量が０である）ことが自明であることから消去する。さらに、このｘ_kの上下限制約に対するラグランジュ乗数λ^＊を後から求めることとし、λ^＊に影響される行も消去する。これらの消去により、式（２）の修正方程式は、下記の縮小修正方程式（３）となる。

この縮小修正方程式（３）の左辺の行列は、変数の上下限制約の境界上にあると仮定されている変数に対応する列ｋの要素（破線で示す）、ならびに、λ^＊に影響されるため消去したい行ｋの要素（破線で示す）を０としている。ただし、対角項は、非０要素があるとみなす。また、縮小修正方程式（３）の右辺のｋ番目の要素（破線で示す）も０とする。このように０を割り付けた縮小修正方程式（３）は、行と列を消去した場合と同じ解を得る縮小修正方程式となっている。なお、消去対象とする列・行のペアは複数あってもよい。

式（３）を解くことにより、ｄ及びμ^＊が求まる。さらに、式（２）より、右辺のｇに関して下式（４）の関係が得られる。

したがって、λ^＊は、次式（５）から求めることができる。

上述の処理により、縮小修正方程式の生成及びラグランジュ乗数λ^＊の算出を行うことができる。そこで、ステップＳ２０７以降の説明に戻る。修正量算出手段１６は、縮小修正方程式（３）を解くに先立ち、縮小修正方程式左辺の行列を三角分解する（ステップＳ２０７）。続いて、修正量算出手段１６は、縮小修正方程式（３）を解き、変数の修正量ｄ及び関数型等式制約に対するラグランジュ乗数μ^＊を得る（ステップＳ２０８）。

続いて、変数変更手段１７は、全ての変数ｘに対してｄの修正を行った場合に、変数が上下限制約を超えて逸脱が発生するか否かを判定する（ステップＳ２０９）。逸脱が発生しないと判定した場合には、変数変更手段１７は、上述の方法で変数上下限制約に対するラグランジュ乗数λ^＊を求める（ステップＳ２１０）。さらに、変数変更手段１７は、全ての変数ｘに対し算出された修正量ｄの修正を行う（ステップＳ２１１）。

続いて、変数変更手段１７は、ステップＳ２１０で算出されたラグランジュ乗数λ^＊の結果を用いて、上下限制約の境界上にある変数の中で制約を外す（すなわち、上限値あるいは下限値が設定されている変数の値を、あらかじめ決められた値で修正することにより上限値あるいは下限値でない上下限制約内の値に変更する）ことにより評価関数値が改善する変数があるかないかを調べる（ステップＳ２１２）。そのような変数がある場合には、変数変更手段１７は、そのような変数を「最適解において上下限制約の境界上にあると仮定する変数」から削除し（ステップＳ２１３）、変数履歴データ記憶ファイルのデータを更新にする。

ステップＳ２１３において、変数変更手段１７によって変数履歴データ記憶ファイルのデータが更新された場合には、繰返し処理判定手段１８は、修正量の算出を繰返し行うことが必要であると判断し、縮小修正方程式生成手段１５に対して、更新された変数履歴データ記憶ファイルの最新のデータ及び修正方程式記憶ファイルに記憶された修正方程式に基づいて縮小修正方程式を再び生成させる。その結果、ステップＳ２０５以降の処理を繰返し、最適解の算出を継続することとなる。

一方、ステップＳ２１２において、変数変更手段１７によって上下限制約の境界上にある変数の中で制約を外すことにより評価関数値が改善する変数が無いと判定された場合には、繰返し処理判定手段１８は、最適解が求まったと判断する。その後、最適解出力手段１９は、更新された変数履歴データ記憶ファイルから最新の変数値を最適解として取り出し、処理を終了する（ステップＳ２１４）。

なお、繰返し処理判定手段１８は、ステップＳ２１２において、変数変更手段１７によって上下限制約の境界上にある変数の中で制約を外すことにより評価関数値が改善する変数が無いと判定された後に、あらかじめ決められた収束判定値及び変数履歴データ記憶ファイルに記憶された変数の履歴データに基づいて収束判定を行い、変数が収束していない場合には再びステップＳ２０５以降の処理を繰り返すような処理を付加することも可能である。

上下限制約の境界上にある変数の中で、制約を外すことにより評価関数値が改善する変数があるかないかを調べるには、次のようにして行うことができる。

上限制約の境界上にある変数（すなわち上限値が設定されている変数）に対応するラグランジュ乗数λ^＊の要素が負の値を持つ場合、あるいは、下限制約の境界上にある変数（すなわち下限値が設定されている変数）に対応するラグランジュ乗数λ^＊の要素が正の値を持つ場合には、これらの変数の制約を外すことにより、評価関数値を改善することが可能となる。したがって、これらの変数を「最適解において上下限制約の境界上にあると仮定する変数」から外す対象と判定することとなる。変数の制約を外すためには、あらかじめ決められた量を修正することにより、上限値あるいは下限値でない上下限制約内の値とすることができる。

一方、先のステップＳ２０９において、全ての変数ｘに対してｄの修正を行った場合に、変数が上下限制約を超えて逸脱が発生すると判定した場合には、変数変更手段１７は、新たに上下限制約の境界上にある変数が現れるまで、変数ｘのｄ方向への修正を行い、新たに上下限制約の境界上の値となった変数を「最適解において上下限制約の境界上にあると仮定する変数」に追加する（ステップＳ２１５）。

このステップＳ２１５における変数の修正は、具体的には次のように行う。算出された修正量ｄは、変数の要素分のデータを備えたベクトルと見ることができる。このベクトルに対して１未満の係数を掛け合わせることにより新たな修正補正量を求めた場合に、その修正補正量により補正した変数が、どれも上下限制約の範囲内になるようにする最大の係数を求めることにより、修正後の全ての変数が上下限制約以内となり、かつ、少なくとも１つの変数が上下限制約の境界上にある状態を創り出すことができる。

続いて、変数変更手段１７は、「最適解において上下限制約の境界上にあると仮定する変数」の中で、上下限制約の境界上にあるという仮定を外す、すなわち上限値あるいは下限値の制約から離れるよう変数を動かすことにより、関数型等式制約の誤差（各関数型等式制約式の誤差の絶対値の総和）が減少する変数があるかないかを調べる（ステップＳ２１６）。

該当する変数が無い場合には、変数変更手段１７は、可能解（制約を満たす解）は無いと判断して変数履歴データ記憶ファイルのデータの更新を行わず、繰返し処理判定手段１８は、繰返し処理を行わないと判断し、処理を終了する（ステップＳ２１７）。この場合には、最適解出力手段１９は、可能解がないことを出力することとなる。

一方、該当する変数がある場合には、変数変更手段１７は、そのような変数を「最適解において上下限制約の境界上にあると仮定する変数」から削除し（ステップＳ２１８）、変数履歴データ記憶ファイルのデータを更新にする。

そして、繰返し処理判定手段１８は、修正量の算出を繰返し行うことが必要であると判定し、縮小修正方程式生成手段１５に対して、更新された変数履歴データ記憶ファイルの最新のデータ及び修正方程式記憶ファイルに記憶された修正方程式に基づいて縮小修正方程式を再び生成させる。その結果、ステップＳ２０５以降の処理を繰返し、最適解の算出を継続することとなる。

実施の形態１によれば、修正方程式及び変数の値に基づいて次元の小さい縮小修正方程式を生成し、生成された縮小修正方程式をもとに最適解に近づくための変数の修正量を求めて変数を修正することを繰返すことにより、演算量の少ない高速処理で２次計画問題の最適解を求めることが可能となる。

実施の形態２．
実施の形態２では、関数型等式制約の誤差の計算結果に基づいて、上下限制約の境界上にあると仮定する変数を特定し、より次元の小さな縮小修正方程式を求める方法について説明する。図３は、本発明の実施の形態２における２次計画法求解装置の構成図である。この実施の形態２における２次計画法求解装置は、図１で示した実施の形態１における２次計画法求解装置と比較すると、記憶部１４内に関数型等式制約記憶ファイルをさらに有している。

図４は、本発明の実施の形態２の２次計画法求解装置における求解処理のフローチャートである。実施の形態２は、図２で示した実施の形態１のステップＳ２１６〜Ｓ２１８の処理を、新たな処理に置き換えたものであり、その置き換えた処理のフローチャートのみが図４に示されている。

なお、本実施の形態２において、変換手段１２は、２次計画問題を関数型等式制約に変換した際に、その関数型等式制約を関数型等式制約記憶ファイルにあらかじめ記憶させておくものとする。この処理は、図４には記載されておらず、実施の形態１の図２のフローチャートにおけるステップＳ２０２でこの処理が行われることとなる。

変数変更手段１７は、先に説明した図２のステップＳ２１５の処理において定められた新たに上下限制約の境界上にあると仮定された変数に対して、その変数に対応するｄの要素を０とする（ステップＳ４０１）。続いて、変数変更手段１７は、ステップＳ４０１で設定された変数を用いて、関数型等式制約記憶ファイルから取り出した関数型等式制約の誤差ｅを求める（ステップＳ４０２）。ここで、誤差ｅは、各関数型等式制約式の誤差の絶対値の総和である。

続いて、変数変更手段１７は、新たに上下限制約の境界上にあると仮定する変数が現れるまで、変数ｘのｄ方向への修正を行ったと仮定した場合の仮定修正後の新たな変数を用いて関数型等式制約の誤差ｅ’を求める（ステップＳ４０３）。なお、この仮定修正後の新たな変数の算出は、実施の形態１のステップＳ２１５で説明した処理と同様にして行うことができる。

さらに、変数変更手段１７は、ステップＳ４０２で求めた誤差ｅとステップＳ４０３で求めた誤差ｅ’について、ｅ’＜ｅの判定を行う（ステップＳ４０４）。ｅ’＜ｅの関係が成立すると判定した場合には、変数変更手段１７は、上述のステップＳ４０３で求めた仮定修正後の新たな変数を実際に採用し、「最適解において上下限制約の境界上にあると仮定する変数」を追加する（ステップＳ４０５）。そして、変数変更手段１７は、さらなる変数ｘの修正を試みるため、ステップＳ４０１に戻り、それ以降の処理を再び行う。

一方、ステップＳ４０４において、ｅ’＜ｅの関係が成立しないと判定した場合には、変数変更手段１７は、上述のステップＳ４０３で求めた仮定修正後の新たな変数を採用せずに処理を終了する。そして、繰返し処理判定手段１８は、修正量の算出を繰返し行うことが必要であると判断し、縮小修正方程式生成手段１５に対して、更新された変数履歴データ記憶ファイルの最新のデータ及び修正方程式記憶ファイルに記憶された修正方程式に基づいて縮小修正方程式を再び生成させる。その結果、ステップＳ２０５以降の処理を繰返し、最適解の算出を継続することとなる。

実施の形態２によれば、上下限制約の境界上にあると仮定する変数を関数型等式制約の誤差の計算結果に基づいて複数設定することができ、より次元の小さな縮小修正方程式に基づく最適解の算出が可能となる。さらに、処理時間のかかる修正量ｄを求める処理１回あたりの変数ｘの修正量を大きくとることが可能となり、２次計画問題を解く全体の処理時間を短縮することが可能となる。

実施の形態３．
実施の形態３では、縮小修正方程式の解法に当たって、大きな処理時間を要する三角分解の処理を毎回行わないことにより、処理時間の短縮を実現する２次計画法求解装置について説明する。図５は、本発明の実施の形態３における２次計画法求解装置の構成図である。この実施の形態３における２次計画法求解装置は、図１で示した実施の形態１における２次計画法求解装置と比較すると、記憶部１４内に三角分解履歴データ記憶ファイルをさらに有している。

図６は、本発明の実施の形態３の２次計画法求解装置における求解処理のフローチャートである。実施の形態３は、図２で示した実施の形態１のステップＳ２０７、Ｓ２０８の処理を、新たな処理に置き換えたものであり、その置き換えた処理のフローチャートのみが図６に示されている。

先に説明したように、図２のステップＳ２０６において縮小修正方程式生成手段１５により縮小修正方程式が生成された後に、修正量算出手段１６は、縮小修正方程式左辺の三角分解が過去に行われたか否かの判定を行う（ステップＳ６０１）。ここで、三角分解履歴データは、後述するステップＳ６０５において、三角分解を行う毎に、修正量算出手段１６によって記憶部１４の三角分解履歴データ記憶ファイルに記憶される。

この三角分解履歴データは、三角分解の元となった縮小修正方程式、その縮小修正方程式に対する三角分解結果及び縮小修正方程式の解法に当たって上下限制約の境界上にあると仮定した変数に関するデータを備えている。修正量算出手段１６は、この三角分解履歴データに基づいて、過去の三角分解の情報を判断することができる。

ステップＳ６０１において、三角分解履歴データに基づいて三角分解が過去に行われていたと判断した場合には、修正量算出手段１６は、さらに、縮小修正方程式記憶ファイルに記憶された縮小修正方程式と、三角分解履歴データ内の前回の縮小修正方程式を比較することにより、縮小修正方程式記憶ファイルに記憶された縮小修正方程式左辺の三角分解が過去に行われたか否かの判定を行う（ステップＳ６０２）。

そして、ステップＳ６０２において、今回解くべき縮小修正方程式（すなわち、縮小修正方程式記憶ファイルに記憶された縮小修正方程式）の三角分解がすでに前回の処理で行われていたと判断した場合には、修正量算出手段１６は、今回の縮小修正方程式の解法に当たって上下限制約の境界上にあると仮定した変数と、三角分解履歴データ記憶ファイルに記憶された前回の三角分解履歴データにおける上下限制約の境界上にあると仮定した変数とを比較する。そして、修正量算出手段１６は、上下限制約の境界上にあると仮定した変数の違いが１つのみであるか否かの判定を行う（ステップＳ６０３）。

そして、ステップＳ６０３において、履歴データに基づいて変数の違いが１要素のみであると判断した場合には、修正量算出手段１６は、三角分解をあらためて行うことなしに、前回の三角分解結果を流用して縮小修正方程式を解き、変数の修正量ｄ，関数型等式制約に対するラグランジュ乗数μ^＊を求め、その後、図２のステップＳ２０９に移行する（ステップＳ６０４）。この具体的な解法については、後述する。

一方、ステップＳ６０１において過去に三角分解が行われていないと判断した場合、ステップＳ６０２において三角分解が行われていないと判断した場合、あるいはステップＳ６０３において変数の違いが１要素のみでないと判断した場合には、修正量算出手段１６は、今回の縮小修正方程式の左辺に対する三角分解を行う（ステップＳ６０５）。

そして、このステップＳ６０５において、修正量算出手段１６は、三角分解を行う毎に、三角分解履歴データを記憶部１４の三角分解履歴データ記憶ファイルに記憶させる。

さらに、修正量算出手段１６は、三角分解結果を用いて縮小修正方程式を解き、変数の修正量ｄ，関数型等式制約に対するラグランジュ乗数μ^＊を求め（ステップＳ６０６）、その後、図２のステップＳ２０９に移行し、その後の処理を継続して行う。

このように今回の縮小修正方程式の三角分解を必要とせず、前回の縮小修正方程式の三角分解の結果を流用できると判断した場合には、あらためて三角分解を行わずに今回の縮小修正方程式を解くため、大きな処理時間を必要とする三角分解の回数が減り、２次計画問題を解く全体の時間を短縮することが可能となる。

ここで、上述のステップＳ６０４における三角分解を用いない解法について、次に説明する。前回の縮小修正方程式の作成時点と今回の縮小修正方程式の作成時点において、上下限制約の境界上にあると仮定する変数の違いが１要素のみの場合には、修正量算出手段１６は、以下の処理により、三角分解を行うことなく縮小修正方程式を解くことができる。

上下限制約の境界上にあると仮定する変数の違いが１要素のみの場合には、縮小修正方程式左辺の行列は、１行・１列のみ変化することとなる。このため、行列の１行が変化した場合の逆行列の変化を表す公式、及び行列の１列が変化した場合の逆行列の変化を表す公式を用いることにより、新たな三角分解を行うことなく、縮小修正方程式を解くことが可能となる。

行列の１列が変化した場合の逆行列の変化を示す公式は、次式（６）のように表される。
Ｚ_Ｃ ^−１＝Ｚ^−１−αＺ^−１ｕ_ｋｒ_ｋ ^ｔ （６）
ただし、Ｚ_Ｃ ^−１：行列Ｚの列ｋが変化した後の逆行列
Ｚ^−１ ：行列Ｚの逆行列
ｕ_ｋ：行列Ｚに対する列ｋの変化量を表すベクトル
ｒ_ｋ ^ｔ：Ｚ^−１のｋ行目
α：１／（１＋ｒ_ｋ ^ｔｕ_ｋ）

上述のｒ_ｋ ^ｔは、縮小修正方程式のように行列の形が対称行列の場合には、次の方程式（７）を解くことにより求めることができる。
Ｚｒ_ｋ＝ｅ_ｋ （７）
ただし、ｅ_ｋはｋ番目の要素が１であり、その他の要素はすべて０であるベクトルである。

同様に、行列の１行が変化した場合の逆行列の変化を示す公式は、次式（８）のように表される。
Ｚ_Ｒ ^−１＝Ｚ^−１−βｓ_ｋｖ_ｋ ^ｔＺ^−１ （８）
ただし、Ｚ_Ｒ ^−１：行列Ｚの行ｋが変化した後の逆行列
Ｚ^−１：行列Ｚの逆行列
ｖ_ｋ ^ｔ：行列Ｚに対する行ｋの変化量を表すベクトル
ｓ_ｋ：Ｚ^−１のｋ列目
α：１／（１＋ｖ_ｋ ^ｔｓ_ｋ）

上述のｓ_ｋは、縮小修正方程式のように行列の形が対称行列の場合には、次の方程式（９）を解くことにより求めることができる。
Ｚｓ_ｋ＝ｅ_ｋ （９）
ただし、ｅ_ｋはｋ番目の要素が１であり、その他の要素はすべて０であるベクトルである。

以上の式（６）〜（９）の関係から、１行・１列を変更した場合の逆行列は、次式（１０）のようになる。

ただし、Ｚ_ＣＲ ^−１：行列Ｚの列ｋ・行ｋが変化した後の逆行列
ｓ_ｋ：［Ｚ^−１−αＺ^−１ｕ_ｋｒ_ｋ ^ｔ］のｋ列目
ｕ_ｋ：行列Ｚに対する列ｋの変化量を表すベクトル
ｒ_ｋ ^ｔ：Ｚ^−１のｋ行目
α：１／（１＋ｒ_ｋ ^ｔｕ_ｋ）

上述のｓ_ｋは、次の方程式（１１）を解くことにより求めることができる。
Ｚｓ_ｋ＝ｅ_ｋ−αｕ_ｋｒ_ｋ ^ｔｅ_ｋ （１１）

このように、Ｚ_ＣＲ ^−１は、Ｚ^−１で表現することができる。したがって、Ｚ_ＣＲに関する一次方程式は、Ｚに関する一次方程式を解くことにより、次の手順で解くことが可能となる。

解くべき方程式を次式（１２）とする。
Ｚ_ＣＲｙ＝ｗ （１２）
これをｙについて解くと、次式（１３）となる。

ここで、ｙ’を次式（１４）とする。

この場合、ｙ’は、Ｚに関する次の方程式（１５）の解として得られる。

この結果、ｙは、下式（１６）により計算される。

実施の形態３によれば、修正量算出手段は、三角分解履歴データに基づいて縮小修正方程式の解法に当たって三角分解を必要としない場合を判断し、前回の三角分解結果を流用して三角分解を行わずに縮小修正方程式を解くことができる。これにより、繰返し計算により最適解を求める際に、大きな処理時間を必要とする三角分解の回数を減らすことができ、２次計画問題を解く全体の時間を短縮することが可能となる。

実施の形態４．
実施の形態４では、本発明の２次計画法求解装置を適用する具体的な対象として、複数の発電機を備えた電力系統を取り上げ、この電力系統における最適解の算出処理について説明する。図７は、本発明の実施の形態４における電力系統に２次計画法求解を適用する場合の説明図である。

この電力系統は、発電機１〜発電機３の３台の発電機を有し、２本の送電線を介して負荷に電力を供給するものである。発電機１は、２ＭＷから１０ＭＷまでの電力を出力でき、発電機２は、５ＭＷから２０ＭＷまでの電力を出力でき、さらに、発電機３は、１０ＭＷから３０ＭＷまでの電力を出力できる発電機である。

また、負荷に対しては、２本の送電線を介して５０ＭＷの電力を供給するものとする。なお、図７において、発電機と負荷とを結ぶ２本の送電線は、発電機１と発電機２の出力の総和を送電する設備容量２５ＭＷの送電線と、発電機３の出力を送電する設備容量３０ＭＷの送電線とで構成されている。

また、発電機１〜発電機３の発電コストＣ１〜Ｃ３は、それぞれの発電機の出力をｘ_１〜ｘ_３とすると、下式（１７）〜（１９）で示すような２次式で与えられることを想定する。
Ｃ１＝１０＋１１０ｘ_１＋０．１ｘ_１ ^２ （１７）
Ｃ２＝２０＋１２０ｘ_２＋０．２ｘ_２ ^２ （１８）
Ｃ３＝３０＋１３０ｘ_３＋０．３ｘ_３ ^２ （１９）

上述のような種々の制約条件に基づいて、発電コストを最小化するために、本発明の２次計画求解装置を適用する。本発明の２次計画法求解装置で扱うことのできる最適化問題は、すでに説明したように下式で表す必要がある。
Min ｆ(ｘ)
Subject to:
Ｈ_１ｘ＝ｂ_１
ｂ_２min≦Ｈ_２ｘ≦ｂ_２max
ｘ_min≦ｘ≦ｘ_max
ただし、ｆ(ｘ)＝ｐ^ｔｘ＋０．５ｘ^ｔＱｘ

図７で示した電力系統に関する最適化問題を、上式の形ｆ（ｘ）で表現すると、次式（２０）のようになる。

なお、上式（２０）の右辺には、０次項がない。これは、０次項は、変数の変化によっては変わらないため、最適解を求めるにあたって０次項を考慮する必要がないためである。

Ｈ_１ｘ＝ｂ_１は、需給バランスを表す等式制約として、次式（２１）となる。

また、ｂ_２min≦Ｈ_２ｘ≦ｂ_２maxは、送電線の設備容量の関係から、次式（２２）となる。

さらに、ｘ_min≦ｘ≦ｘ_maxは、発電機１〜発電機３のそれぞれの出力から、次式（２３）となる。

このように式（２０）〜（２３）で数式化された電力系統の発電コストの最小化問題に対しては、実施の形態１〜３で説明した本発明における２次計画法求解装置を適用して、最適解を求めることが可能となる。

実施の形態４によれば、電力系統の総合発電コストを各種の制約を守って最小化する問題を、本発明の２次計画求解装置が要求する入力データの形で表現することにより、本発明の２次計画求解装置を用いて最適解を求めることができる。

本発明の実施の形態１における２次計画法求解装置の構成図である。 本発明の実施の形態１の２次計画法求解装置における求解処理のフローチャートである。 本発明の実施の形態２における２次計画法求解装置の構成図である。 本発明の実施の形態２の２次計画法求解装置における求解処理のフローチャートである。 本発明の実施の形態３における２次計画法求解装置の構成図である。 本発明の実施の形態３の２次計画法求解装置における求解処理のフローチャートである。 本発明の実施の形態４における電力系統に２次計画法求解を適用する場合の説明図である。

符号の説明

１０ ２次計画法求解装置、１１ 入力手段、１２ 変換手段、１３ 修正方程式生成手段、１４ 記憶部、１５ 縮小修正方程式生成手段、１６ 修正量算出手段、１７ 変数変更手段、１８ 繰返し処理判定手段、１９ 最適解出力手段。

Claims (5)

1. 関数型不等式制約を含む２次計画問題の方程式を設定する入力手段と、
   前記関数型不等式制約を関数型等式制約に変換して生成される修正方程式を記憶する修正方程式記憶ファイル、変数の値の履歴を記憶する変数履歴データ記憶ファイル、及び前記変数の上下限制約の値を記憶する上下限制約値記憶ファイルを有する記憶部と、
   前記関数型不等式制約を含む２次計画問題の方程式に対してスラック変数を導入して、関数型等式制約を含む２次計画問題の方程式及び新たな変数の上下限制約に変換し、前記上下限制約の値を前記上下限制約値記憶ファイルに記憶させる変換手段と、
   上下限制約を有する前記新たな変数について、前記上下限制約内の初期値を設定するとともに、前記２次計画問題の最適解において前記上下限制約の境界上にあると仮定する変数を特定し、特定した前記変数の等式制約及び前記上下限制約に対するラグランジュ乗数を用いて修正方程式を生成し、設定した前記初期値を前記変数履歴データ記憶ファイルに記憶させ、生成した前記修正方程式を前記修正方程式記憶ファイルに記憶させる修正方程式生成手段と、
   前記変数履歴データ記憶ファイルの最新データに基づいて前記修正方程式記憶ファイルに記憶された修正方程式を解くことにより、前記最適解に近づくための変数の修正量を算出する修正量算出手段と、
   前記修正量算出手段によって算出された修正量及び前記上下限制約値記憶ファイルに記憶された上下限制約の値に基づいて、前記上下限制約の範囲内に収まる修正後の新たな変数を求めて前記記憶部の前記変数履歴データ記憶ファイルを更新する変数変更手段と、
   前記変数履歴データ記憶ファイルに記憶された変数の履歴データ及びあらかじめ決められた収束判定値に基づいて変数の収束状態を判定し、前記変数が収束していないと判定したときは、前記修正量算出手段に対して、更新された前記変数履歴データ記憶ファイルの最新のデータに基づいて前記修正方程式記憶ファイルに記憶された修正方程式を解くことを再び実行させ、前記変数が収束したと判定したときは、処理を終了すると判定する繰返し処理判定手段と、
   前記繰返し処理判定手段により処理が終了したと判定された場合に、前記記憶部の前記変数履歴データ記憶ファイルから最新の変数を最適解として取り出して出力する最適解出力手段と
   を備えた２次計画法求解装置において、
   前記記憶部は、前記修正方程式よりも次元の小さい縮小修正方程式を記憶する縮小修正方程式記憶ファイルをさらに有し、
   前記修正方程式記憶ファイルに記憶された修正方程式から、前記上下限制約の境界上にあると仮定された変数、及び前記上下限制約に対する前記ラグランジュ乗数を消去した次元の小さい縮小修正方程式を生成し、生成した前記縮小修正方程式を前記記憶部の前記縮小修正方程式記憶ファイルに記憶させる縮小修正方程式生成手段をさらに備え、
   前記修正量算出手段は、前記記憶部の変数履歴データ記憶ファイルの最新のデータに基づいて前記縮小修正方程式記憶ファイルに記憶された縮小修正方程式を解くことにより、前記最適解に近づくための変数の修正量を算出し、
   前記繰返し処理判定手段は、前記変数履歴データ記憶ファイルに記憶された変数の履歴データ及びあらかじめ決められた収束判定値に基づいて変数の収束状態を判定し、前記変数が収束していないと判定したときは、前記縮小修正方程式生成手段に対して、更新された前記変数履歴データ記憶ファイルの最新のデータ及び前記修正方程式記憶ファイルに記憶された修正方程式に基づいて縮小修正方程式を再び生成させる
   ことを特徴とする２次計画法求解装置。
2. 請求項１に記載の２次計画法求解装置において、
   前記変数変更手段は、前記修正量算出手段によって算出された前記修正量の全量の修正をそれぞれの変数に対して行った場合に、修正後の全ての変数が上下限制約以内であるときは前記修正後の変数を新たな変数の値として変数履歴データ記憶ファイルを更新し、修正後の変数の少なくともいずれか１つが上下限制約を超えるときは、全ての修正量に対して等しい１未満の係数を掛け合わせて求まる修正補正量を用いてそれぞれの変数を修正した後の全ての変数が上下限制約を超えない最大の前記係数を求めることにより修正後の新たな変数を求めて変数履歴データ記憶ファイルを更新することを特徴とする２次計画法求解装置。
3. 請求項２に記載の２次計画法求解装置において、
   前記記憶部は、関数型等式制約を記憶する関数型等式制約記憶ファイルをさらに有し、
   前記変換手段は、変換した前記関数型等式制約を前記関数型等式制約記憶ファイルに記憶させ、
   前記変数変更手段は、前記修正量算出手段によって算出された前記修正量の全量の修正をそれぞれの変数に対して行った場合に、修正後の変数の少なくともいずれか１つが上下限制約を超えるときは、全ての修正量に対して等しい１未満の係数を掛け合わせて求まる修正補正量を用いてそれぞれの変数を修正した後の全ての変数が上下限制約を超えない最大の前記係数を求めることにより修正後の新たな変数を求めて変数履歴データ記憶ファイルを更新した後に、前記変数履歴データ記憶ファイルの変数及び前記関数型等式制約記憶ファイルの関数型等式制約を用いて前記関数型等式制約の誤差を第１の誤差として算出し、さらに、上下限制約の境界上にない変数に対して等しい１未満の係数を掛け合わせて求まる仮定修正補正量によりそれぞれの変数を修正した後の変数が上下限制約を超えない最大の前記係数を求めることにより仮定修正後の新たな変数を求め、前記仮定修正後の新たな変数及び前記関数型等式制約記憶ファイルの関数型等式制約を用いて前記関数型等式制約の誤差を第２の誤差として算出し、前記第１の誤差が前記第２の誤差よりも大きい場合には、仮定修正後の新たな変数により前記変数履歴データ記憶ファイルを更新することを特徴とする２次計画法求解装置。
4. 請求項１ないし３のいずれか１項に記載の２次計画法求解装置において、
   前記記憶部は、縮小修正方程式の解法で用いた三角分解結果及び前記縮小修正方程式の解法に当たって上下限制約の境界上にあると仮定した変数を三角分解履歴データとして記憶する三角分解履歴データ記憶ファイルをさらに有し、
   前記修正量算出手段は、縮小修正方程式の解法に当たって三角分解を実施する毎に、前記三角分解履歴データを前記三角分解履歴データ記憶ファイルに記憶させ、今回の縮小修正方程式の解法に当たって上下限制約の境界上にあると仮定した変数と、前記三角分解履歴データ記憶ファイルに記憶された前回の三角分解履歴データにおける上下限制約の境界上にあると仮定した変数とを比較し、前記上下限制約の境界上にあると仮定した変数の違いが１つのみであると判断したときは、今回の縮小修正方程式の解法に当たって前記三角分解履歴データ記憶ファイルに記憶された前回の三角分解履歴データにおける三角分解結果を用いて修正量を算出することを特徴とする２次計画法求解装置。
5. 請求項１ないし４のいずれか１項に記載の２次計画法求解装置において、
   前記変数変更手段は、前記修正量算出手段によって算出された前記修正量の全量の修正をそれぞれの変数に対して行った場合に、修正後の全ての変数が上下限制約以内であるときは前記修正後の変数を新たな変数の値として変数履歴データ記憶ファイルを更新し、前記修正後の変数を用いて上下限制約に対するラグランジュ乗数を求め、前記ラグランジュ乗数の中に負の値を持ち対応する変数が上下限制約の上限値であると仮定されているものがある場合、あるいは、前記ラグランジュ乗数の中に正の値を持ち対応する変数が上下限制約の下限値であると仮定されているものがある場合には、これらの変数を上下限制約の境界上にあると仮定した変数から除外して前記変数の値を変更して前記記憶部の変数履歴データ記憶ファイルを更新し、
   前記繰返し処理判定手段は、前記変数変更手段により除外される変数がある場合には繰返し処理を行うと判定し、前記縮小修正方程式生成手段に対して、更新された前記変数履歴データ記憶ファイルの最新のデータ及び前記修正方程式記憶ファイルに記憶された修正方程式に基づいて縮小修正方程式を再び生成させ、前記変数変更手段により除外される変数がない場合には最適解が求まったとして繰返し処理を行わないと判定する
   ことを特徴とする２次計画法求解装置。

Images