楕円体法

出典: ORWiki

【だえんたいほう (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) より, B0 = R2I と選ぶことができる.

　各反復では, 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.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E6%A5%95%E5%86%86%E4%BD%93%E6%B3%95" より作成