《楕円体法》

【だえんたいほう (ellipsoid method)】

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

　楕円体法を説明するために, 与えられた多面体 $P=\{x\in \mathbf {R} ^{n}\mid a_{i}^{\top }x\leq b_{i}\ (i=1,2,\cdots ,m)\}$ が空であるか否かを判定し, また空でなければ $P\,$ に含まれる点を求める, という非空性問題について考える. なお, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P\,} の上での線形関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c^{\top} x} の最大化問題を解くには, $\{x\in P\mid c^{\top }x\leq \gamma \}$ という多面体に対する非空性問題を繰り返し解き, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \gamma \in \mathbf{R}} に関する2分探索を行えば良い.

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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}$ が既知である.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(ii)} \quad P\, } が空でないならば, その体積は $\varepsilon (>0)$ 以上である.

　楕円体法では, いわば 「構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\,} 次元空間での 楕円体を用いた2分探索」を行うことにより, $P\,$の点を求める. 各反復では, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P\,} を含む楕円体構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle E_k\,} を常に保持する. 楕円体 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle E_k\,} は, 中心と呼ばれるベクトル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_k \in \mathbf{R}^n} 及び構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n \times n} 正定値対称行列$B_{k}\,$を用いて,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle E_k = \{x \in \mathbf{R}^n \mid (x - x_k)^{\top} B_k^{-1}(x - x_k) \leq 1\}}

と表される. なお, 上記の仮定 (i) より, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_0 = R^2 I} と選ぶことができる.

　各反復では, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_k \in P\,} が成り立つか否かを調べる. 成り立つ場合はアルゴリズムを停止する. 成り立たない場合は, $a_{i}^{\top }x>b_{i}$ なる $i\,$ が存在するので, そのような $i\,$ を見つける. 中心 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_k\,} を通る超平面 $a_{i}^{\top }x=a_{i}^{\top }x_{k}$ により, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle E_k\,} を半分にして得られる集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle E_k' = \{x \in E_k \mid a_i^{\top} x \leq a_i^{\top} x_k\}} に対し, これを含み, かつ体積が最小の楕円体を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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}}dd^{\top }\right).$

ここで, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d = (1/\sqrt{a_i^{\top}B_k a_i})B_k a_i} である.

　上記のように 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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\,$ が十分大きくなり 楕円体の体積が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varepsilon} 未満になった とすると, 仮定 (ii) により $P=\emptyset$ であることが分かるので, アルゴリズムを停止する. $P\,$ が多面体であることから, 仮定 (i), (ii) での 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_0\,} , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle R\,} , $\varepsilon$ をうまく選ぶことができ, それにより多項式回の反復で終了することが導かれる.

　上記で述べた楕円体法の改良として,「深い」(deep)カットを用いた方法が 提案されている. この方法では, 半楕円体 $E_{k}'\,$ の代わりに, より小さな集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{x \in E_k \mid a_i^{\top} x \leq b_i\}} に注目し, それを含む最小の楕円体 $E_{k+1}\,$ へと更新していく. この場合, 連続する2つの楕円体の比は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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つが, 最適化問題と分離問題の多項式時間に関する等価性であろう.

　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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}$ を求める問題のことである. 上記で述べた楕円体法のアルゴリズムを見ると分かるが, 必ずしも 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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.