重心法

重心法は凸最適化の理論的アルゴリズムである。これは、1次元関数から多次元関数への二分法の一般化と見ることができる。 ^{[1] ：Sec.8.2.2}この方法は最適な収束率を達成するため理論的に重要である。しかし、各ステップの計算コストが非常に高いため、実用的な価値はほとんどない。

私たちの目標は、次の形式の凸最適化問題 を解くことです。

Gにおいてf ( x ) st x を最小化する、

ここで、f は凸関数であり、G はユークリッド空間R ⁿの凸部分集合です。

ここでは、「サブ勾配オラクル」があると仮定します。これは、任意のポイントでfのサブ勾配を計算できるルーチンです ( fが微分可能であれば、サブ勾配は勾配のみですが、 fが微分可能であるとは想定していません)。 ${\displaystyle \nabla f}$

この方法は反復的です。各反復tで、目的の最小値が確実に含まれる凸領域G _{t を}保持します。最初はG ₀ = Gです。その後、各反復t は次のように進行します。

• G _tの重心をx t_とします。
• x _tにおけるサブ勾配を計算し、f '( x _t ) と表記します。
  • 劣勾配の定義により、 fのグラフは劣勾配の上にあるため、G _t内のすべてのxに対して、 f ( x )− f ( x _t ) ≥ ( x − x _t ) ^T f'( x _t ) が成立します。
• f '( x _t )=0の場合、上記はx _tが正確な最小点であることを意味するため、終了してx _{t を返します。}
• _それ以外の場合は、G _{t +1}  := {G _t内のx :( x − xt ) ^Tf '( xt ₎ ≤0}とします。

上記の不等式により、fの最小点_は必ずGt +1に含まれなければならないことに注意されたい_。^{[1] ：Sec.8.2.2}

それは証明できる

${\displaystyle Volume(G_{t+1})\leq \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]\cdot Volume(G_{t})}$。

したがって、

${\displaystyle f(x_{t})-\min _{G}f\leq \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]^{t/n}[\max _{G}f-\min _{G}f]}$。

言い換えれば、この方法は残差目的値の線形収束を持ち、収束率は である。目的値のε近似値を得るために必要なステップ数は最大 である。^{[1] : Sec.8.2.2}${\displaystyle \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]^{1/n}\leq (1-1/e)^{1/n}}$${\displaystyle 2.13n\ln(1/\epsilon )+1}$

この方法の主な問題は、各ステップで多面体の重心を計算する必要があることです。この問題に対してこれまでに知られているすべての方法では、次元nの指数関数的な数の算術演算が必要です。^{[1] ：Sec.8.2.2}したがって、この方法は5次元以上の場合には実際には役に立ちません。

楕円体法は、重心法の扱いやすい近似法と見ることができます。実行可能な多面体G _{t を}維持する代わりに、それを含む楕円体を維持します。楕円体の重心の計算は一般的な多面体の計算よりもはるかに簡単なので、楕円体法は通常、多項式時間で計算できます。