楕円体法のソースを表示

'''楕円体法'''（だえんたいほう、{{Lang-en-short|ellipsoid method}}）とは[[数理最適化]]において[[凸集合]]内での[[凸関数]][[凸最適化|最小化]]問題に対する[[反復法]]の一種である。楕円体法では各反復において[[楕円体]]を以前の反復より体積が小さくなるように生成し、[[凸関数]]の最小解集合を求める。

楕円体は有理数の入力データによる[[線形計画問題]]に対する多項式時間で解く[[アルゴリズム]]となる。

== 歴史 ==
楕円体法には長い歴史が存在する。楕円体法は[[反復法 (数値計算)|反復法]]として{{仮リンク|ナウム・ショール|en|Naum Z. Shor}}によって始めて提案された。1972年には実数の[[凸最適化|凸最小化]]問題に対する近似アルゴリズムとして{{仮リンク|アルカディ・ネミロフスキ|en|Arkadi Nemirovski}}とデビッド・B・ユーディンによって研究されていた。

有理数入力データの線形計画問題に対する楕円体法としては{{仮リンク|レオニード・カチヤン|en|Leonid Khachiyan}}によって多項式時間で解くアルゴリズムとして提案・証明された。当時まで主に研究されていた[[単体法]]に関しては実用上では高速に動く解法であったが、理論的には指数時間アルゴリズムであったため、理論的に重要な成果であった。このことから、任意の入力に対して多項式時間を保証する楕円体の登場は大きな影響を与えた。

多項式時間を保証する線形計画問題に対するアルゴリズムがカチヤンの研究によって初めて示された。しかしながら実用上における楕円体法は計算速度が遅く、研究者の関心は低かった。にもかかわらず、後の線形計画問題に関する研究に大きな影響を与え、より実用的で多項式時間を保証する解法の提案につながった。特に初の多項式時間を保証する線形計画問題に対する[[内点法]]の[[カーマーカー法]]は実用上も楕円体法よりも高速で実行し、最悪時間計算量も楕円体法よりも勝る。

楕円体法は最悪時において制約の行数に依らず問題の次元・サイズにのみ依存する[[計算量]]を持つことから、[[組合せ最適化]]理論において重要な役割を長年果たしてきた<ref name=":1">{{citation |last1=Grötschel |first1=Martin |author1-link=:en:Martin Grötschel |last2=Lovász |first2=László |author2-link=ラースロー・ロヴァース |last3=Schrijver |first3=Alexander |author3-link=:en:Alexander Schrijver |doi=10.1007/978-3-642-78240-4 |edition=2nd |isbn=978-3-642-78242-8 |mr=1261419 |publisher=Springer-Verlag, Berlin |series=Algorithms and Combinatorics |title=Geometric algorithms and combinatorial optimization |url=https://books.google.com/books?id=hWvmCAAAQBAJ&pg=PA281 |volume=2 |year=1993 }}</ref><ref>[[:en:Lovász|L. Lovász]]: ''An Algorithmic Theory of Numbers, Graphs, and Convexity'', CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986.</ref><ref>V. Chandru and  M.R.Rao, Linear Programming, Chapter 31 in  ''Algorithms and Theory of Computation Handbook'', edited by [[:en:Mikhail Atallah|M. J. Atallah]], CRC Press 1999, 31-1 to 31-37.</ref><ref>V. Chandru and  M.R.Rao, Integer Programming, Chapter 32 in '' Algorithms and Theory of Computation Handbook'', edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45.</ref>。21世紀になり楕円体法と同様の計算量を持つ内点法も登場するようになった{{Citation needed|date=2013-04}}。

== 説明 ==
{{main|凸最適化}}
凸最適化問題は以下の式から構成される。
* [[凸関数]] <math>f_0(x): \mathbb{R}^n \to \mathbb{R}</math>,（''n''個の変数をもつ）ベクトル ''<math>x</math>'' において <math>f_0(x)</math> を最小化する。
* 凸の不等式制約 <math>f_i(x) \leqslant 0</math>, ただし、関数 <math>f_i</math> は凸である; これらの制約は[[凸集合]] ''<math>Q</math>'' を構成する。
* 線型の等式制約 <math>h_i(x) = 0</math>.

初期の[[楕円体]] <math>\mathcal{E}^{(0)} \subset \mathbb{R}^n</math> を

:<math>\mathcal{E}^{(0)} = \left \{z \in \mathbb{R}^n \ : \ (z - x_0)^T P_{(0)}^{-1} (z-x_0) \leqslant 1   \right \}</math>

と最小解 <math>x^*</math> が含まれるように定義する。ただし、<math>P_{(0)} \succ 0</math>とし、<math>x_0</math> は楕円体 <math>\mathcal{E}</math> の中心とする。

最後に凸集合 ''<math>Q</math>'' に対する{{仮リンク|分離オラクル|en|separation oracle}}の存在性について説明する。
点 <math>x\in  \mathbb{R}^n</math>が与えられたとして、オラクルは二つの回答のうち一つを返す:<ref name=":0">{{Cite web |title=MIT 6.854 Spring 2016 Lecture 12: From Separation to Optimization and Back; Ellipsoid Method - YouTube|url=https://www.youtube.com/watch?v=qWpYtfXeEn8 |archive-url=https://ghostarchive.org/varchive/youtube/20211222/qWpYtfXeEn8 |archive-date=2021-12-22 |url-status=live |access-date=2021-01-03 |website=www.youtube.com |date=2016-03-18 }}{{cbignore}}</ref>

* 点 <math>x</math> が <math>Q</math> に含まれる、あるいは -
* 点 <math>x</math> が <math>Q</math> に含まれない、加えて点 <math>x</math> と実行可能集合 <math>Q</math> を分離する超平面が存在する"、すなわちベクトル <math>c</math> によって任意の <math>y\in Q</math> に対して <math>c\cdot x < c\cdot y </math> を満たす。楕円体法は各反復ごとに以下のどちらかを出力する:

* 点は多面体 ''<math>Q</math>''（実行可能な点）に含まれる、あるいは -
* ''<math>Q</math>'' は空である.

不等式制約付き最小化問題の実行可能点において目的関数が常にゼロをとるとき、この問題は単に実行可能解を見つける問題と等価である。線形計画問題は線形の許容性判定問題に書き換えることができる（意味としては目的関数がゼロで制約条件に不等式あるいは等式の制約が存在する問題である。）。書き換える方法として線形計画問題の主問題と双対問題を組み合わせて一つの問題として扱う方法が挙げられる。 これは主実行可能解と双対実行可能解には[[弱双対性]]が成り立っていることから、主実行可能解における目的関数値と双対実行可能解における目的関数値の差が0以上であるという制約を新たに加える<ref name=":3">{{Cite book |last=Matoušek |first=Jiří |title=Understanding and using linear programming |last2=Gärtner |first2=Bernd |date=2007 |publisher=Springer |isbn=978-3-540-30697-9 |series=Universitext |location=Berlin; New York |pages=}}</ref>{{rp|84}}。もう一つの方法としては線形計画問題の目的関数を新たな制約として扱い、二分探索によって最適値を見つける方法が挙げられる<ref name=":3" />{{rp|7–8}}。

== 無制約最適化問題 ==
''k''番目の反復における楕円体を説明する。ここで楕円体の中心を <math>x^{(k)}</math> とする。

:<math>\mathcal{E}^{(k)} = \left \{x \in \mathbb{R}^n \ : \ \left (x-x^{(k)} \right )^T P_{(k)}^{-1} \left (x-x^{(k)} \right ) \leqslant 1   \right \}.</math>

ここで分離オラクルによってベクトル <math>g^{(k+1)} \in \mathbb{R}^n</math> を得る。すなわち、

:<math>g^{(k+1)T} \left (x^* - x^{(k)} \right ) \leqslant 0.</math>

このことから最小解は反復を通じて以下の通りに含まれなければならない:

:<math>x^* \in \mathcal{E}^{(k)} \cap \left \{z \ : \ g^{(k+1)T} \left (z - x^{(k)} \right ) \leqslant 0 \right \}.</math>

新たな楕円体 <math>\mathcal{E}^{(k+1)}</math> は現在の半楕円体を含む最小体積の楕円体となり、新たな楕円体の中心 <math>x^{(k+1)}</math> を求める。更新式は以下のように与えられる:

:<math>\begin{align}
x^{(k+1)} &= x^{(k)} - \frac{1}{n+1} P_{(k)} \tilde{g}^{(k+1)} \\
P_{(k+1)} &= \frac{n^2}{n^2-1} \left(P_{(k)} - \frac{2}{n+1} P_{(k)} \tilde{g}^{(k+1)} \tilde{g}^{(k+1)T} P_{(k)} \right ) 
\end{align}</math>

ただし、

:<math>\tilde{g}^{(k+1)} = \left (\frac{1}{\sqrt{g^{(k+1)T} P_{(k)} g^{(k+1)}}} \right )g^{(k+1)}</math>

である。楕円体法は以下の停止基準を満たせば終了する:

:<math>\sqrt{g^{(k)T}P_{(k)}g^{(k)}} \leqslant \epsilon \quad  \Rightarrow \quad f (x^{(k)} ) - f \left(x^* \right ) \leqslant \epsilon.</math>

== 不等式制約付き最適化問題 ==
制約付き最適化問題に対する''k''番目の反復における楕円体法について説明する。点 <math>x^{(k)}</math>は楕円体 <math>\mathcal{E}^{(k)}</math> の中心であると仮定する。また反復を通じて得られた実行可能解で最良の目的関数値を記録し、このリストを <math>f_{\rm{best}}^{(k)}</math> とする。点 <math>x^{(k)}</math> が実行可能な点であるかでないかによって以下のどちらかの手続きを行う:

*もし <math>x^{(k)}</math> が実行可能であるならば、無制約最適化問題と同様に劣勾配 <math>g_0</math> が以下の性質を満たすように更新する:

::<math>g_0^T  (x^*-x^{(k)}  ) + f_0 (x^{(k)}  ) - f_{\rm{best}}^{(k)} \leqslant 0</math>

*もし <math>x^{(k)}</math> が実行不可能であり''j''番目の制約について違反しているならば、実行可能性カット{{Efn|{{Lang-en-short|feasibility cut}} }}を用いて楕円体を更新する。実行可能性カットは <math>f_j</math> の劣勾配 <math>g_j</math> が任意の実行可能解 ''z'' に対して以下の性質を満たさなければならない:

::<math>g_j^T  (z-x^{(k)} ) + f_j (x^{(k)}  )\leqslant 0</math>

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
* Dmitris Alevras and Manfred W. Padberg, ''Linear Optimization and Extensions: Problems and Extensions'', Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
* V. Chandru and  M.R.Rao, Linear Programming, Chapter 31 in  ''Algorithms and Theory of Computation Handbook'', edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37.
* V. Chandru and  M.R.Rao, Integer Programming, Chapter 32 in '' Algorithms and Theory of Computation Handbook'', edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45.
* [[ジョージ・ダンツィーグ]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.
* [[ジョージ・ダンツィーグ]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.
* [[ラースロー・ロヴァース]]: ''An Algorithmic Theory of Numbers, Graphs, and Convexity'', CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986
* Kattta G. Murty, ''Linear Programming'', Wiley, 1983.
* [[:en:Manfred W. Padberg|M. Padberg]], ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.
* [[クリストス・パパディミトリウ]] and Kenneth Steiglitz, ''Combinatorial Optimization: Algorithms and Complexity'', Corrected republication with a new preface, Dover.
* [[:en:Alexander Schrijver|Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, {{ISBN|0-471-98232-6}}

== 関連解法 ==
* <!-- {{仮リンク|center-of-gravity法|en|center-of-gravity method}} -->
* [[内点法]] - 凸最適化問題に対する多項式時間アルゴリズム。楕円体法よりも優れた性能を有する。

== 外部リンク ==
* [http://www.stanford.edu/class/ee364b/ EE364b], a Stanford course homepage

{{最適化アルゴリズム}}

{{DEFAULTSORT:たえんたいほう}}
[[Category:組合せ最適化]]
[[Category:凸最適化]]
[[Category:線型計画法]]
[[Category:数学に関する記事]]