2026-03-12T08:19:45Z https://ir.soken.ac.jp/oai

oai:ir.soken.ac.jp:00000717 2023-06-20T14:50:44Z 2:429:17

線形計画問題に対するアフィンスケーリング法の収束に関する理論的解析 Convergence Analysis of Affine Scaling Method for Linear Programming 村松, 正和 ムラマツ, マサカズ MURAMATSU, Masakazu 線型計画問題は最も基本的な最適化問題であり,本論文の主要なテーマであるアフィ<br />ンスケーリング法は,1967年にDikinによって提案された最初の線型計画問題にたい<br />する内点法である｡アフィンスケーリング法は非常に単純な内点法であり,実用的にも<br />すぐれた解法であることが数値的に確かめられているが,一方,逆に単純であるがため<br />に大域的収束の証明が困難とされてきた｡本論文ではアフィンスケーリング法の実用性<br />を常に視界に入れ,<br />●アフィンスケーリング法のロング･ステップサイズにおける大域的収束<br />●アフィンスケーリング法の非許容解を出発点とする方法への拡張<br />を大きな2つのテーマとしている｡<br />　内点法は一般に許容領域の内点が初期値として与えられ,そこから許容領域の内部を<br />通って最適解へ近づく｡多くの計算機実験から,アフィンスケーリング法は毎回次の点<br />を制約領域の境界までのある比率(例えば,0.99)だけ進んだところにとるようにする<br />と非常に性能がよいことが明らかにされている｡<br />　このような"次の点の取り方"をロング･ステップサイズとよぶ｡<br />ところが理論的にはそのようなロング･ステップサイズにおけるアフィンスケーリン<br />グ法の大域的収束は未解決の問題であった｡特に退化とよばれる現象が起こると,アフ<br />ィンスケーリング法の大域的収束の証明が難しくなることが知られている｡"退化して<br />いない"という仮定(非退化仮定)をおいて証明をした論文は数多いが,この退化は実<br />際の線型計画問題ではよく起きる現象であるので,実用上はそれらは重要な意味を持ち<br />えない｡実用という見地から本論文では決して非退化を仮定しない｡<br />　Ⅱ章では(1)の結果を元にして,比率を3分の2以下に取ればアフィンスケーリ<br />ング法は収束することを証明する｡これは現在までに得られている最良の結果である｡<br />また同じステップサイズで,双対推定と呼ばれる量が双対問題の最適解に収束すること<br />も証明する｡これはアフィンスケーリング法によって,主問題と双対問題が同時に<br />解かれることを意味する｡主問題の最適値と双対問題の最適値は等しい(双対定理)の<br />で,この性質はある種の停止条件として使うことができる｡<br />　証明には土谷が主退化仮定を取り除く際に開発した局所Karmarkarポテンシャル関<br />数を活用する｡この関数は厳密に評価する不等式を得たことが証明の成功につながった｡<br />　Ⅲ章においてはⅡ章の結果を応用し,Karmarkarの射影スケーリング法のロング･ス<br />テップサイズの変種を考える｡この章の結果は(2)による｡ここで提案するアルゴリ<br />ズムは本質的に同次形線型計画問題に対するアフィンスケーリング法と同等であるので,<br />上の結果を容易に適用できる｡さらに問題の特殊性を考慮してKarmarkarポテンシャ<br />ル関数をより厳しく評価し,ステップサイズを3分の2より小さく取れば○(nL)<br />(ただし,nは変数の数,Lは問題のサイズ),3分の2ちようどにとれば<br />○(n2 L)の反復回数で最適解を得られることが証明される｡さらに双対推定の収<br />束や,局所的収束率といった性質についても証明を得ている｡<br />　ここで扱われる同次形線型計画問題は最適値が0であることがあらかじめわかってい<br />ると仮定されている｡(この仮定はそれほど不合理なものではなく,一般に解消できる<br />ことが知られている｡)Ⅲ章のおわりで,この条件がよりゆるい"最適値の下界が知ら<br />れている″という条件に置き換えることができ,多項式性に関する定理が同様に成立す<br />ることを示す｡このような条件の緩和のアイデアはToddとBurrellの仕事による｡<br />　最後にⅣ章ではアフィンスケーリング法を許容領域以外の点から出発できるような改<br />良について論づる｡この章の結果は(3)による｡<br />　冒頭にも述べたように内点法は一般に制約領域の内点が与えられていると仮定して,<br />そこからアルゴリズムを始める｡しかし実際の多くの線型計画問題では,許容内点が存<br />在するか否か,あるいはそもそも許容解が存在するか否かが明らかでない｡それを明ら<br />かにするには別の線型計画問題をひとつ解くくらいの手間がかかることが知られている｡<br />従って,内点法を許容解以外の点から始められるように拡張することは重要な課題であ<br />る｡すでに多くの内点法について,このような拡張が提案され,また理論的にも解析さ<br />れている｡アフィンスケーリング法も例外でなく,DikinやAndersensenによってい<br />ろいろな拡張の仕方が提案されているが,やはり大域的収束の証明は困難であり,今ま<br />では計算機実験の結果のみが残されていた｡<br />　これに対し,本論文ではアフィンスケーリング法の新しい拡張版を提案するだけでな<br />く,この大域的収束の証明を与える｡すなわち,もし解こうとする線型計画問題に最適<br />解が存在すれば,点列はそのひとつに収束し,また双対推定は双対問題の最適解に収束<br />する｡<br />　このような拡張を考えると,一般の(内点許容解から始まる)内点法とは異なった場<br />合,すなわち許容解がなかったり,内点許容解がなかったりする場合が考えられる｡本<br />論文ではこれらの場合についても点列の挙動を解析し,アルゴリズムとして意味のある<br />結果が得られることを証明している｡既に述べたように,これらの証明はすべて非退化<br />仮定なしで証明してある｡ application/pdf 総研大甲第67号 eng thesis https://ir.soken.ac.jp/records/717 博士（学術） 1994-03-24 総合研究大学院大学 https://ir.soken.ac.jp/record/717/files/甲67_要旨.pdf application/pdf 345.8 kB 2016-02-17 https://ir.soken.ac.jp/record/717/files/甲67_本文.pdf application/pdf 3.1 MB 2016-02-17