楕円体法 - 版の履歴

Tamura: /* 詳説 */

2008-08-22T07:14:40Z

詳説

Tamura: /* 詳説 */

2008-08-22T07:13:17Z

詳説

Tamura: /* 概要 */

2008-08-22T07:11:39Z

概要

Tamura: 詳説の第１段落を概要に移した．旧概要は最後の一文以外削除．（ほぼ同様の文章を繰返していたため）

2008-08-22T07:08:05Z

詳説の第１段落を概要に移した．旧概要は最後の一文以外削除．（ほぼ同様の文章を繰返していたため）

Imahori: 基礎編と用語編のマージ

2008-03-13T13:38:48Z

基礎編と用語編のマージ

2007年8月8日 (水) 11:21にKanda.kによる

2007-08-08T11:21:31Z

Orsjwiki: "楕円体法" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T02:15:05Z

"楕円体法" を保護しました。 [edit=sysop:move=sysop]

2007年7月16日 (月) 08:37に122.17.2.240による

2007-07-16T08:37:38Z

2007年7月13日 (金) 05:08に122.17.2.240による

2007-07-13T05:08:30Z

2007年6月28日 (木) 08:31にOrsjwikiによる

2007-06-28T08:31:20Z

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

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

← 古い版		2008年8月22日 (金) 07:13時点における版
27行目:		27行目:
	と表される. なお, 上記の仮定 (i) より, <math>B_0 = R^2 I</math> と選ぶことができる.		と表される. なお, 上記の仮定 (i) より, <math>B_0 = R^2 I</math> と選ぶことができる.

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

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

@@ 2行目: / 2行目: @@
 === 概要 ===
-楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.
+　[[楕円体法]](ellipsoid method) は, 微分不可能な凸計画問題に対する解法として, 1976年にユーディンとネミロフスキー(Yudin-Nemirovskii) によって提案された.  その後1979年にカチヤン(L. G. Khachiyan)は, 楕円体法が線形計画問題に対する[[多項式時間解法]] に成り得ることを示した.  この結果は, 長年にわたって未解決のままであった,「線形計画問題を多項式時間で解くことが出来るか?」という計算複雑度に関する問題への肯定的な答を与えるものであり, 数理計画の分野に衝撃をもたらした.  線形計画法に対する解法としての楕円体法は, 実用の面からは単体法などに比べて効率が悪く, また理論的な計算量の面からも, 1984年以降に現れた内点法に劣っていることが分かっている. しかしながら, 線形, 非線形, 組合せなどの最適化問題に対し, 様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.
 === 詳説 ===
 　楕円体法を説明するために, 与えられた多面体 <math>P = \{x \in \mathbf{R}^n \mid a_i^{\top} x \leq b_i\ (i = 1, 2, \cdots, m)\}</math> が空であるか否かを判定し, また空でなければ <math>P\,</math> に含まれる点を求める, という非空性問題について考える. なお, <math>P\,</math> の上での線形関数 <math>c^{\top} x</math> の最大化問題を解くには, <math>\{x \in P \mid c^{\top} x \leq \gamma\}</math> という多面体に対する非空性問題を繰り返し解き, <math>\gamma \in \mathbf{R}</math> に関する2分探索を行えば良い.

@@ 1行目: / 1行目: @@
 '''【だえんたいほう (ellipsoid method)】'''
 楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.
-詳しくは[[《楕円体法》|基礎編：楕円体法]]を参照.
+=== 詳説 ===

← 古い版		2007年8月8日 (水) 11:21時点における版
2行目:		2行目:

	楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.		楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.
		+
		+	詳しくは[[《楕円体法》\|基礎編：楕円体法]]を参照.

← 古い版	2007年7月20日 (金) 02:15時点における版
(相違点なし)

← 古い版		2007年7月16日 (月) 08:37時点における版
1行目:		1行目:
	'''【だえんたいほう (ellipsoid method)】'''		'''【だえんたいほう (ellipsoid method)】'''

−	楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「$n$ 次元空間における楕円体を用いた2分探索」のような解法である.	+	楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.

← 古い版		2007年7月13日 (金) 05:08時点における版
1行目:		1行目:
	'''【だえんたいほう (ellipsoid method)】'''		'''【だえんたいほう (ellipsoid method)】'''

−	~~[[楕円体法]](ellipsoid method) は~~, ~~微分不可能な凸計画問題に対する解法として~~, ~~1976年にユーディンとネミロフスキー~~(Yudin-~~Nemirovskii~~) によって提案された. ~~その後1979年にカチヤン~~(~~L. G.~~ Khachiyan)は, ~~楕円体法が線形計画問題に対する[[多項式時間解法]] に成り得ることを示した~~. ~~この結果は~~, 長年にわたって未解決のままであった,「線形計画問題を多項式時間で解くことが出来るか?」という計算複雑度に関する問題への肯定的な答を与えるものであり, 数理計画の分野に衝撃をもたらした. 線形計画法に対する解法としての楕円体法は, 実用の面からは単体法などに比べて効率が悪く, また理論的な計算量の面からも, 1984年以降に現れた内点法に劣っていることが分かっている. しかしながら, 線形, 非線形, ~~組合せなどの最適化問題に対し, 様々な理論的な結果を残している~~.	+	楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「$n$ 次元空間における楕円体を用いた2分探索」のような解法である.
−
−	楕円体法を説明するために, 与えられた多面体 <math>P = \{x \in \mathbf{R}^n \mid a_i^{\top} x \leq b_i\ (i = 1, 2, \cdots, m)\}</math> が空であるか否かを判定し, また空でなければ <math>P\,</math> に含まれる点を求める, という非空性問題について考える. なお, <math>P\,</math> の上での線形関数 <math>c^{\top} x</math> の最大化問題を解くには, <math>\{x \in P \mid c^{\top} x \leq \gamma\}</math> という多面体に対する非空性問題を繰り返し解き, <math>\gamma \in \mathbf{R}</math> に関する2分探索を行えば良い.
−
−	~~この問題に対し, 以下の2点を仮定する.~~
−
−
−	~~:<math>\mbox{(i)} \quad P \subseteq \{x \in \mathbf{R}^n \mid \\|x - x_0\\| \leq R\}</math>なる <math>x_0 \in \mathbf{R}^n</math> 及び <math>R \in \mathbf{R}</math> が既知である.~~
−
−	~~:<math>\mbox{(ii)} \quad P\, </math> が空でないならば, その体積は <math>\varepsilon (> 0)</math> 以上である.~~
−
−
−	~~楕円体法では, いわば~~ 「<math>n\,</math>次元空間での [[楕円体]]を用いた2分探索」を行うことにより, <math>P\,</math>の点を求める. 各反復では, <math>P\,</math>を含む楕円体<math>E_k\,</math> を常に保持する. 楕円体 <math>E_k\,</math>は, 中心と呼ばれるベクトル <math>x_k \in \mathbf{R}^n</math>及び<math>n \times n</math>正定値対称行列<math>B_k\,</math>を用いて,
−
−
−	~~:<math>E_k = \{x \in \mathbf{R}^~~n ~~\mid (x - x_k)^{\top} B_k^{-1}(x - x_k) \leq 1\}</math>~~
−
−
−	~~と表される. なお, 上記の仮定 (i) より, <math>B_0 = R^2 I</math> と選ぶことができる.~~
−
−	各反復では, <math>x_k \in P\,</math> が成り立つか否かを調べる. 成り立つ場合はアルゴリズムを停止する. 成り立たない場合は, <math>a_i^{\top} x > b_i</math> なる <math>i\,</math> が存在するので, そのような <math>i\,</math> を見つける. 中心 <math>x_k\,</math> を通る超平面 <math>a_i^{\top} x = a_i^{\top} x_k</math> により, <math>E_k\,</math> を半分にして得られる集合 <math>E_k' = \{x \in E_k \mid a_i^{\top} x \leq a_i^{\top} x_k\}</math> に対し, これを含み, かつ体積が最小の楕円体を <math>E_{k+1}\,</math> とおく. そのような楕円体 <math>E_{k+1}\,</math> を表す <math>x_{k+1}\,</math> 及び <math>B_{k+1}\,</math> は次のようにして求められる:
−
−
−	~~:<math>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).</math>~~
−
−
−	~~ここで, <math>d = (1/\sqrt{a_i^{\top}B_k a_i})B_k a_i</math>である.~~
−
−
−	~~上記のように <math>E_{k+1}\,</math> を定めると, 楕円体の体積の比は,~~
−
−
−	~~:<math>\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</math>~~
−
−
−	となる. したがって, 楕円体の体積は線形空間の次元 <math>n\,</math> のみに依存する一定の比率で減少していく. 反復回数 <math>k\,</math> が十分大きくなり楕円体の体積が <math>\varepsilon</math> 未満になったとすると, 仮定 (ii) により <math>P = \emptyset</math> であることが分かるので, アルゴリズムを停止する. <math>P\,</math> が多面体であることから, 仮定 (i), (ii) での <math>x_0\,</math>, <math>R\,</math>, <math>\varepsilon</math> をうまく選ぶことができ, それにより多項式回の反復で終了することが導かれる.
−
−	上記で述べた楕円体法の改良として,「深い」(deep)カットを用いた方法が提案されている. この方法では, 半楕円体 <math>E_k'\,</math> の代わりに, より小さな集合 <math>\{x \in E_k \mid a_i^{\top} x \leq b_i\}</math> に注目し, それを含む最小の楕円体 <math>E_{k+1}\,</math> へと更新していく. この場合, 連続する2つの楕円体の比は, <math>\alpha = (a_i^{\top} x_k - b_i)/\sqrt{a_i^{\top}B_k a_i}</math> とおくと,
−
−
−	~~:<math>\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}</math>~~
−
−
−	~~と表され, また <math>0 \leq \alpha \leq 1</math> なので, 元の楕円体法に比べて反復回数が減少することがわかる.~~
−
−	さらに, 代用(surrogate)カット, 平行(parallel)カットを用いれば, 楕円体の体積比をより減少させることができる. また, 深いカットと全く逆の考え方により得られる「浅い」(shallow)カットを用いると, 連続する楕円体の体積比は逆に増加するが, 理論的には, 他のカットでは得られない興味深い結果を得ることができる. これらのカットについての詳細は参考文献を参照されたい.
−
−	線形計画法に対する楕円体法の適用は, 線形計画のみならず組合せ最適化においても重要な結果を残している. その1つが, 最適化問題と[[分離問題]]の多項式時間に関する等価性であろう.
−
−	<math>P \subseteq \mathbf{R}^n</math> を多面体とする. ただし, <math>P\,</math> の不等式系による表現は必ずしも与えられていない, と仮定する. 分離問題とは, 任意のベクトル <math>x_* \in \mathbf{R}^n</math> が与えられたとき, <math>x_* \in P</math> か否かを判定し, <math>x_* \not\in P</math> ならば <math>a^{\top} x \leq b</math> <math>(\forall x \in P)</math> かつ <math>a^{\top} x_* > b</math> なる <math>a \in \mathbf{R}^n</math> 及び <math>b \in \mathbf{R}</math> を求める問題のことである. 上記で述べた楕円体法のアルゴリズムを見ると分かるが, 必ずしも <math>P\,</math> の不等式表現が陽に与えられている必要はなく, 各反復において <math>P\,</math> と <math>x_k\,</math> に関する分離問題を多項式時間で解けるならば, 最適化問題もまた多項式時間で解くことができる. 一方, この逆もまた成り立つことが 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.

@@ 1行目: / 1行目: @@
-だえんたいほう(ellipsoid method)
+'''【だえんたいほう (ellipsoid method)】'''
-　[[楕円体法]](ellipsoid method) は, 微分不可能な凸計画問題に対する解法として, 1976年にユーディンとネミロフスキー(Yudin-Nemirovskii) によって提案された.  その後 1979年にカチヤン(L. G. Khachiyan)は, 楕円体法が 線形計画問題に対する [[多項式時間解法]] に成り得ることを示した.  この結果は, 長年にわたって未解決のままであった,「線形計画問題を多項式時間で解くことが出来るか?」という計算複雑度に関する問題への肯定的な答を与えるものであり, 数理計画の分野に衝撃をもたらした.  線形計画法に対する解法としての楕円体法は, 実用の面からは単体法などに比べて効率が悪く, また理論的な計算量の面からも, 1984年以降に現れた内点法に劣っていることが分かっている. しかしながら, 線形, 非線形, 組合せなどの最適化問題に対し, 様々な理論的な結果を残している.
+　[[楕円体法]](ellipsoid method) は, 微分不可能な凸計画問題に対する解法として, 1976年にユーディンとネミロフスキー(Yudin-Nemirovskii) によって提案された.  その後1979年にカチヤン(L. G. Khachiyan)は, 楕円体法が線形計画問題に対する[[多項式時間解法]] に成り得ることを示した.  この結果は, 長年にわたって未解決のままであった,「線形計画問題を多項式時間で解くことが出来るか?」という計算複雑度に関する問題への肯定的な答を与えるものであり, 数理計画の分野に衝撃をもたらした.  線形計画法に対する解法としての楕円体法は, 実用の面からは単体法などに比べて効率が悪く, また理論的な計算量の面からも, 1984年以降に現れた内点法に劣っていることが分かっている. しかしながら, 線形, 非線形, 組合せなどの最適化問題に対し, 様々な理論的な結果を残している.
 　楕円体法を説明するために, 与えられた多面体 <math>P = \{x \in \mathbf{R}^n \mid a_i^{\top} x \leq b_i\ (i = 1, 2, \cdots, m)\}</math> が空であるか否かを判定し, また空でなければ <math>P\,</math> に含まれる点を求める, という非空性問題について考える. なお, <math>P\,</math> の上での線形関数 <math>c^{\top} x</math> の最大化問題を解くには, <math>\{x \in P \mid c^{\top} x \leq \gamma\}</math> という多面体に対する非空性問題を繰り返し解き, <math>\gamma \in \mathbf{R}</math> に関する2分探索を行えば良い.
@@ 9行目: / 9行目: @@
 :<math>\mbox{(i)} \quad  P \subseteq \{x \in \mathbf{R}^n \mid \|x - x_0\| \leq R\}</math>なる <math>x_0 \in \mathbf{R}^n</math> 及び <math>R \in \mathbf{R}</math> が既知である.
 :<math>\mbox{(ii)} \quad P\, </math> が空でないならば, その体積は <math>\varepsilon (> 0)</math> 以上である.
-　楕円体法では, いわば 「<math>n\,</math> 次元空間での [[楕円体]]を用いた2分探索」を行うことにより, <math>P\,</math> の点を求める. 各反復では, <math>P\,</math> を含む楕円体<math>E_k\,</math> を常に保持する. 楕円体 <math>E_k\,</math> は, 中心と呼ばれるベクトル <math>x_k \in \mathbf{R}^n</math>及び<math>n \times n</math>正定値対称行列<math>B_k\,</math>を用いて,
+　楕円体法では, いわば 「<math>n\,</math>次元空間での [[楕円体]]を用いた2分探索」を行うことにより, <math>P\,</math>の点を求める. 各反復では, <math>P\,</math>を含む楕円体<math>E_k\,</math> を常に保持する. 楕円体 <math>E_k\,</math>は, 中心と呼ばれるベクトル <math>x_k \in \mathbf{R}^n</math>及び<math>n \times n</math>正定値対称行列<math>B_k\,</math>を用いて,
@@ 30行目: / 31行目: @@
-上記のように <math>E_{k+1}\,</math> を定めると, 楕円体の体積の比は,
+　上記のように <math>E_{k+1}\,</math> を定めると, 楕円体の体積の比は,
@@ 60行目: / 61行目: @@
 [1] R. G. Bland, D. Goldfarb and M. J. Todd, "The ellipsoid method: a survey," ''Operations Research'', '''29'''(1981) 1039-1091.