楕円体法とは？わかりやすく解説

辞書 類語・対義語辞典 英和・和英辞典 日中中日辞典 日韓韓日辞典 古語辞典

その他の辞書▼
- 手話辞典
- インドネシア語辞典
- タイ語辞典
- ベトナム語辞典

Weblio 辞書ヘルプ

556の専門辞書や国語辞典百科事典から一度に検索!

無料の翻訳ならWeblio翻訳！

初めての方へ参加元一覧

Weblio 辞書 > 学問 > OR事典 > 楕円体法の意味・解説

索引トップ用語の索引ランキングカテゴリー

楕円体法

読み方：だえんたいほう
【英】：ellipsoid method

概要

　楕円体法(ellipsoid method) は, 微分不可能な凸計画問題に対する解法として, 1976年にユーディンとネミロフスキー(Yudin-Nemirovskii) によって提案された. その後 1979年にカチヤン(L. G. Khachiyan)は, 楕円体法が線形計画問題に対する多項式時間解法に成り得ることを示した. この結果は, 長年にわたって未解決のままであった,「線形計画問題を多項式時間で解くことが出来るか?」という計算複雑度に関する問題への肯定的な答を与えるものであり, 数理計画の分野に衝撃をもたらした. 線形計画法に対する解法としての楕円体法は, 実用の面からは単体法などに比べて効率が悪く, また理論的な計算量の面からも, 1984年以降に現れた内点法に劣っていることが分かっている. しかしながら, 線形, 非線形, 組合せなどの最適化問題に対し, 様々な理論的な結果を残している. 「 $n$ 次元空間における楕円体を用いた 2分探索」のような解法である.

詳説

　楕円体法を説明するために, 与えられた多面体 $P = \{x \in \mathbf{R}^n \mid a_i^{\top} x \leq b_i\ (i = 1, 2, \cdots, m)\}$ が空であるか否かを判定し, また空でなければ $P\,$ に含まれる点を求める, という非空性問題について考える. なお, $P\,$ の上での線形関数 $c^{\top} x$ の最大化問題を解くには, $\{x \in P \mid c^{\top} x \leq \gamma\}$ という多面体に対する非空性問題を繰り返し解き, $\gamma \in \mathbf{R}$ に関する 2分探索を行えば良い.

　この問題に対し, 以下の2点を仮定する.

$\mbox{(i)} \quad P \subseteq \{x \in \mathbf{R}^n \mid \|x - x_0\| \leq R\}$ なる $x_0 \in \mathbf{R}^n$ 及び $R \in \mathbf{R}$ が既知である.

$\mbox{(ii)} \quad P\,$ が空でないならば, その体積は $\varepsilon (> 0)$ 以上である.

　楕円体法では, いわば「 $n\,$ 次元空間での楕円体を用いた 2分探索」を行うことにより, $P\,$ の点を求める. 各反復では, $P\,$ を含む楕円体 $E_k\,$ を常に保持する. 楕円体 $E_k\,$ は, 中心と呼ばれるベクトル $x_k \in \mathbf{R}^n$ 及び $n \times n$ 正定値対称行列 $B_k\,$ を用いて,

$E_k = \{x \in \mathbf{R}^n \mid (x - x_k)^{\top} B_k^{-1}(x - x_k) \leq 1\}$

と表される. なお, 上記の仮定 (i) より, $B_0 = R^2 I$ と選ぶことができる.

　各反復では, $x_k \in P\,$ が成り立つか否かを調べる. 成り立つ場合はアルゴリズムを停止する. 成り立たない場合は, $a_i^{\top} x_k > b_i$ なる $i\,$ が存在するので, そのような $i\,$ を見つける. 中心 $x_k\,$ を通る超平面 $a_i^{\top} x=a_i^{\top} x_k$ により, $E_k\,$ を半分にして得られる集合 $E_k' = \{x \in E_k \mid a_i^{\top} x \leq a_i^{\top} x_k\}$ に対し, これを含み, かつ体積が最小の楕円体を $E_{k+1}\,$ とおく. そのような楕円体 $E_{k+1}\,$ を表す $x_{k+1}\,$ 及び $B_{k+1}\,$ は次のようにして求められる:

$x_{k+1} = x_k - \frac{1}{n+1}d,\qquad B_{k+1} = \frac{n^2}{n^2 - 1}\left(B_k - \frac{2}{n+1}d d^{\top} \right).$

ここで, $d = (1/\sqrt{a_i^{\top}B_k a_i})B_k a_i$ である.

　上記のように $E_{k+1}\,$ を定めると, 楕円体の体積の比は,

$\frac{{\rm vol}(E_{k+1})}{{\rm vol}(E_{k})} = \left(\left(\frac{n}{n+1}\right)^{n+1} \left(\frac{n}{n-1}\right)^{n-1}\right)^{1/2} < e^{-1/(2n)} < 1$

となる. したがって, 楕円体の体積は線形空間の次元 $n\,$ のみに依存する一定の比率で減少していく. 反復回数 $k\,$ が十分大きくなり楕円体の体積が $\varepsilon$ 未満になったとすると, 仮定 (ii) により $P = \emptyset$ であることが分かるので, アルゴリズムを停止する. $P\,$ が多面体であることから, 仮定 (i), (ii) での $x_0\,$ , $R\,$ , $\varepsilon$ をうまく選ぶことができ, それにより多項式回の反復で終了することが導かれる.

　上記で述べた楕円体法の改良として,「深い」(deep)カットを用いた方法が提案されている. この方法では, 半楕円体 $E_k'\,$ の代わりに, より小さな集合 $\{x \in E_k \mid a_i^{\top} x \leq b_i\}$ に注目し, それを含む最小の楕円体 $E_{k+1}\,$ へと更新していく. この場合, 連続する 2つの楕円体の比は, $\alpha = (a_i^{\top} x_k - b_i)/\sqrt{a_i^{\top}B_k a_i}$ とおくと,

$\frac{{\rm vol}(E_{k+1})}{{\rm vol}(E_{k})} = \left(\left(\frac{n(1 - \alpha)}{n+1}\right)^{n+1} \left(\frac{n (1 + \alpha)}{n-1}\right)^{n-1}\right)^{1/2}$

と表され, また $0 \leq \alpha \leq 1$ なので, 元の楕円体法に比べて反復回数が減少することがわかる.

　さらに, 代用(surrogate)カット, 平行(parallel)カットを用いれば, 楕円体の体積比をより減少させることができる. また, 深いカットと全く逆の考え方により得られる「浅い」(shallow)カットを用いると, 連続する楕円体の体積比は逆に増加するが, 理論的には, 他のカットでは得られない興味深い結果を得ることができる. これらのカットについての詳細は参考文献を参照されたい.

　線形計画法に対する楕円体法の適用は, 線形計画のみならず組合せ最適化においても重要な結果を残している. その1つが, 最適化問題と分離問題の多項式時間に関する等価性であろう.

　 $P \subseteq \mathbf{R}^n$ を多面体とする. ただし, $P\,$ の不等式系による表現は必ずしも与えられていない, と仮定する. 分離問題とは, 任意のベクトル $x_* \in \mathbf{R}^n$ が与えられたとき, $x_* \in P$ か否かを判定し, $x_* \not\in P$ ならば $a^{\top} x \leq b$ $(\forall x \in P)$ かつ $a^{\top} x_* > b$ なる $a \in \mathbf{R}^n$ 及び $b \in \mathbf{R}$ を求める問題のことである. 上記で述べた楕円体法のアルゴリズムを見ると分かるが, 必ずしも $P\,$ の不等式表現が陽に与えられている必要はなく, 各反復において $P\,$ と $x_k\,$ に関する分離問題を多項式時間で解けるならば, 最適化問題もまた多項式時間で解くことができる. 一方, この逆もまた成り立つことが Grötschel-Lovász-Schrijver (1981) 及び Padberg-Rao (1981) によって証明されている.

　この他にも, 劣モジュラ関数の最小化やパーフェクトグラフでの最大安定集合問題などの組合せ最適化問題が多項式時間で解ける, という結果が, 楕円体法の適用により導かれている.

参考文献

[1] R. G. Bland, D. Goldfarb and M. J. Todd, "The ellipsoid method: a survey," Operations Research, 29(1981) 1039-1091.

[2] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1991.

[3] 伊理正夫,『線形計画法』, 共立出版, 1986.

[4] G. L. Nemhauser, A. H. G. Rinnooy Kan and M. J. Todd, eds., Optimization, Handbooks in Operations Research and Management Science Vol. 1, North-Holland, 1989. 伊理正夫, 今野浩, 刀根薫監訳,『最適化ハンドブック』,朝倉書店, 1995.

「OR事典」の他の用語

線形計画：

最適化問題最適解楕円体楕円体法目的関数相補性定理等質自己双対錐

エベレスト

転生したらスライムだった件

めざましどようび

手塚とおる

>> 「楕円体法」を含む用語の索引
楕円体法のページへのリンク

辞書ショートカット

1 OR事典

カテゴリ一覧

＋ビジネス

＋業界用語

＋コンピュータ

＋自動車・バイク

＋船

＋建築・不動産

＋ヘルスケア

＋スポーツ

＋辞書・百科事典

すべての辞書の索引

Weblioのサービス

「楕円体法」の関連用語

1

ロバース, ラスロー

50% |||||

2

ウィキペディア小見出し辞書

34% |||||

3

劣モジュラ最適化

16% |||||

4

その他のアルゴリズム

ウィキペディア小見出し辞書

14% |||||

5

ブロイデン法

百科事典

12% |||||

6

局所探索法の一覧

ウィキペディア小見出し辞書

12% |||||

7

線型計画法

百科事典

10% |||||

8

10% |||||

9

局所探索法

百科事典

10% |||||

10

百科事典

10% |||||

楕円体法のお隣キーワード

板取り問題

株価変動モデル

楕円体法

構造化モデリング

構造化問題

標準形ゲーム

検索ランキング

楕円体法のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.

ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問
 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典

ご利用にあたって

・Weblio辞書とは

・検索の仕方

・利用規約

・プライバシーポリシー

・サイトマップ

便利な機能

・ウェブリオのアプリ

・画像から探す

お問合せ・ご要望

・お問い合わせ

会社概要

・公式企業ページ

・会社情報

・採用情報

ウェブリオのサービス

・Weblio 辞書

・類語・対義語辞典

・英和辞典・和英辞典

・Weblio翻訳

・日中中日辞典

・日韓韓日辞典

・フランス語辞典

・インドネシア語辞典

・タイ語辞典

・ベトナム語辞典

・古語辞典

・手話辞典

・IT用語辞典バイナリ

・おすすめのプログラミングスクール情報「Livifun」

©2024 GRAS Group, Inc.RSS