分離の予言

Black-box description of a convex set

分離オラクル（切断面オラクルとも呼ばれる）は、凸最適化の数学的理論における概念である。これは、最適化アルゴリズムへの入力として与えられる凸集合を記述する手法である。分離オラクルは、楕円体法への入力として用いられる。^{[1] : 87, 96, 98}

意味

KをR ⁿの凸コンパクト集合とする。Kの強分離オラクルとは、 R ⁿのベクトルyが与えられたときに、以下のいずれかを返すオラクル（ブラックボックス）である。^{[1] : 48}

• yがKにあると主張します。
• yとKを分ける超平面、つまりK内のすべてのxに対してとなるようなR ⁿ内のベクトルaを見つけます。 ${\displaystyle a\cdot y>a\cdot x}$

強い分離オラクルは完全に正確であるため、構築が難しい場合があります。実用的な理由から、 Kの境界と不等式における小さな誤差を許容する、より弱いバージョンが検討されています。小さな誤差許容値d >0 を仮定すると、次の式が成り立ちます。

• ベクトルyは、 K からのユークリッド距離がd以下であれば、 K のd近傍と呼ばれます 。
• ベクトルyがK 内にあり、 K 外部の任意の点からのユークリッド距離が少なくともdである場合、そのベクトルはK 内で d の深さであるといえます 。

弱バージョンでは、任意の実数ではなく、有限長の表現を持つ有理数も考慮されます。Kの弱分離オラクルとは、 ^Qnのベクトルyと0より大きい有理数dが与えられたときに、次のいずれかを返すオラクルです。 ^{[1] : 51}

• yがKのd近傍であると主張する。
• Q ⁿ内のベクトルaを見つけます。このベクトルの最大要素は 1 となり、K内のd深さのすべてのxに対して、 ${\displaystyle a\cdot y+d\geq a\cdot x}$

実装

凸集合の特殊なケースとして、線型不等式で表される集合があります。このような集合は凸多面体と呼ばれます。凸多面体に対する強分離オラクルを実装することは可能ですが、実行時間は入力形式に依存します。 ${\displaystyle K=\{x|Ax\leq b\}}$

不等式による表現

行列Aとベクトルbが入力として与えられ、となる場合、強い分離オラクルは次のように実装できます。^[2]点yが与えられた場合、を計算します。 ${\displaystyle K=\{x|Ax\leq b\}}$ ${\displaystyle Ay}$

• 結果が最大 の場合、定義によりyはKに含まれます。 ${\displaystyle b}$
• それ以外の場合、が の対応する値よりも大きくなるようなAの行が少なくとも 1 つ存在します。この行は、Kのすべてのxと同様に、分離超平面を与えます。 ${\displaystyle c}$ ${\displaystyle c\cdot y}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle c\cdot y>b\geq c\cdot x}$

このオラクルは、制約の数が多項式である限り、多項式時間で実行されます。

頂点による表現

Kの頂点集合が入力として与えられ、その頂点の凸包が与えられているとする。yがKに属するかどうかを判断するには、 yが入力ベクトルの凸結合であるかどうか、つまり、次式を満たす係数z ₁ ,..., z _kが存在するかどうかを確認する必要がある 。^{[1] : 49} ${\displaystyle K={\text{conv}}(v_{1},\ldots ,v_{k})=}$

• ${\displaystyle z_{1}\cdot v_{1}+\cdots +z_{k}\cdot v_{k}=y}$;
• ${\displaystyle 0\leq z_{i}\leq 1}$1,..., kの すべての iについて。

これはk個の変数とn 個の等式制約（ yの各要素につき 1 つ）を持つ線形計画法です。yがKに含まれない場合、上記のプログラムは解を持たず、分離オラクルはベクトルcを次のように求める必要があります。

• ${\displaystyle c\cdot y>c\cdot v_{i}}$1,..., kのすべての iについて。

上記の2つの表現は、大きさが大きく異なる場合があることに注意してください。多面体は少数の不等式で表現できますが、頂点の数が指数関数的に多くなります（例えば、n次元立方体）。逆に、多面体は少数の頂点しか持たないが、不等式の数の数が指数関数的に多くなります（例えば、(0,...,±1,...,0) という形の2nベクトルの凸包）。

問題固有の表現

一部の線形最適化問題では、制約の数が指数関数的であっても、多項式時間で動作するカスタム分離オラクルを作成できます。以下に例を示します。

• 最小コスト樹状化問題：重み付き有向グラフとその頂点rが与えられたとき、 rから他の任意の頂点への有向路を含む最小コストの部分グラフを求める。この問題は、各頂点の部分集合に制約（指数関数的数）を課す線形計画問題として表すことができる。しかし、最小カット手順をn -1回適用することで分離オラクルを実装することができる。^[3]
• 最大独立集合問題。これは、奇数長の閉路ごとに制約条件を課したLPで近似できる。このような閉路は指数関数的に多数存在するが、最小長の奇数閉路を見つけるだけで多項式時間で動作する分離オラクルを実装でき、これは多項式時間で実行できる。^[3]
• ビンパッキング問題における構成線形計画の双対。これは、各実行可能な構成に対して制約条件付きの線形計画によって近似できる。このような閉路は指数関数的に多数存在するが、ナップサック問題を解くことで擬多項式時間で動作する分離オラクルを実装できる。これは、Karmarkar-Karpビンパッキングアルゴリズムで利用されている。

非線形集合

f をR ⁿ上の凸関数とする。集合は R ^{n +1} 内の凸集合である。 fの評価オラクル（与えられた点ごとにfの値を返すブラックボックス）が与えられれば、ベクトル ( y , t ) がK内にあるかどうかを簡単にチェックできる。分離オラクルを得るためには、fのサブグラディエントを評価するオラクルも必要である。^{[1] ：49}あるベクトル ( y、s ) がK内にないと仮定し、f ( y ) > sとする。をyにおけるfのサブグラディエントとする（gは R ⁿ内のベクトル）。と表記する。すると、、およびK内のすべての ( x、t )に対して、となる。サブグラディエントの定義により、R ⁿ内のすべてのxに対してとなる。したがって、、となるので、、およびc は分離超平面を表す。 ${\displaystyle K=\{(x,t)|f(x)\leq t\}}$ ${\displaystyle c:=(g,-1)}$ ${\displaystyle c\cdot (y,s)=g\cdot y-s>g\cdot y-f(y)}$ ${\displaystyle c\cdot (x,t)=g\cdot x-t\leq g\cdot x-f(x)}$ ${\displaystyle f(x)\geq f(y)+g\cdot (x-y)}$ ${\displaystyle g\cdot y-f(y)\geq g\cdot x-f(x)}$ ${\displaystyle c\cdot (y,s)>c\cdot (x,t)}$

使用法

強い分離オラクルは、線形計画問題を解くための楕円体法への入力として与えることができます。線形計画問題 を考えてみましょう。楕円体法は、初期値として実行可能領域 全体を含む楕円体を保持します。各反復tにおいて、現在の楕円体の中心を取得し、それを分離オラクルに渡します。 ${\displaystyle {\text{maximize}}~~c\cdot x~~{\text{subject to}}~~Ax\leq b,x\geq 0}$ ${\displaystyle Ax\leq b}$ ${\displaystyle x_{t}}$

• オラクルが が実行可能である（つまり、 が集合 に含まれる）と判定した場合、 において「最適カット」を行います。つまり、 となるすべての点x を楕円体からカットします。これらの点は明らかに最適ではありません。 ${\displaystyle x_{t}}$ ${\displaystyle Ax\leq b}$ ${\displaystyle x_{t}}$ ${\displaystyle c\cdot x<c\cdot x_{t}}$
• オラクルが が実行不可能であると判定した場合、通常は が違反する特定の制約、つまり行列 A の行で となる行を返します。すべての実行可能なxに対して となるため、これはすべての実行可能なx に対してとなることを意味します。次に、 において「実行可能性カット」を行います。つまり、 となるすべての点yを楕円体からカットします。これらの点は明らかに実行不可能です。 ${\displaystyle x_{t}}$ ${\displaystyle x_{t}}$ ${\displaystyle a_{j}}$ ${\displaystyle a_{j}\cdot x_{t}>b_{j}}$ ${\displaystyle a_{j}\cdot x\leq b_{j}}$ ${\displaystyle a_{j}\cdot x_{t}>a_{j}\cdot x}$ ${\displaystyle x_{t}}$ ${\displaystyle a_{j}\cdot y>a_{j}\cdot x_{t}}$

切り取り線を引いた後、残りの領域を含む、より小さな新しい楕円体を構築します。このプロセスは、必要な精度の多項式時間で近似解に収束することが示されます。

弱いオラクルから強いオラクルへの変換

多面体に対する弱い分離オラクルが与えられれば、慎重な丸めの方法、またはディオファントス近似によって強い分離オラクルを構築することが可能である。^{[1] : 159}

参照

• 凸集合上のアルゴリズム問題

参考文献

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. 「MIT 6.854 2016年春 講義12：分離から最適化へ、そしてその逆へ；楕円体法 - YouTube」www.youtube.com . 2016年3月18日. 2021年1月3日閲覧。
3. Vempala, Santosh (2016). 「分離のオラクル」(PDF) .

Retrieved from "https://en.wikipedia.org/w/index.php?title=Separation_oracle&oldid=1324684307"