楕円体法

数学的最適化において、楕円体法は、凸集合上の凸関数を最小化する反復法です。楕円体法は、各ステップで体積が均一に減少する楕円体のシーケンスを生成し、凸関数の最小化を囲みます。

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

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

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

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

楕円体アルゴリズムにより、複雑性理論家は問題の次元とデータのサイズに依存し、行数には依存しない（最悪の場合の）境界を達成できるため、組み合わせ最適化理論では長年にわたって重要でした。^{[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つの答えのうちの1つを返す必要がある: ^[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}$

どこでもゼロである関数の不等式制約付き最小化は、実行可能な点を単純に特定する問題に対応する。任意の線形計画問題は線形実行可能性問題（つまり、線形不等式および等式制約の下でゼロ関数を最小化する）に還元できることが判明している。これを行う1つの方法は、主線形計画と双対線形計画を1つのプログラムに組み合わせ、主解の値が双対解の値よりも悪くないという追加の（線形）制約を追加することである。^{[6] ：84}別の方法は、線形計画の目的を追加の制約として扱い、バイナリサーチを使用して最適値を見つけることである。^{[6] ：7–8}

アルゴリズムのk回目の反復では、楕円体の中心に 点がある。${\displaystyle x^{(k)}}$

${\displaystyle {\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\ :\ \left(xx^{(k)}\right)^{T}P_{(k)}^{-1}\left(xx^{(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(zx^{(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 )を最小化するst 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 )はデータに依存する量です。直感的には、精度の桁ごとに必要な演算回数は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] ：Sec.8.3.3では、 変数の数が最大20〜30の場合に効率的であると述べています。これは、制約が数千あっても反復回数が制約の数に依存しないためです。ただし、変数が多い問題では、楕円体法は}非常に非効率的で、反復回数はO( n2 )に比例して増加します。

たとえ「小さな」サイズの問題の場合でも、数値的不安定性とパフォーマンスの低下に悩まされます^[要出典]。

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

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

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

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

ステップ 2: 検索を実現可能性チェックに縮小します。 z ≥ 0 またはRz ≤ r を見つける問題は、バイナリ決定問題、「 Rz ≤ rとなるz ≥ 0は存在するか? 」に縮小できます。これは次のように実行できます。決定問題への回答が「いいえ」の場合、検索問題への回答は「なし」となり、これで完了です。それ以外の場合は、最初の不等式制約R ₁ z ≤ r ₁を取り、等式R ₁ z = r ₁に置き換え、決定問題を再度適用します。回答が「はい」の場合、等式を維持します。回答が「いいえ」の場合、不等式は冗長であるため、削除できます。次に、次の不等式制約に進みます。各制約について、等式に変換するか、削除します。最終的には、等式制約のみになります。これは、線形方程式系を解く任意の方法で解決できます。

ステップ 3 : 決定問題は、別の最適化問題に縮小できます。残差関数f(z) := max[(Rz) ₁ -r ₁、(Rz) ₂ -r ₂、(Rz) ₃ -r ₃、...] を定義します。明らかに、f ( z )≤0 の場合に限ります。したがって、決定問題を解決するには、最小化問題 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] : 83 カットにより}各ステップで楕円体の半分以上が除去されます。これにより、 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}$

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

• Dmitris Alevras と Manfred W. Padberg、「Linear Optimization and Extensions: Problems and Extensions」、Universitext、Springer-Verlag、2001 年。(Padberg の問題と解答。)
• V. Chandru および MRRao、「線形計画法」、第 31 章、MJAtallah 編『 アルゴリズムと計算理論ハンドブック』、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 年
• Katta 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、スタンフォード大学のコースホームページ