楕円体法

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

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

歴史

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

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

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

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

説明

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

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

• 凸関数 $f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R}$,（n個の変数をもつ）ベクトル $x$ において $f_{0}(x)$ を最小化する。
• 凸の不等式制約 $f_{i}(x)\leqslant 0$, ただし、関数 $f_{i}$ は凸である; これらの制約は凸集合 $Q$ を構成する。
• 線型の等式制約 $h_{i}(x)=0$.

初期の楕円体 ${\mathcal {E}}^{(0)}\subset \mathbb {R} ^{n}$ を

${\mathcal {E}}^{(0)}=\left\{z\in \mathbb {R} ^{n}\ :\ (z-x_{0})^{T}P_{(0)}^{-1}(z-x_{0})\leqslant 1\right\}$

と最小解 $x^{*}$ が含まれるように定義する。ただし、$P_{(0)}\succ 0$とし、$x_{0}$ は楕円体 ${\mathcal {E}}$ の中心とする。

最後に凸集合 $Q$ に対する分離オラクルの存在性について説明する。 点 $x\in \mathbb {R} ^{n}$が与えられたとして、オラクルは二つの回答のうち一つを返す:

• 点 $x$ が $Q$ に含まれる、あるいは -
• 点 $x$ が $Q$ に含まれない、加えて点 $x$ と実行可能集合 $Q$ を分離する超平面が存在する"、すなわちベクトル $c$ によって任意の $y\in Q$ に対して $c\cdot x<c\cdot y$ を満たす。楕円体法は各反復ごとに以下のどちらかを出力する:

• 点は多面体 $Q$（実行可能な点）に含まれる、あるいは -
• $Q$ は空である.

不等式制約付き最小化問題の実行可能点において目的関数が常にゼロをとるとき、この問題は単に実行可能解を見つける問題と等価である。線形計画問題は線形の許容性判定問題に書き換えることができる（意味としては目的関数がゼロで制約条件に不等式あるいは等式の制約が存在する問題である。）。書き換える方法として線形計画問題の主問題と双対問題を組み合わせて一つの問題として扱う方法が挙げられる。 これは主実行可能解と双対実行可能解には弱双対性が成り立っていることから、主実行可能解における目的関数値と双対実行可能解における目的関数値の差が0以上であるという制約を新たに加える。もう一つの方法としては線形計画問題の目的関数を新たな制約として扱い、二分探索によって最適値を見つける方法が挙げられる。

無制約最適化問題

k番目の反復における楕円体を説明する。ここで楕円体の中心を $x^{(k)}$ とする。

${\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\ :\ \left(x-x^{(k)}\right)^{T}P_{(k)}^{-1}\left(x-x^{(k)}\right)\leqslant 1\right\}.$

ここで分離オラクルによってベクトル $g^{(k+1)}\in \mathbb {R} ^{n}$ を得る。すなわち、

$g^{(k+1)T}\left(x^{*}-x^{(k)}\right)\leqslant 0.$

このことから最小解は反復を通じて以下の通りに含まれなければならない:

$x^{*}\in {\mathcal {E}}^{(k)}\cap \left\{z\ :\ g^{(k+1)T}\left(z-x^{(k)}\right)\leqslant 0\right\}.$

新たな楕円体 ${\mathcal {E}}^{(k+1)}$ は現在の半楕円体を含む最小体積の楕円体となり、新たな楕円体の中心 $x^{(k+1)}$ を求める。更新式は以下のように与えられる:

${\begin{aligned}x^{(k+1)}&=x^{(k)}-{\frac {1}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}\\P_{(k+1)}&={\frac {n^{2}}{n^{2}-1}}\left(P_{(k)}-{\frac {2}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}{\tilde {g}}^{(k+1)T}P_{(k)}\right)\end{aligned}}$

ただし、

${\tilde {g}}^{(k+1)}=\left({\frac {1}{\sqrt {g^{(k+1)T}P_{(k)}g^{(k+1)}}}}\right)g^{(k+1)}$

である。楕円体法は以下の停止基準を満たせば終了する:

${\sqrt {g^{(k)T}P_{(k)}g^{(k)}}}\leqslant \epsilon \quad \Rightarrow \quad f(x^{(k)})-f\left(x^{*}\right)\leqslant \epsilon .$

不等式制約付き最適化問題

制約付き最適化問題に対するk番目の反復における楕円体法について説明する。点 $x^{(k)}$は楕円体 ${\mathcal {E}}^{(k)}$ の中心であると仮定する。また反復を通じて得られた実行可能解で最良の目的関数値を記録し、このリストを $f_{\rm {best}}^{(k)}$ とする。点 $x^{(k)}$ が実行可能な点であるかでないかによって以下のどちらかの手続きを行う:

• もし $x^{(k)}$ が実行可能であるならば、無制約最適化問題と同様に劣勾配 $g_{0}$ が以下の性質を満たすように更新する:

$g_{0}^{T}(x^{*}-x^{(k)})+f_{0}(x^{(k)})-f_{\rm {best}}^{(k)}\leqslant 0$

• もし $x^{(k)}$ が実行不可能でありj番目の制約について違反しているならば、実行可能性カットを用いて楕円体を更新する。実行可能性カットは $f_{j}$ の劣勾配 $g_{j}$ が任意の実行可能解 z に対して以下の性質を満たさなければならない:

$g_{j}^{T}(z-x^{(k)})+f_{j}(x^{(k)})\leqslant 0$

参考文献

• Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
• V. Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37.
• V. Chandru and M.R.Rao, Integer Programming, Chapter 32 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45.
• ジョージ・ダンツィーグ and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
• ジョージ・ダンツィーグ and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
• ラースロー・ロヴァース: An Algorithmic Theory of Numbers, Graphs, and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986
• Kattta G. Murty, Linear Programming, Wiley, 1983.
• M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999.
• クリストス・パパディミトリウ and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover.
• Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6

関連解法

• 内点法 - 凸最適化問題に対する多項式時間アルゴリズム。楕円体法よりも優れた性能を有する。

外部リンク

• EE364b, a Stanford course homepage