楕円体法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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\}.}$

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

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

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

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

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

${\displaystyle {\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}}}$

ただし、

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

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

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

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

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

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

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

${\displaystyle 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

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法 逐次線形二次計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 逆削除法 　最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 フローネットワーク 最大流問題 ディニッツ法 エドモンズ–カープ法 フォード–ファルカーソン法 プリフロープッシュ法 最小費用流問題 ネットワーク単体法 アウトオブキルタ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ 群知能（ACO・PSO） ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア （一覧）