逐次近似評価法の収束の証明

逐次近似評価法の収束の証明

（昭和47年10月20日 原稿受理）

電気工学教室伊藤輝生

Convergence Proof of the Numerical Method of Successive

by Te斑o ITOH

  桓甑spapeピ， c◎nveτgence◎パheΩume驚ica1 meth◎d◎f successive apPτ◇ximati◎n of performance indecies is proved， which solves optimal control problems of discrete line雛system§with bou且ded c◎ntど砲eピ餓d袈ad影aticρerf◎宮mance i垣ecies、

；に：限：操麓＿＿＿一巳i馳⑤

解法として，逐次近似評価法を提案した％ そこ       N−・

において，嚇解への糠の証明を省略したの α・＝、．。蕊ば φz−℃φε堪翻

する。       b④：Σφ℃φ伺d

       ゴ＝

2．文献〔1〕の結果      である。また（4）式をDP法により表現すれ 文献〔1〕において導出された結果についてま

ば，残り N一為＋1段最適評価が

とめておく。系および評価が       W舟＋・一躍゜ （ ＋1）P°（N− ＋1）〆 ＋1）

允（〃十1）＝φκ（の十山（の，〃＝0，…，1V−1

      ①

一ト2Lo（ハ「一ゐ十1）欝o（是十1）十κo（N一ゐ十1）

      （6）

   N       であらわされるとき，ゐ段の最適操作量は

であるとき，与えられた初期値淘（0）＝卯。に対       （7）

◎，…，2V−1を求める問題の解は， Kuhn・Tucker

の条件よりパ個の連立躍式       （8）

      となり，残り1V一為段評価は，

・・（ ）一・at［（一・／・・）｛，怠、・〃（ノ）  撫一κW・（N一力）ヅ（〃）

    ⇒］・∫一・・…−4）靭（ 十2LO（ハr一ゐ）席o（〃）十1ζo（2V一ゐ∧τ一鳶）＝φア（Ω十Po（2V一丘十1））φ）（9）

の解として与えられる。ここで，       一（1−1α［βo（1V一ゐ）エo（〃）

 124

＋θ・（2V一為）］Dγ。（N一為）β゜ノ（N一のβ§（N一為）  以上の関係を利用した数値計算アルガズムは L・（N−〃）＝L・（2V一百）φ         つぎのようである。（10）式中のα［β゜（1V−〃）

  ＿γ・（1V一鳶）｛二θo（1V一力）＋α［β。（1V一め躍。（の   ×ダ（め＋θ℃V一力）］の代りに・

  十θo（ハr・一の仁一1αμ〕o（N一のκo（為）  ノ  ピ     1α心兎1≦1，ゐ＝4，…，2V−1     （15）

  ＋θ゜（1v−〃）］Dβ゜（N一め        、 を満足するα悟為を代入し， P（o）−o， L（o）−o，

X°（』V一為㍉＝K◎（2V一力十1）      κ（◎）＝◎，を与えて，（8）（1◎）式の繰返し関係   …γ゜（1V− ）（（θ゜（2V− ））2      を用いれば，β（2V一ノ），θ（1V一ノ），ノー1，…，1V−1，

  一減玖N一為）躍§（カ）＋θ゜（N一力川［1  一が，α｝，…・α・一・一・の関数として・また埠）・

  十（θo（2V一 ））2］一α［βo（1V− ） o（ ）     α1，…，αN．1，の関数としてあらわされるから，

  ＋θ§ρV一為）］θ奪（2V の）      （1◎）   （8）（1◎）式のような最適繰返し関係は，

α同一

専o1］⑰ま∵α［㌘：竺（彦）十θ（ハ／一一ゑ）］，N−1     （16）

となる。また（9）式は，もともと       ∧同

、 ．、一γ・（2V一克）｛が（ゐ）−8・（N一拠ゐ） 恥＝恩｛輪一α［β（N カ）κ（カ）÷θ（醐］）2   ＿θ・（2V−〃））・裾・ P＊（N−〃）卯・（の      一〇        （17）

  ＋2L＊（ハr一力）κo（〃）十κ＊（∧r一力）     （12）   を満足する場合であることがわかる。したがって   ここで，p㌣N＿の，が（1v＿旬，κ＊（N＿めは  これに着目すれば

  （10）式において，α［・］−0とおじ・た式，  α −0・ゴー1・…・N一た   （18）

  を変形したもので，この評価，すなわち，残り  とおいたとき，

霊：適顯｛叢ご1ヒ1㌦一慧∵一力）＋θ（㍑2

による微係数は，

  ∂允（〃）／∂μ（∫）＝φ・一伺∂      （13）   が与えられた場合に

であることとを舗すれば（・・）式を斑・（為）に α・一α夙…・N一相  （2°）

よって微分することにより得られることになり， み一・     （21）

 ∂恥 ／∂欝・（ゐ）＿＿2γ・（N＿ヵ）｛μ・（〃）       を得る方法について提案していたが，以下におい   ＿β・（』V＿旬澱（ゐ）＿θ・（2V＿ゐ）｝β・ （N＿〃）    て，あらためて証明付で述べる。

  ＋2P＊（N一ゐ）席o（ゐ）十2L＊ （1V−〃）  （14）    3． 逐次近似評価法の証明

となる。すなわち・（7）式により髭゜（カ）は・が（の   まず，（18）（19）式が与えられたとすれば，

の関数としてあらわされているが・Kuh距Tuck i8）（・・）式の繰返し関係に（・8）式を代入して

・・の条件より・・奪㈲は固定して導びいてよい 得られる曙以後の近似評価

鑑謬鷲慧書選蕊；こあ 輪一ぱ（脚噸力） （22）

ときは，（、3）式の第頂，したがって，（・2）式 に対して・畷から −1段までの畷過程の

α［β・（N一丘）轟）＋θ・（ル〃）］の値は，（・・）式 れていることを意味している・つぎに，

の定義によれば，◎であるが，実際には，0から    α［・8（N一旬工（明

1（または，0から一1）の任意の値でよい。   （θ（」V一鳶）は，（18）式のもとでは0）の値によ

125

って，（2◎）（21）式を得ることができることを証  ができる。すなわち，

明しよう。       β（2V一ノ）允（戊）十θGV一ノ）＝1

 G）α［8（ハ「一々）淘（初＝0のとき。この場合   （または，βσV一ノ）灘（ノ）＋θ（N一ノ）＝−1）

は，αぽ一〇とおいていたから，何の変更もな  の状態では，他の操作量とは無関係にα相の値

には，砕．々を0から1に変化させる必要があ  と書くことにすれば，ακ． ，ゼー1，…，〃−1を固 るがそれにともなって，残り2V一為段近似評価  定したまま，

が，（8）（10）式よりあきらかに，         αN．々＝⇒．鳶＋ε，ε＞0，     （25）

 κ （旬P＊σV 旬工（助      とおけば，仮定により

→灘 ﾖP＊（N一顕 ）      輪、≒α［β（N一鋤ω＋θ（N一ノ）］（26）

刊α祠γ（2v−〃）（s嬉n（α。．∂一β（N一為）κ（烏））2

      であるから，みコ≒0である。しかし，

       （23）

      ．8（2V一ノ）斑（ノ）＋θ（N一ノ）はαぽの連続関数で と変化するから，いままでの近似評価に対する最  あるから，（25）式のα脳烏に対して

三竺蕊；鷲㌶織㌶β（ハr一ノ）允（ゾ）十θ（∧↑一ノ）＝1（または一1）＋δ（ε）       （27）

合を想定すれば，晦4が1に到達するまで，

      1inδ（の一〇      （28）

 α［β（2V一ノ）灘（ノ）十θ（1V−」）］，ノ＝1，…，カー1     ε→o

       （24）   であるから，εを充分小さく選ぶことにより，

の値が変化しなけれぱぴ◎を得る．一般に， αwの値の変化の影響を臆四・さくでき・し

α ．、の変化に対して，α｛β（1V−〃）κ（鳶）］の値  たがって・充分小さなεに対して は変化しない。なぜなら，もし，変化すると仮   砲一テα［刀（2v−」）允（ノ）＋θ（N ノ）］

定すれば，ある αル、に対して，最初の関係   と変化させれば，」村一〇の関係を保つことがで 丑（N一めκ（ゑ）＞1カミβ（ハ↑一ゐ）漏（旬一1となるこ  きることがわかる。また碗一為を◎から1まで とになる。（14）式の説明において述べたように，  変化させる間に・1回以上および同時に2個以上 0段から為一1段まで最適関係が成立している状  の□1≦ヌ≦是一駕について・β（2v一ノ）κ（ノ）＋

態では，B（2V一めMの一1ならば，0からカー−1  θ（N一ノ）の値が1（または一1）を切る場合に 段までの操作量に，砺．鳶は何の影響も与えない  も，各」に対して・その都度同様の操作をほど

αN．花の最適値は，この場合はつねに1である。   （iii）α［β（1V− ）w（ ）］一一1のとき。この場 つぎに，α祈鳶を◎から1に変化させるとき，  合は，（ii）の場合において・碗一・の値を0から

（24）式の少くとも1個以上のノについて値が変  一1まで変化させる以外は（ii）とまったく同様 化すると仮定しよう。すなわち，あるノについ  である。

て，最初にβ（1V一ノ）κ（ノ）＋θ（2V−−」）が1（また   さて，ある蹄一・に対して，β（2V一ノ）灘（ノ）＋

は一1）を切る（必ず 切る ということにっい  θ（1V一ノ）の値が1となったとき，この値が必ず

ては，後述する）とすれば，そのときの砺鴫の  1を切ることについて示せば，収束の証明が完成

から〃一一1段までの最適関係九．、＝0を保つこと   α ＝0，〆＝1，…，1V−〃＋1    （29）

126

と仮定することは，残りN一為＋1段評価を，   で変化させることを考えれば，

  部 （〃＋1）P＊（N一屏了）躍（鳶＋1）         ／㌫→／〜㌫＋δ／示：   （3γ）

と近似することであるから・評価は・       と変化したとき，躍（ノ）の変分を勘（ノ）と書けば，

 み＋1＝〃ほ＋1）P＊（1V一ゐ＋1）M〃十1）      （旦4）式より，αN．ヵ≧0を考慮して，

   ゑキエ

  ＋Σ｛灘 （ノ）ρκ（ノ）＋λ（〃（プー1））2｝ （30）   δ （ゐ）

となる∴旗      一δ〆㌫一δ／㌫卜（1／α競）｛§砺・（ノ）

吉三慧罐；允（ゐ） （31） ＋毎｝］＋（ト／㌫）卜（・侮）§醐ノ）］

      （38）

と近似すれば，（3◎）式は，

酬α・一・1γ（1v−〃）｛、ign（αば    となり，さらにδ （り・ゴ＝q ・ −Lは・（33）

      式より，形式的に，

  一β（1v一の灘（為））2暢 （〃）P＊（N一ゐ）斑（為）

  噺〆⑭躍（ノ）＋λ（・（月））つ（32） δ・の一d・a脚）］・［（一㈲隠醐ノ）

となり・（23）式と剛近似織を得ることカ・わ  ＋・W）｝｝∫一砥…・丘一L（39）

かる（（32）式の第2項までが，残り1V一力段の

方程式として（4）式の形で表現すれば，文献〔1〕

と同様にして，      と書くことができるから・（39＞式の解は・形式       的に

・（の一・at［（一・／・・）｛，具、仇・・（プ）  ㌻δ。（。）］

      ニ        

  袖＋砺・（カ）｝1鳳…・為一・（33） Lδ。（鳶一・）二

の近似評価に対する髄解が得られているという        （42）

 （1／αガ）Σ角μ（」）抽，＋αほ況（の

   ＝β（N一りw（τ）十θ（1V−∫）全ω（∫） （36）      ．．

なる関係で紺ればならない．つ甑輪、の ＋D・at回α≡㌔ 三D・at［ω］

       ：      ㌔ ζ7克＿2丘＿1

単調な変化悶して・姻も単調姪化をする   σ脚。輪、∴◎

       （43）ことを示す。簡単のため，、α ．．為を0から1ま

ぱ

となる。これを（38）式に代入すれば，      おいて

懐霊蹴㌔副ω（卿  ω（も）（（△《・㎞）隠｝（ノ）

D・at［ω㈲一1（・一ω（〃））δ／㌫（39）  ＋ぴ＋α嬢・（ゐ）｝）

 α々一［αo々… α鳶＿1々P＝［αヵo…・α姑＿1］      （40）      ＝1      （44）

となる。あきらかに（39）式の分母は正であり・  となるとする（ω（ち）一一1となる場合も同様）。

ω（ん）（一β（1V−〃）κ（ ））は・前述のように0≦  簡単のため，αぷくα輻舟となるα ．．たに対して 鞠づ≦1を満足する碗．滝に対して，1を切るこ  は，

とはないからL互子も定符号である・よって・  ωω＜・     （45）

（39）式は／輪の一醸化悶して・δ姻であると仮定しておく．（33）式から（39）式を が単調に変化すること蛎している・いま・㍗導びいたの胴膀妨で（33）式の輪求め

を0から1へ連続的に変化させた場合，あるκ。，

       れば，

0≦ち≦カー1，に対して，最初に，砕．。＝α寿一、に

匡：1∵一回一回1：ピ1∵＋「li：：：∵㈲

と書くことができるから，（46）式を（幽）式のω（∫。）の式に代入すれば，

 ω（∫。）＝∫（dsat［ω（の］，∫＝・0，…，為〜1）＋9（dsat｛ω（∫）］，∫＝0，…，々−1）〃（ゐ）

    ＋（一1／α嫡）｛ぶ…α［ω（ ）］｝        （47）

一一… 一一…8…駒僻）一回

劇岨L坤…・一㎞）｛㌦…‖…㌫1ぴ一回［馴㈲

となる。（47）〜（49）式からあきらかなように，   一一

dsat【ω（り］（＝dsat［刀（1V−∫）エ＠）＋θ（N一ξ）D，  で1を切らないとすれば，∫（・），9（・）の値が一定 ゴ＝0，…，〃−1，の値が変化しない限り，∫（・）9（・）  であり，α ．尾の増大とともに，やはり単調に変 の値は変化せず，α｛ω⑦1，∫一◎，…，カー1も変化  化するはずであるから，ω（紛が1を切らないと しない。このような場合には，（47）式はμ（〃）の  いう仮定に矛盾する。よって，砺輔を0から単 線形関数であり，吟づとともにμ（幼が単調に  調に増大していくとき，最初に1（または一一1）に 変化するから，ω（∫。）もαN．ヵとともに単調に変  到達するω（∫。），1≦ 。≦〃−1，は必ず1（または 化することがわかる。仮定により，αル，〈α翫、  −1）を切ることがわかる。証明終り。

に対しては，ωσ，）は1より小で，αぽの増大と   以上の収束の証明からあきらかなように，例え ともに1に到達するから，もちろん9（・）≒0で  ば，β（1V−〃）允（〃）＞1のときには，αN−・を」ぽ ある。（47）式の第3項がα［ω（も）］を含まない  一〇を満足させつつ1に到達させればよいから，

ことに注意して，もし，ω（召0）の値が鋤．戸麟．、，  具体的な計算アルゴリズムとしては，つぎのよう

128

にすればよい。      が得られることから，有限回でみ．、一◎を得るこ  αM＝0に対して・み一・＝0が得られている状  とがわかる。すなわち，有限回で（i）の状態にな 態を，αL．、．…α矩＝，と書くことにすれば，    るから，この過程を通る繰返し番号を

（a）α・一・＝1とおき，』°が得られるか  1＜∫、＜…＜∫。〈・・．  （58）

どうか調べる。すなわち，碗．鳶一1とすれぽ   とおけば，

㌫㌫㍊㌶㌘讃㌔ α編く臨ぐ一くα誌〈…（59）

1≦r≦〃−1，に対して，α［ωσ）］の値が変化し  となり・最終的に

た場合，それらの値をα輻、，…，α輻肩、，と書く    αム＝1      （60）

ことにすれば，これらの値が」已一〇を与える解  となることがわかる。すなわち，文献〔1〕の計 であれば，やはり」』−0の収束を得る。      算アルゴリズムの収束が証明された。

 （b） （a）のようにαぷ＝1に対して」桓＝0

の解が得られない場合には，初回のみ，       4 む  す  び

  α撫＿◎，αム、、＿1         （5◎）    制限付操作量線形系の二次評価に対する最適制 とおき，一般に       御問題の数値解法としては，種々の勾配法2）3＞が   嶋一（αLi。＋αも。、）／2  （51） 適用されまたは適嗣能であるカ㍉ここで示し       た逐次近似評価法の特長は，解が

として，（a）の場合と同様にして，み。1＝0が得

られるかどうか柵べる。そして，    μ（ゐ）＝sat［β（N喝工（々）＋θ（N一為）］

（i）ふ⇒が得られた場合。       （61）

  嬬一嶋，端司   （52） の形の帰還形で与え猟勾配部よる方法のよ

  α温一αよ・uα㌫一α粍   （53） れる。

とおいて，（51）式にもどる。この操作により

      参 考 文 献   αも抽くα慧。＜α急。．     （54）

および      1）の熱鷲罐莫㌶豊鰹讐繁

  αLln＜α吉＿力くαLax       （55）     2） Kishi・民H・：◎n Line C◎mp磁er Co磁mI       Techniques and Their Application to Re−entry   （麟一が初めて・ω（∫o），1≦∫o≦〃−1，が1を    Aemspace Veh輌cle Cont，◎1． Advanc￠s輌n C◇滋．

  切るαN一鳶の値）       「01Systems・C・T・Le皿des（ed）， Academic が保証されるから・」⊇返し後   3）P簑灘9∵L、Th。 G，。d｛。。， p，。j。，ti。n M←

  1α㌍仁一αカ＿々｜＜1／2z榊1        （56）      thod for Non−1inear Pmgramming， Part I一

なる関係がなりたち，嚇当に大きくなれぱ ㌫蒜砿⊇S巡」° い一ぷ／

  α鱗一α差．、＋ε      （57）