楕円体法とは何？わかりやすく解説 Weblio辞書

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

楕円体法

概要

　楕円体法(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事典」の他の用語

線形計画：

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

ウィキペディア

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

楕円体法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/28 02:08 UTC 版)

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

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

歴史

楕円体法には長い歴史が存在する。楕円体法は反復法としてナウム・ショール（英語版）によって始めて提案された。1972年には実数の凸最小化問題に対する近似アルゴリズムとしてアルカディ・ネミロフスキ（英語版）とデビッド・B・ユーディンによって研究されていた。

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

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

楕円体法は最悪時において制約の行数に依らず問題の次元・サイズにのみ依存する計算量を持つことから、組合せ最適化理論において重要な役割を長年果たしてきた^[1]^[2]^[3]^[4]。21世紀になり楕円体法と同様の計算量を持つ内点法も登場するようになった^[要出典]。

説明

→詳細は「凸最適化」を参照

凸最適化問題は以下の式から構成される。

凸関数 $f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R}$

非線形(制約付き)

一般	バリア関数ペナルティ関数法
微分可能	ラグランジュの未定乗数法逐次二次計画法逐次線形計画法

凸最適化

凸縮小化

線型および
二次

内点法	アフィンスケーリング法（英語版）カーマーカーの射影変換法メロートラの予測子修正子法（英語版）
基底-交換	単体法改訂単体法十文字法レムケの相補掃き出し法
その他	カチヤンの楕円体法有効制約法

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ブルーフカ法クラスカル法プリム法
最短経路問題	ベルマン–フォード法ダイクストラ法ワーシャル–フロイド法ジョンソン法（英語版）

ネットワークフロー
(最大流問題)

Dinic法（英語版）
エドモンズ・カープ
フォード・ファルカーソン
プッシュリラベル最大流アルゴリズム（英語版）

メタヒューリスティクス

カテゴリ（最適化 • アルゴリズム） • ソフトウェア

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

楕円体法

概要

詳説

楕円体法

歴史

説明

「楕円体法」の関連用語


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの楕円体法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

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

楕円体法

概要

詳説

楕円体法

歴史

説明

「楕円体法」の関連用語

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