楕円体法

グラフの例。

数理最適化において、楕円体法は凸集合上の凸関数を最小化する反復法である。楕円体法は、各ステップで体積が一様に減少する楕円体の列を生成し、それによって凸関数の最小化点を囲む。

楕円体法は、有理数データによる実行可能な線形最適化問題を解決することに特化しており、入力サイズの多項式であるステップ数で最適な解を見つける アルゴリズムです。

歴史

楕円体法には長い歴史があります。反復法として、 Naum Z. Shorによって予備的なバージョンが導入されました。1972年には、Arkadi Nemirovskiと David B. Yudin (Judin) によって、実凸最小化の近似アルゴリズムが研究されました。

有理データを用いた線形計画問題を解くアルゴリズムとして、楕円体アルゴリズムがレオニード・ハチヤンによって研究されました。ハチヤンの功績は、線形計画が多項式時間で解けることを証明したことです。これは理論的な観点から注目すべき進歩でした。当時、線形問題を解く標準的なアルゴリズムは単体アルゴリズムでした。単体アルゴリズムの実行時間は通常、問題の規模に対して線形ですが、問題の規模に対して指数関数的に増加する例も存在します。したがって、あらゆるケースにおいて多項式であることが保証されるアルゴリズムを持つことは、理論的なブレークスルーでした。

カチヤンの研究は、線形計画法を解くアルゴリズムの中に、実行時間が多項式であることが証明できるものがあることを初めて示しました。しかしながら、実際にはこのアルゴリズムは非常に遅く、実用的価値はほとんどありませんでした。しかし、後に非常に実用的であることが判明した研究へのインスピレーションとなりました。具体的には、内点法であるカルマーカーのアルゴリズムは、楕円体法よりも実際にははるかに高速です。また、カルマーカーのアルゴリズムは、最悪の場合でもより高速です。

楕円体アルゴリズムは、複雑性理論家が問題の次元とデータのサイズに依存し、行数には依存しない（最悪の場合の）境界を達成することを可能にするため、長年にわたり組み合わせ最適化理論において重要な位置を占めてきました。 ^{[1] [2] [3] [4]} 21世紀になって初めて、同様の複雑性特性を持つ内点アルゴリズムが登場しました。^[要出典]

説明

凸最小化問題は、次の要素から構成されます。

• ベクトル上で最小化される凸関数 （n 個の変数を含む）。${\displaystyle f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle 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}}}$

最後に、凸集合 に対する分離オラクルの存在を要求します。点 が与えられた場合、オラクルは次の2つの答えのいずれかを返す必要があります。^[5]${\displaystyle Q}$ ${\displaystyle x\in \mathbb {R} ^{n}}$

• 「ポイントは」、または -${\displaystyle x}$ ${\displaystyle Q}$
• 「点は内になく、さらに、から分離する超平面、つまり、すべての に対してとなるベクトルがここにあります。${\displaystyle x}$ ${\displaystyle Q}$ ${\displaystyle x}$ ${\displaystyle Q}$ ${\displaystyle c}$ ${\displaystyle c\cdot x<c\cdot y}$ ${\displaystyle y\in Q}$

楕円体法の出力は次のいずれかになります。

• 多面体内の任意の点（つまり、任意の実行可能な点）、または -${\displaystyle Q}$
• 空の証明。${\displaystyle Q}$

どこでもゼロとなる関数の不等式制約付き最小化は、単純に任意の実行可能点を特定する問題に対応する。任意の線形計画問題は線形実行可能性問題（すなわち、何らかの線形不等式制約と線形等式制約の下でゼロ関数を最小化する問題）に帰着できることが判明している。これを実現する一つの方法は、主線形計画問題と双対線形計画問題を一つの計画に統合し、主解の値が双対解の値よりも悪くならないという追加の（線形）制約を追加することである。 ^{[6] : 84}別の方法は、線形計画問題の目的関数を追加の制約として扱い、二分探索を用いて最適値を見つけることである。^{[6] : 7–8}

制約のない最小化

アルゴリズムの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回目の反復では、前述と同様に楕円体の中心に点が存在します。また、これまでの実行可能な反復における最小の目的関数値を記録するリストを保持する必要があります。その点が実行可能かどうかに応じて、以下の2つのタスクのいずれかを実行します。 ${\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}$

• が実行不可能でj番目の制約に違反する場合、楕円体を実行可能性カットで更新する。この実行可能性カットは、以下の式を満たすべきである。${\displaystyle x^{(k)}}$ ${\displaystyle g_{j}}$ ${\displaystyle f_{j}}$

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

すべての実行可能なzに対して。

凸計画におけるパフォーマンス

理論的な実行時複雑度の保証

実RAMモデルにおける楕円体法の実行時計算量保証は、次の定理によって与えられる。^{[7] : Thm.8.3.1}

凸最適化問題の族を考える。形式は、f ( x )を最小化する。ただしxはGに属する。ここでfは凸関数、Gは凸集合（ユークリッド空間R ⁿの部分集合）である。この族の各問題pは、データベクトル Data( p ) で表される。例えば、関数fと実行可能領域Gを表す行列およびベクトルの実数値係数である。問題pのサイズ、Size( p ) は、 Data( p )の要素数（実数）として定義される。以下の仮定が必要である。

1. G (実現可能領域) は次のとおりです。
   • 境界付き;
   • 空でない内部を持ちます（したがって厳密に実行可能な点が存在します）。
2. Data( p )が与えられれば、poly(Size(p))算術演算を使って計算できる。
   • Gを含む楕円体。
   • ボリュームGの下限 'MinVol(p)>0' 。
3. Data( p )とRn内の点x^が与えられれば、poly(Size(p))算術演算を使って計算できる。
   • Gの分離オラクル(つまり、xがG内にあると断言するか、 xとGを分離する超平面を返します)。
   • fの 1 次オラクル(つまり、f ( x ) の値と部分勾配f' ( x ) を計算します)。

これらの仮定の下では、楕円体法は「R多項式」である。これは、あらゆる問題インスタンスpとあらゆる近似比ε >0 に対して、この方法が次を満たす解 x を見つけるような多項式 Poly が存在することを意味する。

${\displaystyle f(x)-\min _{G}f\leq \varepsilon \cdot [\max _{G}f-\min _{G}f]}$ 、

実数に対して最大で次の回数の算術演算を使用します。

${\displaystyle Poly(Size(p))\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

ここで、V ( p ) はデータに依存する量です。直感的に言えば、これは精度が1桁増加するのに必要な演算回数がSize( p )の多項式であることを意味します。楕円体法の場合、以下の式が成り立ちます。

${\displaystyle V(p)=\left[{\frac {Vol({\text{initial ellipsoid}})}{Vol(G)}}\right]^{1/n}\leq \left[{\frac {Vol({\text{initial ellipsoid}})}{MinVol(p)}}\right]^{1/n}}$ 。

楕円体法では最大でステップが必要であり、各ステップでは Poly(Size(p)) の算術演算が必要です。 ${\displaystyle 2(n-1)n\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

実践的なパフォーマンス

楕円体法は、平面配置問題などの低次元問題において数値的に安定して用いられる。NemirovskyとBenTal ^{[7]の8.3.3節で}は、変数の数が20～30以下の場合に効率的であると述べられている。これは、制約条件が数千個あっても反復回数が制約条件の数に依存しないためである。しかし、変数数が多い問題では、楕円体法は非常に非効率的であり、反復回数はO( n ² )のように増加する。

たとえ「小さい」サイズの問題の場合でも、数値的不安定性と実際にはパフォーマンスの低下に悩まされます^{[引用が必要]}。

理論的重要性

楕円体法は、組合せ最適化における重要な理論的手法です。計算複雑性理論において、楕円体アルゴリズムは、その計算複雑性が行数ではなく列数と係数のデジタルサイズに依存するため、魅力的です。

楕円体法を使用すると、凸集合上の多くのアルゴリズムの問​​題が多項式時間で同等であることを示すことができます。

線形計画法におけるパフォーマンス

レオニード・ハチヤンは、楕円体法を線形計画法の特殊なケースに適用しました。すなわち、A,b,c のすべての係数が有理数であるとき、 c ^T x st Ax ≤ bを最小化します。彼は線形計画法が多項式時間で解けることを示し、ハチヤンの定理の概要を示します。^{[7] ：Sec.8.4.2}

ステップ1：最適化を探索問題に縮小する。線形計画法の双対性定理によれば、上記の最小化問題は探索問題に縮小できる：x,y をAx ≤ b ; A ^T y = c ; y ≤ 0 ; c ^T x=b ^T y で求める。 最初の問題は、2番目の問題が解ける場合と同数である。問題が解ける場合、 2番目の問題の解のx成分は、最初の問題の最適解となる。したがって、これからは、z ≥ 0 をRz ≤ rで求める問題を解く必要があると仮定できる。すべての有理数係数に共通分母を掛け合わせると、すべての係数が整数であると仮定できる。

ステップ2：探索を実行可能性検証に簡略化します。Rz ≤ rにおいてz ≥ 0を見つける問題は、「 Rz ≤ rとなるz ≥ 0は存在するか？ 」という二項決定問題に簡略化できます。これは次のように実行できます。決定問題への答えが「いいえ」の場合、探索問題への答えは「なし」となり、処理は完了です。それ以外の場合は、最初の不等式制約R ₁ z ≤ r ₁を等式R ₁ z = r ₁に置き換え、決定問題を再度適用します。答えが「はい」の場合、等式はそのまま維持されます。答えが「いいえ」の場合、不等式は冗長であるため削除できます。次に、次の不等式制約に進みます。各制約について、等式に変換するか削除します。最終的に、等式制約のみが残ります。これは、連立一次方程式を解く任意の方法で解くことができます。

ステップ3：決定問題は別の最適化問題に簡約できます。残差関数f(z) := max[(Rz) ₁ -r ₁ , (Rz) ₂ -r ₂ , (Rz) ₃ -r ₃ ,...] を定義します。明らかに、f ( z )≤0 はRz ≤ rの場合に限ります。したがって、決定問題を解くには、最小化問題 min _z f ( z )を解けば十分です。関数fは凸関数（線形関数の最大値）です。最小値をf * で表します。すると、決定問題への答えは f*≤0 の場合に限り「はい」となります。

ステップ4：最適化問題 min _z f ( z )において、 z は辺の長さが2 ^Lのボックス内にあると仮定できます。ここで、Lは問題データのビット長です。したがって、楕円体法を用いてLの多項式時間で、任意の精度 ε まで解くことができる有界凸計画が得られます。

ステップ5：ある多項式において、f*>0ならばf*>2 ^-poly(L)であることが証明できます。したがって、精度ε=2 ^-poly(L)を選択できます。すると、楕円体法によって求められるε近似解は、f*>0の場合に限り正となり、かつ決定問題が解けない場合に限り正となります。

変種

楕円体法には、各ステップでどのようなカットが使用されるかによっていくつかのバリエーションがあります。^{[1] ：第3節}

異なるカット

中心切断楕円体法^[1] : ^{82, 87–94}では、切断は常に現在の楕円体の中心を通る。入力は有理数ε >0、弱分離オラクルによって与えられた凸体K 、そしてS(0, R )（原点を中心とする半径Rの球体）にKが含まれるような数Rである。出力は以下のいずれかである。

• (a) Kから最大εの距離にあるベクトル、または
• (b) 正定値行列Aと点aがあり、楕円体 E(​​ A , a ) はK を含み、 E( A , a ) の体積は最大でεである。

ステップ数は、必要な精度桁数はp  := 8 N、分離オラクルの必要な精度はd  := 2 ^{− p}です。 ${\displaystyle N:=\lceil 5n\log(1/\epsilon )+5n^{2}\log(2R)\rceil }$

ディープカット楕円体法^[1] : ⁸³では、各ステップで楕円体の半分以上がカットされます。これにより、Kが空であることの発見が速くなります。しかし、Kが空でない場合は、セントラルカット法の方が実行可能点をより速く見つけられる例があります。ディープカットの使用によって実行時間の大きさが変わることはありません。

浅いカット楕円体法では、^{[1] : 83, 94–101 、}各ステップで楕円体の半分未満がカットされます。この方法は実際にはあまり役に立ちませんが、理論的には重要です。他の方法からは導き出せない結果を証明できるからです。入力は有理数ε >0、浅い分離オラクルによって与えられた凸体K 、そしてS(0, R )がKを含むような数Rです。出力は正定値行列Aと、次のいずれかが成り立つ 点aです。

• (a) 楕円体 E(​​ A , a ) が神託によって「困難」であると宣言されている、または -
• (b) KはE( A , a )に含まれ、E( A , a )の体積は最大でεである。

ステップ数は、必要な精度桁数はp  := 8 Nです。${\displaystyle N:=\lceil 5n(n+1)^{2}\log(1/\epsilon )+5n^{2}(n+1)^{2}\log(2R)+\log(n+1)\rceil }$

異なる楕円体

外接楕円体法と内接楕円体法にも区別がある。^[8]

• 外接楕円体法では、各反復において、前の楕円体の残りの部分を包含する最小の体積を持つ楕円体を求める。この方法は、ユディンとネミロフスキーによって開発された。^[9]
• 内接楕円体法では、各反復において、前の楕円体の残りの部分を包含する最大の体積を持つ楕円体を求める。この手法は、タラソフ、カチアン、エルリクによって開発された。^[10]

これらの方法は実行時間の複雑さが異なります (以下、nは変数の数、イプシロンは精度です)。

• 外接法は反復計算を必要とし、各反復計算は分離超平面の探索と新たな外接楕円体の探索から構成されます。外接楕円体の探索には時間がかかります。${\displaystyle O(n^{2})\ln {\frac {1}{\epsilon }}}$ ${\displaystyle O(n^{2})}$
• 内接法は反復計算を必要とし、各反復計算は分離超平面の探索と新たな内接楕円体の探索から構成されます。内接楕円体の探索には、ある程度の時間がかかります。${\displaystyle O(n)\ln {\frac {1}{\epsilon }}}$ ${\displaystyle O(n^{3.5+\delta })}$ ${\displaystyle \delta >0}$

これらの方法の相対的な効率は、分離超平面を見つけるのに必要な時間に依存し、これはアプリケーションによって異なります。実行時間が の場合、外接法の方が効率的ですが、の場合、内接法の方が効率的です。^[8]${\displaystyle O(n^{t})}$ ${\displaystyle t\leq 2.5}$ ${\displaystyle t>2.5}$

関連する方法

• 重心法は概念的に単純で、必要なステップ数も少ない手法です。しかし、各ステップは、現在の実行可能多面体の重心を計算する必要があるため、計算コストが高くなります。
• 内点法でも凸最適化問題を多項式時間で解くことができますが、その実用的なパフォーマンスは楕円体法よりもはるかに優れています。

注記

1. マーティン・グレッチェル; Lovász, ラスロー; Schrijver、Alexander (1993)、幾何学的アルゴリズムと組み合わせ最適化、Algorithms and Combinatorics、vol. 2 (第 2 版)、Springer-Verlag、ベルリン、doi :10.1007/978-3-642-78240-4、ISBN 978-3-642-78242-8、MR  1261419
2. L. Lovász：「数、グラフ、凸性のアルゴリズム理論」、CBMS-NSF応用数学地域会議シリーズ50、SIAM、フィラデルフィア、ペンシルバニア州、1986年。
3. V. Chandru と MRRao、「線形計画法」、 MJ Atallah編『アルゴリズムと計算理論ハンドブック』第 31 章 、CRC Press 1999、31-1 から 31-37。
4. V. Chandru と MRRao、「整数計画法」、MJAtallah 編『アルゴリズムと計算理論ハンドブック』第 32 章、CRC Press 1999、32-1 から 32-45。
5. “MIT 6.854 Spring 2016 Lecture 12: From Separation to Optimization and Back; Ellipsoid Method - YouTube”. www.youtube.com . 2016年3月18日. 2021年12月22日時点のオリジナルよりアーカイブ。 2021年1月3日閲覧。
6. マトウシェク、ジジー;ガートナー、ベルント (2007)。線形計画法を理解して使用する。大学のテキスト。ベルリン;ニューヨーク：スプリンガー。ISBN 978-3-540-30697-9。
7. Nemirovsky and Ben-Tal (2023). 「最適化III：凸最適化」（PDF） . 2023年12月10日時点のオリジナル（PDF）からのアーカイブ。
8. Newman, DJ; Primak, ME (1992-12-01). 「均衡経済モデルを解くための外接楕円体法と内接楕円体法の複雑性」 .応用数学と計算. 52 (2): 223– 231. doi :10.1016/0096-3003(92)90079-G. ISSN  0096-3003.
9. Berkovich, Yudin David; Semenovich, Nemirovsky Arkady. 「情報複雑性と凸極値問題の効率的な解法」. Matekon . 13 (2): 22– 45. ISSN  0025-1127.
10. Primak, ME; Kheyfets, BL (1995-06-01). 「内接楕円体法の修正」 .数学およびコンピュータモデリング. 21 (11): 69– 76. doi :10.1016/0895-7177(95)00080-L. ISSN  0895-7177.

さらに読む

• Dmitris Alevras および Manfred W. Padberg、「Linear Optimization and Extensions: Problems and Extensions」、Universitext、Springer-Verlag、2001 年。(Padberg の問題と解答。)
• V. Chandru および MRRao、「線形計画法」、MJAtallah 編『 アルゴリズムおよび計算理論ハンドブック』第 31 章、CRC Press 1999、31-1 から 31-37。
• V. Chandru および MRRao、「整数計画法」、第 32 章、 MJAtallah 編、 『アルゴリズムおよび計算理論ハンドブック』、CRC Press 1999、32-1 から 32-45。
• George B. DantzigとMukund N. Thapa. 1997.線形計画法1：入門. Springer-Verlag.
• George B. DantzigとMukund N. Thapa. 2003.線形計画法2：理論と拡張. Springer-Verlag.
• L. Lovász：「数、グラフ、凸性のアルゴリズム理論」、CBMS-NSF応用数学地域会議シリーズ50、SIAM、ペンシルベニア州フィラデルフィア、1986年
• Kattta G. Murty、「線形計画法」、Wiley、1983 年。
• M. Padberg、「線形最適化と拡張」、第 2 版、Springer-Verlag、1999 年。
• Christos H. Papadimitriouおよび Kenneth Steiglitz、「Combinatorial Optimization: Algorithms and Complexity」、新しい序文を付けて修正再出版、Dover。
• Alexander Schrijver、線形および整数計画法の理論。ジョン・ワイリー＆サンズ、1998、ISBN 0-471-98232-6

外部リンク

• EE364b、スタンフォード大学のコースホームページ