(57)【要約】      （修正有）【課題】電力網における電力潮流を最適化する方法を提供する。【解決手段】最初に最適化問題を１組の別個のパラメーター化された最適化問題に分解することによって、電力網における電力潮流が最適化される。別個の最適化問題は互いに独立しており、分解は対応する乗数を有する、双対化され結合された制約に基づく。各最適化問題を独立して解いて、対応する解と、パラメーターの変化に対する各解の感度とを得る。対応する解及び感度を用いてパラメーターを更新し、収束するまで反復する。【選択図】図３
2014166134.tif 000002
【特許請求の範囲】
【請求項１】
最適化問題を解くことによって電力網における電力潮流を最適化する方法であって、
前記最適化問題を１組の別個のパラメーター化された最適化問題に分解するステップであって、前記組における前記別個のパラメーター化された最適化問題は互いに独立しており、前記分解は対応する乗数を有する制約に基づき、該乗数は前記別個のパラメーター化された最適化問題のパラメーターであり、前記制約は双対化され結合された制約である、ステップと、
前記各別個のパラメーター化された最適化問題を独立して解いて、対応する解と、前記パラメーターの変化に対する前記各解の感度とを得る、解くステップと、
前記対応する解及び前記感度を用いて前記パラメーターを更新するとともに、収束するまで前記分解するステップと、前記解くステップと、該更新するステップとを繰り返す、更新するとともに繰り返すステップと、
を含み、前記ステップはプロセッサにおいて実行される、最適化問題を解くことによって電力網における電力潮流を最適化する方法。
【請求項２】
請求項１に記載の方法であって、
前記制約の変数は連続して制御可能である、請求項１に記載の方法。
【請求項３】
請求項１に記載の方法であって、
ノード及びエッジのグラフによって前記電力網を表すステップであって、前記ノードはバスに接続された発電機及び負荷を表し、前記ノード間の前記エッジ（ｉ，ｊ）は送電線路を表す、請求項１に記載の方法。
【請求項４】
請求項３に記載の方法であって、
該方法への入力は、
前記グラフと、
前記送電線路のアドミタンス
【数１】
2014166134.tif 000078
であって、式中、ｇは前記送電線路のコンダクタンスを表し、ｂは前記送電線路のサセプタンスを表し、
【数２】
2014166134.tif 000079
である、前記送電線路のアドミタンスと、
前記発電機によって生成することができる有効電力
【数３】
2014166134.tif 000080
及び前記発電機によって生成することができる無効電力
【数４】
2014166134.tif 000081
に対する制約と、
前記送電線路上を送電される皮相電力及び有効電力に対する制約
【数５】
2014166134.tif 000082
と、
前記バスにおける電圧の大きさに対する制限
【数６】
2014166134.tif 000083
と、
前記送電線路上での熱損失に対する制約
【数７】
2014166134.tif 000084
と、
を含み、該方法の出力は、
前記バスにおける複素数値電圧Ｖｉ並びに前記発電機の有効電力レベル及び無効電力レベル
【数８】
2014166134.tif 000085
を含む、請求項３に記載の方法。
【請求項５】
請求項４に記載の方法であって、
前記最適化は、有効電力発電変数
【数９】
2014166134.tif 000086
と、無効電力発電変数
【数１０】
2014166134.tif 000087
と、前記バスにおける複素数値電圧Ｖ＝（Ｖ１，．．．，Ｖ｜Ｎ｜）とに依存する決定関数ｆ（ＰＧ，ＱＧ，Ｖ）を用いる、請求項４に記載の方法。
【請求項６】
請求項５に記載の方法であって、
前記決定関数ｆは二次であり、厳密に増加するもの、すなわち、
【数１１】
2014166134.tif 000088
であり、式中、ｃは、ｃ２ｉ，ｃ１ｉ≧０∀ｉ∈Ｎである定数を示す、請求項５に記載の方法。
【請求項７】
請求項１に記載の方法であって、
前記網の実現可能な動作の制限と、決定変数に対する等式制約と、不等式制約と、界とが用いられる、請求項１に記載の方法。
【請求項８】
請求項１に記載の方法であって、
不等式制約が、平滑化パラメーターを用いて平滑化された等式制約として表され、該平滑化パラメーターは前記更新するステップを繰り返すステップの間、ゼロに低減される、請求項１に記載の方法。
【請求項９】
請求項１に記載の方法であって、
前記パラメーターの前記更新は線分探索手順を用いて実行される、請求項１に記載の方法。
【請求項１０】
請求項１に記載の方法であって、
前記パラメーターの前記更新は信頼領域を用いて実行される、請求項１に記載の方法。
【請求項１１】
請求項１に記載の方法であって、
前記更新するステップは、前記感度を用いた更新と、前記感度を用いない更新とを交互に行う、請求項１に記載の方法。
【請求項１２】
請求項１に記載の方法であって、前記感度は前記乗数の変化に対する前記解における変動を評価する、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、電力網に関し、より詳細には、この網における電力潮流を最適化することに関する。
【背景技術】
【０００２】
電力網は、送電線路に接続されたバスを含む。これらのバスは、局所的に発電機及び負荷に接続されている。最適電力潮流（ＯＰＦ：ｏｐｔｉｍａｌ  ｐｏｗｅｒ  ｆｌｏｗ）解析が、多くの場合、網の動作を監視及び制御するのに用いられる。電力潮流は、電圧の大きさ及び位相角に部分的に依存する。バス上の電力潮流及び電圧レベルは、大きさ、位相、送電される電力、発電機容量、熱損失等の制約を条件として目的関数を最小化することによって最適化される。
【０００３】
ほとんどの従来のＯＰＦ最適化は、
（ｉ）集中型の方式で問題を解き、
（ｉｉ）バスにわたって最適化を分散させるのに網のトポロジーを利用しない。
【０００４】
最適化問題を分散させるいくつかの従来の方法は、
（ｉ）反復部分構造化とも呼ばれるシュール補元法（Ｓｃｈｕｒ  ｃｏｍｐｌｅｍｅｎｔ  ｍｅｔｈｏｄ）を用いて、最適化問題における単一のステップの計算を分散させる。
（ｉｉ）最適化問題が双対分解によって分散されるとき、最適化問題を解くのに従来の劣勾配法が用いられる。劣勾配法は略線形に（ｓｕｂ−ｌｉｎｅａｒｌｙ）解に収束する。
【０００５】
したがって、計算を適切に分散させることによって、効率的でかつ好都合な方法で電力網における電力潮流を最適化する必要性が依然として存在する。
【０００６】
特許文献１は、最適な電力潮流と、この最適な電力潮流に基づく電力系統の利用可能な送電能力とを求める当該電力系統を動作させるシステム及び方法を記載している。このシステムは、発電機位相角が事前に設定された値を超えないという制約条件を有する、時間関数によって規定された発電機位相角を含めて、発電機の機械的出力及び電気的出力を求めることによって発電機の初期位相角及び最大電力値に関連付けられたデータを導出する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第６６２５５２０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
電力網における電力潮流を最適化する方法を提供することが求められている。
【０００９】
本発明の実施の形態は、分解及び調整手順を用いて電力網における電力潮流を最適化する方法を提供する。分解手順は、最適化問題を、互いに独立した１組のより小さな別個のパラメーター化された最適化問題に分散させる。調整手順は、個々の問題に関連付けられたパラメーターを変更して、問題全体の解が得られることを確実にする。
【課題を解決するための手段】
【００１０】
方法は、結合された制約を双対化して、１組のより小さな分離した最適化問題を得ることに基づいている。本方法の１つの実施の形態では、調整手順において半平滑方程式の理論が用いられている。半平滑方程式理論によって、解の近傍において超線形収束を理論的に保証することができることが確実になる。さらに、この理論によって、メリット関数を用いて、解の近くにない初期パラメーターを用いた解への大域的収束を確実にすることが可能になる。
【００１１】
１つの実施の形態では、平滑化に基づく方法の理論を用いて、分解された問題を解く。平滑化パラメーターの単調減少を用いて、解の近傍において超線形収束を理論的に保証することができることを確実にする。さらに、この理論によって、メリット関数を用いて、初期パラメーターが最適値から遠く離れている場合であっても解への大域的収束を確実にすることが可能になる。
【発明の効果】
【００１２】
これにより、電力網における電力潮流を最適化する方法を提供することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態によって用いることができる電力網及びこの電力網を表すグラフの概略図である。
【図２】従来の電力最適化方法のフローチャートである。
【図３】本発明の実施形態による電力最適化方法のフローチャートである。
【図４】本発明のいくつかの実施形態による電力最適化方法の擬似コードである。
【図５】本発明のいくつかの実施形態による電力最適化方法の擬似コードである。
【発明を実施するための形態】
【００１４】
電力網トポロジー及びグラフ図
図１は、本発明の実施形態を用いることができる電力網トポロジーを示している。この網は、変換器によって接続されたＡＣ成分及びＤＣ成分を含むことができる。唯一の要件は、網の動作を制御する変数及び制約が連続的に制御可能であるということである。
【００１５】
この網は、負荷（Ｌ）１２及び発電機（Ｇ）１４に局所的に接続されたバス１０を含む。これらのバスは、ブランチ（Ｂ）としても知られている送電線路２０によって相互接続されている。これらの送電線路のうちの幾つかは、変圧器（Ｔ）２２に接続することができる。
【００１６】
発電機は、有効電力（例えばメガワット（ＭＷ：Ｍｅｇａ  Ｗａｔｔｓ）で測定される）及び無効電力（メガボルトアンペアリアクティブ（ＭＶａｒ：Ｍｅｇａ  Ｖｏｌｔ  Ａｍｐｅｒｅ  Ｒｅａｃｔｉｖｅ）で測定される）を供給する。
【００１７】
最適化のためのパラメーターには、ブランチインピーダンス及びバス固定並列アドミタンスに基づくアドミタンス行列と、潮流容量定格（ｆｌｏｗ  ｃａｐａｃｉｔｙ  ｒａｔｉｎｇｓ）、すなわち、熱定格（ｔｈｅｒｍａｌ  ｒａｔｉｎｇｓ）によって制約される最大総電力潮流とが含まれるが、これらに限定されるものではない。
【００１８】
この網のトポロジーは、エッジ（送電線路）３１によって接続されたノード（発電機及び接続された負荷）３０からなるグラフＧによって表すことができる。
【００１９】
入力
最適化方法への入力は、以下のものを含む。
１．Ｎ個のノードの集合がＥ個のエッジ（ｉ，ｊ）の集合によって接続されたグラフＧ（Ｎ，Ｅ）。
２．線路のアドミタンスｙｉｊ＝ｇｉｊ＋ｊｂｉｊ∀（ｉ，ｊ）∈Ｅ、式中、ｇは、線路のコンダクタンスを表し、ｂは、線路のサセプタンス（アドミタンスの虚部）を表し、
【数１】
2014166134.tif 000003
である。
３．発電機が生成することができる有効電力
【数２】
2014166134.tif 000004
と、発電機が生成することができる無効電力
【数３】
2014166134.tif 000005
とに対する制約。
４．線路上を送電される皮相電力及び有効電力に対する制約
【数４】
2014166134.tif 000006
。
５．バスにおける電圧の大きさに対する制限
【数５】
2014166134.tif 000007
。
６．線路上での熱損失に対する制約
【数６】
2014166134.tif 000008
。
【００２０】
出力
方法の出力は、バスにおける複素数値電圧Ｖｉ∀ｉ∈Ｎと、発電機の有効電力レベル及び無効電力レベル
【数７】
2014166134.tif 000009
とを含む。
【００２１】
最適化は、有効電力発電変数（ｇｅｎｅｒａｔｉｏｎ  ｖａｒｉａｂｌｅｓ）
【数８】
2014166134.tif 000010
と、無効電力発電変数
【数９】
2014166134.tif 000011
と、バスにおける複素数値電圧Ｖ＝（Ｖ１，．．．，Ｖ｜Ｎ｜）とに依存する決定関数ｆ（ＰＧ，ＱＧ，Ｖ）を用いる。
【００２２】
最適電力潮流
決定関数ｆの形式は、二次であり、厳密に増加するもの、すなわち、
【数１０】
2014166134.tif 000012
であり、式中、ｃは、ｃ２ｉ，ｃ１ｉ≧０∀ｉ∈Ｎである定数を示す。
【００２３】
網の実現可能な動作の制限をモデル化するのに、決定変数に対する等式制約と、不等式制約と、界とが用いられる。等式制約
【数１１】
2014166134.tif 000013
によって、電気網の動作をモデル化することができる。式中、Ｎｅは、等式制約の数を示す。
【００２４】
発電機によって発電される電力に対する制約、バスにおける電圧の大きさ、線路上を送電される電力及び実現可能な動作を確保する熱損失に対する制限が、不等式制約
【数１２】
2014166134.tif 000014
としてモデル化される。式中、Ｎｉは、不等式制約の数を示す。
【００２５】
バスにおける電圧及び発電機によって生成される電力を求めるように、以下の最適化問題が大域的最適性に向けて解かれる。
【数１３】
2014166134.tif 000015
式中、ｈｎは、等式制約を表し、ｇｎは、不等式制約を表す。
【００２６】
最適電力潮流制約
好ましい実施形態では、等式制約
【数１４】
2014166134.tif 000016
は、以下のように表される。
【数１５】
2014166134.tif 000017
式中、Ｓｉｊ＝Ｐｉｊ＋ｊＱｉｊは、バスｉからバスｊに送電される複素数値電力を示し、Ｓｊｉ＝Ｐｊｉ＋ｊＱｊｉは、バスｊからバスｉに送電される複素数値電力を示し、（Ｖｉ）＊は、複素数値変数の複素共役を示し、
【数１６】
2014166134.tif 000018
は、発電機によって生成される複素数値電力を示し、
【数１７】
2014166134.tif 000019
は、複素数値電力需要量を示す。線路上の電力潮流を表すこれらの変数は、便宜上用いられるものである。
【００２７】
好ましい実施形態では、不等式制約
【数１８】
2014166134.tif 000020
は、以下のように表される。
【数１９】
2014166134.tif 000021
【００２８】
従来の双対分解に基づく最適化
図２は、以下の式（２）によって定義されるような最適化問題２０１を解く従来の方法を示している。
【数２０】
2014166134.tif 000022
【００２９】
最適化問題は、等式制約Ａ１ｘ１＋Ａ２ｘ２＝ｂを除いて、ｘ１、ｘ２を分離するように分解することができることに注目されたい。これらの結合制約は、以下の式（３）のように、目的関数における制約を、乗数ξを用いて双対化する（２１０）ことによって取り除くことができる。
【数２１】
2014166134.tif 000023
【００３０】
式（３）における最適化問題を分解して（２２０）、変数ｘ１２２１及びｘ２２２２を１組の別個のパラメーター化された最適化問題及び対応する制約に分離することができ、次にその組の最適化問題ｘ１、ｘ２を独立して解くことができる。本明細書において用いられる例では、組は２つの別個の問題ｘ１及びｘ２を含む。しかしながら、各問題は必要に応じて、より細かい粒度に更に分解することができることが理解される。
【００３１】
【数２２】
2014166134.tif 000024
２３１及び
【数２３】
2014166134.tif 000025
２３２によって、分解された問題のそれぞれに対する最適解を表す。乗数ξの正しい選択が完全に知られていることはほとんどない。結果として、本方法は、収束テスト２４０を用いて収束２５０まで反復し（２７０）、収束していない場合、制約
【数２４】
2014166134.tif 000026
が概ね満たされるまで、
【数２５】
2014166134.tif 000027
のみを用いて乗数ξを更新する（２６０）。
【００３２】
線分探索手順を用いて更新を実行し、極小値を得ることができる。線分探索によって、目的関数がそれに沿って低減する降下方向、及びステップサイズを得る。降下方向は、勾配降下法、ニュートン法、及び準ニュートン法等の様々な方法によって計算することができる。
【００３３】
代替的に、信頼領域を用いて（二次）モデル関数の領域のサブセットを最適化する。信頼領域内で目的関数の適切なモデルが見つかった場合、領域は拡張され、そうでない場合、領域は縮小される。
【００３４】
高速双対分解に基づく最適化
図３は、双対分解に基づく方法の収束を加速する一実施形態を示している。初期ステップは、１組の別個の最適化問題を得る従来の方法について上記で説明したとおりである。
【００３５】
主要な差異は以下のとおりである。最適化のそれぞれを解くとき、本発明による方法は上記と同様に最適解
【数２６】
2014166134.tif 000028
２３１、２３２を得るが、ξの選択に対する解の感度
【数２７】
2014166134.tif 000029
３３１、３３２も得る。
【００３６】
感度は、乗算パラメーターξの変化に対する解
【数２８】
2014166134.tif 000030
の変動を評価（ｍｅａｓｕｒｅ）する。
【００３７】
更新３６０が
【数２９】
2014166134.tif 000031
を用いるという点で、更新も異なる。
【００３８】
感度は、以下の線形相補性問題の解によって得ることができる。ｘ１についての部分問題において、感度は以下のように得られる。
【数３０】
2014166134.tif 000032
式中、λ及びνはそれぞれ、不等式制約及び界に対応する乗数であり、上付き文字Ｔは転置演算子であり、Ｌ１（ｘ１，λ１，ν１；ξ）は以下のように定義されるラグランジュ関数である。
【数３１】
2014166134.tif 000033
【００３９】
ｘ２の感度は、類似した方式で得ることができる。連立方程式（４）は、解が
【数３２】
2014166134.tif 000034
を満たすとき（これは強相補性とも呼ばれる）、一次方程式の解にまで縮約することができる。
【００４０】
乗数ξに対する感度を用いて、双対化された制約の線形化を用いて、探索方向ｄξを求めることができる。
【数３３】
2014166134.tif 000035
【００４１】
これは、双対化制約のニュートン方向に類似の方向を取ることに相当し、これがまさに収束が加速される理由である。ニュートンステップは、解の近傍にあるとき、局所的に超線形に収束することが知られている。従来の双対分解法はこの急速な局所収束特性を有していない。
【００４２】
さらに、この手法はメリット関数
【数３４】
2014166134.tif 000036
を定義して、式（２）の最適化問題２０１を解くことに向けた方法の進行を評価することを可能にする。式中、
【数３５】
2014166134.tif 000037
はユークリッドベクトルノルムを表す。
【００４３】
メリット関数は、十分な減少を要求することを通じて次の乗数の選択に影響を与える。ここで、ステップ長α∈（０，１］は
【数３６】
2014166134.tif 000038
を満たすように選択され、式中、β＞０は通例、小さな定数であり、φ’（ξ；ｄξ）は方向ｄξに沿った点ξにおけるメリット関数の方向微分である。この方向微分は、以下の極限によって数学的に定義される。
【数３７】
2014166134.tif 000039
【００４４】
最適電力潮流に向けた高速双対分解に基づく最適化
網内のエッジをＮｇ個のより小さなエッジ組（Ｅ１，Ｅ２，．．．，ＥＮｇ）に分割することを考える。ここで、組は別個であり、それらの和集合は全てのエッジの組Ｅである。エッジ組Ｅｋ内のバスの組はＮｋによって表される。このより小さな網の組Ｇ（Ｎｋ，Ｅｋ）を利用すると、最適電力潮流問題は以下に示すように等価に定式化することができる。さらに、Ｋｉによって、ノードｉが属する網の組を表す。
【００４５】
各部分網の目的関数は以下のように示すことができる。
【数３８】
2014166134.tif 000040
式中、
【数３９】
2014166134.tif 000041
は、ノード組Ｎｋ内のノードｉにおける実電力（ｒｅａｌ  ｐｏｗｅｒ）、無効電力及び電圧である。定数は以下のように選択される。
【数４０】
2014166134.tif 000042
式中、ｎｉはノードｉが現れる部分網ｋの数を示す。
【００４６】
制約は、電気網の動作を以下の等式制約によってモデル化する。
【数４１】
2014166134.tif 000043
式中、Ｎｅｋは部分網ｋ内の等式制約数を表す。
【００４７】
発電機によって生成される電力に対する制限、バスにおける電圧の大きさに対する制限、線路上を送電される電力及び実現可能な動作を確保する熱損失に対する制約を不等式制約
【数４２】
2014166134.tif 000044
としてモデル化する。式中、Ｎｉｋは部分網ｋ内の不等式制約の数を示す。
【００４８】
また、電力発電及びバスにおける電圧の大きさに対する制約も課せられる。
【００４９】
バスにおける電圧及び発電機によって生成される電力を求めるように、以下の最適化問題が大域的最適性に対して解かれる。
【数４３】
2014166134.tif 000045
式中、制約の最後の組は、異なる部分網ｋによって共有されるノードの発電機電力及び電圧を同等とみなす。上記の定式は最適電力潮流定式と全く同一である。
【００５０】
説明を容易にするように、以下において表記ｘｋ＝（ＰＧ，ｋ，ＱＧ，ｋ，Ｖｋ）が用いられ、或るｉ∈Ｎｋについて
【数４４】
2014166134.tif 000046
が用いられる。この表記を用いて、式（２）の問題は以下のように再定式化することができる。
【数４５】
2014166134.tif 000047
【００５１】
上記の問題の方程式は、最適化における等式制約の組を取り除き、それを以下のように目的関数と置き換えることによって、より小さな最適化問題に分解される。
【数４６】
2014166134.tif 000048
式中、
【数４７】
2014166134.tif 000049
は複数の部分網にわたって共有されるノードの電力発電変数及び電圧変数のコピーを同等とみなす等式制約の乗数である。この手順は結合制約の双対化と呼ばれる。これは、部分網によって切り離された最適化問題を与える。
【００５２】
部分網ごとの最適化は
【数４８】
2014166134.tif 000050
であり、ここで、ｋ＝ｍｉｎ（Ｋｉ）の場合の目的関数は
【数４９】
2014166134.tif 000051
であり、ｌ≠ｍｉｎ（Ｋｉ）の場合は
【数５０】
2014166134.tif 000052
である。
【００５３】
分解ステップは、乗数ξの所与の選択について、部分網ｋ＝１，．．．，Ｎｇの最適化問題のそれぞれを解く。
【数５１】
2014166134.tif 000053
によって、部分網ｋに対応する問題に対する最適解を表す。さらに、
【数５２】
2014166134.tif 000054
によって、乗数の所与の選択についての部分網ｋに対する最適解の感度を表す。感度は以下のように得ることができる。部分網ｋの一次最適性条件は
【数５３】
2014166134.tif 000055
であり、ここで、ラグランジュ関数は以下のように定義される。
【数５４】
2014166134.tif 000056
式中、表記
【数５５】
2014166134.tif 000057
は等式制約
【数５６】
2014166134.tif 000058
の乗数を表し、
【数５７】
2014166134.tif 000059
は不等式制約
【数５８】
2014166134.tif 000060
の乗数を表す。
【００５４】
部分網ｋに対応する問題に対する最適解への解
【数５９】
2014166134.tif 000061
は、上記で列挙した一次最適性条件を必ず満たすことになる。乗数ξに対する最適解の感度は、変数ｘｋ及び乗数（λｈ，ｋ，λｇ，ｋ）に関して一次条件を微分することによって得られる以下の線形相補性問題を解くことによって得ることができる。
【数６０】
2014166134.tif 000062
【００５５】
感度計算を用いて、以下の式を解くことによって乗数の探索方向ｄξを計算する。
【数６１】
2014166134.tif 000063
【００５６】
この探索方向を用いて、以下で説明するように新たな１組の乗数ξ＋＝ξ＋αｄξが選択される。式中、０＜α≦１である。メリット関数と呼ばれる関数φ（ξ）を以下のように定義する。
【数６２】
2014166134.tif 000064
【００５７】
メリット関数は、様々な部分網を結合する双対化された制約の残差のユークリッドノルムである。これは、式（１）における元の問題が解かれた度合いを評価する。φ（ξ）≒０のとき、本方法は式（１）の解としての
【数６３】
2014166134.tif 000065
で終了する。
【００５８】
乗数に関するステップは、メリット関数が以下の条件に規定されているように減少するよう選択される。
【数６４】
2014166134.tif 000066
式中、φ’（ξ；ｄξ）は、ｄξに沿った点ξにおけるメリット関数の方向微分であり、以下の極限によって数学的に定義される。
【数６５】
2014166134.tif 000067
【００５９】
新たな乗数ξ＋を用いて、式（３）における分解された最適化、感度計算（４）、及び乗数ステップ計算（５）は、メリット関数φ（ξ）がゼロに近づくまで繰り返される。
【００６０】
方法ステップの説明が図４に提供される。
【００６１】
最適な電力潮流の平滑化を用いた高速双対分解
高速分解手法は、双対化された制約の乗数ξに関する感度の計算に基づく。しかしながら、感度はいくつかの条件の下では存在しない場合がある。例えば、最適化問題（３）において
【数６６】
2014166134.tif 000068
が成り立たないときである。そのような場合、方向微分のみを得ることができる。
【００６２】
この状況を修正するように、以下のように部分網ｋのそれぞれについて解かれる問題の変更を考える。定常条件（９）を以下のように変更することを考える。
【数６７】
2014166134.tif 000069
式中、関数ψ（ａ，ｂ；τ）は、以下の特性を満たす相補性制約の平滑化関数である。
（ｉ）ψ（ａ，ｂ；０）＝０⇔ａ≧０⊥ｂ≧０
（ｉｉ）ψ（ａ，ｂ；τ）は全てのτ＞０について連続して微分可能である。
【００６３】
第１の特性が、τ→０であるときに連続平滑化問題（ｓｅｑｕｅｎｃｅ  ｓｍｏｏｔｈｅｄ  ｐｒｏｂｌｅｍ）を解くことによって式（９）に対する解を復元することができることを確実にする一方、第２の特性は、全てのτ＞０について、最適化問題が平滑であり連続して微分可能であることを確実にする。そのような関数にはいくつかの選択肢が存在する。
１．
【数６８】
2014166134.tif 000070
２．
【数６９】
2014166134.tif 000071
３．ψ（ａ，ｂ；τ）＝ａｂ−τ，ａ，ｂ≧０
【００６４】
第３の選択肢において、ａ及びｂの非負性が明示的に強制されなくてはならない。これはまさに内点法が行うことである。
【００６５】
この変更を用いて、元の問題（１）に対する解が得られる方法を、最初に固定のτ＞０について或る特定の許容範囲まで式（１４）における問題を解き、次にτ→０を減少させて極値における式（１）に対する解を得ることに言い換えることができる。
【００６６】
式（１４）に対する解を
【数７０】
2014166134.tif 000072
によって表す。平滑化の場合、乗数ξに対する解の感度は、以下の一次方程式の解として計算することができる。
【数７１】
2014166134.tif 000073
【００６７】
これらは、式（１０）におけるような線形相補性方程式とは対照的に一次方程式であることに注目されたい。
【００６８】
感度計算を用いて、以下の式を解くことによって乗数の探索方向ｄξを計算する。
【数７２】
2014166134.tif 000074
【００６９】
この探索方向を用いて、以下で説明するように新たな１組の乗数ξ＋＝ξ＋αｄξが選択される。式中、０＜α≦１である。メリット関数と呼ばれる関数φ（ξ）を以下のように定義する。
【数７３】
2014166134.tif 000075
【００７０】
メリット関数は、異なる部分網を結合する双対化された制約の残差のユークリッドノルムである。これは、元の問題（１）が解かれている度合いを評価する。φ（ξ；τ）≒τであるとき、特定の平滑化パラメーター値についての反復が終了することができ、パラメーターを減少させる。φ（ξ；τ）≒０であるとき、方法は式（１）の解として
【数７４】
2014166134.tif 000076
を有して終了する。
【００７１】
乗数のステップは、メリット関数が以下の条件に表されるように減少するように選択される。
【数７５】
2014166134.tif 000077
ここで、∇ξφ（ξ；τ）は所与の点ξにおけるメリット関数の勾配である。式（１３）におけるような方向微分の代わりに全微分（ｆｕｌｌ  ｄｅｒｉｖａｔｉｖｅ）を定義することができる。平滑化パラメーターが超線形に減少するように選択される場合、式（１）に対する解の近傍における高速な局所的収束を得ることができる。
【００７２】
図４及び図５は上記の実施形態の擬似コードを示している。本方法のステップは、当該技術分野において既知のメモリ及び入出力インターフェースに接続された１つ又は複数のプロセッサにおいて実行することができる。
【図１】
2014166134.tif 000089
【図２】
2014166134.tif 000090
【図３】
2014166134.tif 000091
【図４】
2014166134.tif 000092
【図５】
2014166134.tif 000093
【外国語明細書】
2014166134.tif 000094
2014166134.tif 000095
2014166134.tif 000096
2014166134.tif 000097
2014166134.tif 000098
2014166134.tif 000099
2014166134.tif 000100
2014166134.tif 000101
2014166134.tif 000102
2014166134.tif 000103
2014166134.tif 000104
2014166134.tif 000105
2014166134.tif 000106
2014166134.tif 000107
2014166134.tif 000108
2014166134.tif 000109
2014166134.tif 000110
2014166134.tif 000111
2014166134.tif 000112
2014166134.tif 000113
2014166134.tif 000114
2014166134.tif 000115
2014166134.tif 000116
2014166134.tif 000117
2014166134.tif 000118
2014166134.tif 000119
2014166134.tif 000120
2014166134.tif 000121
2014166134.tif 000122
2014166134.tif 000123
2014166134.tif 000124
2014166134.tif 000125