チェビシェフ中心

幾何学において、空でない内部を持つ有界集合のチェビシェフ中心は、集合全体を囲む最小半径の球の中心、あるいは（非等価的に）最大の内接球の中心である。[1] 質問 {\displaystyle Q} 質問 {\displaystyle Q} 質問 {\displaystyle Q}

パラメータ推定の分野では、チェビシェフ中心アプローチは、実現可能性セットが与えられた場合に、x の最悪の推定誤差を最小化する推定値を見つけようとします (つまり、最悪のケースが最良)。 × ^ {\displaystyle {\hat {x}}} × {\displaystyle x} 質問 {\displaystyle Q} × ^ {\displaystyle {\hat {x}}}

数学的表現

チェビシェフ中心にはいくつかの表現法があります。集合 を考え、そのチェビシェフ中心を と表記します。は次を解くことで計算できます。 質問 {\displaystyle Q} × ^ {\displaystyle {\hat {x}}} × ^ {\displaystyle {\hat {x}}}

分 × ^ 、 r { r : ‖ × ^ − × ‖ 2 ≤ r 、 た × ∈ 質問 } {\displaystyle \min _{{\hat {x}},r}\left\{r:\left\|{\hat {x}}-x\right\|^{2}\leq r,\forall x\in Q\right\}}

ユークリッドノルム に関して、あるいは次のように解くことによっても解ける。 ‖ ⋅ ‖ {\displaystyle \|\cdot \|}

a r g m i n x ^ ⁡ max x ∈ Q ‖ x − x ^ ‖ 2 . {\displaystyle \operatorname {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\|^{2}.} [1]

これらの特性にもかかわらず、チェビシェフ中心を求めることは困難な数値最適化問題となる可能性がある。例えば、上記の2番目の表現では、集合Qが凸でない場合、内部最大化は非凸となる。

プロパティ

内積空間および2次元空間において、が閉有界凸であるとき、チェビシェフ中心は に含まれる。言い換えれば、チェビシェフ中心の探索は の内部で一般性を失うことなく行うことができる。[2] Q {\displaystyle Q} Q {\displaystyle Q} Q {\displaystyle Q}

他の空間では、たとえ凸であっても、 チェビシェフ中心は に含まれない可能性がある 。例えば、 が点 (1,1,1)、(-1,1,1)、(1,-1,1)、(1,1,-1) の凸包によって形成される四面体である場合、ノルムを用いてチェビシェフ中心を計算すると、[3]が得られる。 Q {\displaystyle Q} Q {\displaystyle Q} Q {\displaystyle Q} ℓ ∞ {\displaystyle \ell _{\infty }}

0 = a r g m i n x ^ ⁡ max x ∈ Q ‖ x − x ^ ‖ ∞ 2 . {\displaystyle 0=\operatorname {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\|_{\infty }^{2}.}

リラックスしたチェビシェフ中心

集合が楕円体の交差として表される場合を考えてみましょう。 Q {\displaystyle Q} k {\displaystyle k}

min x ^ max x { ‖ x ^ − x ‖ 2 : f i ( x ) ≤ 0 , 0 ≤ i ≤ k } {\displaystyle \min _{\hat {x}}\max _{x}\left\{\left\|{\hat {x}}-x\right\|^{2}:f_{i}(x)\leq 0,0\leq i\leq k\right\}}

と

f i ( x ) = x T Q i x + 2 g i T x + d i ≤ 0 , 0 ≤ i ≤ k . {\displaystyle f_{i}(x)=x^{T}Q_{i}x+2g_{i}^{T}x+d_{i}\leq 0,0\leq i\leq k.\,}

追加の行列変数を導入することで、チェビシェフ中心の内部最大化問題を次のように記述できます。 Δ = x x T {\displaystyle \Delta =xx^{T}}

min x ^ max ( Δ , x ) ∈ G { ‖ x ^ ‖ 2 − 2 x ^ T x + Tr ⁡ ( Δ ) } {\displaystyle \min _{\hat {x}}\max _{(\Delta ,x)\in G}\left\{\left\|{\hat {x}}\right\|^{2}-2{\hat {x}}^{T}x+\operatorname {Tr} (\Delta )\right\}}

トレース演算子は どこにあり、 Tr ⁡ ( ⋅ ) {\displaystyle \operatorname {Tr} (\cdot )}

G = { ( Δ , x ) : f i ( Δ , x ) ≤ 0 , 0 ≤ i ≤ k , Δ = x x T } {\displaystyle G=\left\{(\Delta ,x):{\rm {f}}_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta =xx^{T}\right\}}
f i ( Δ , x ) = Tr ⁡ ( Q i Δ ) + 2 g i T x + d i . {\displaystyle f_{i}(\Delta ,x)=\operatorname {Tr} (Q_{i}\Delta )+2g_{i}^{T}x+d_{i}.}

を要求してに対する要求を緩和し、すなわち が半正定値行列の集合である場合に、最小値、最大値の順序を最大値、最小値に変更すると (詳細については参考文献を参照)、最適化問題は次のように定式化できます。 Δ {\displaystyle \Delta } Δ ≥ x x T {\displaystyle \Delta \geq xx^{T}} Δ − x x T ∈ S + {\displaystyle \Delta -xx^{T}\in S_{+}} S + {\displaystyle S_{+}}

R C C = max ( Δ , x ) ∈ T { − ‖ x ‖ 2 + Tr ⁡ ( Δ ) } {\displaystyle RCC=\max _{(\Delta ,x)\in {T}}\left\{-\left\|x\right\|^{2}+\operatorname {Tr} (\Delta )\right\}}

と

T = { ( Δ , x ) : f i ( Δ , x ) ≤ 0 , 0 ≤ i ≤ k , Δ ≥ x x T } . {\displaystyle {T}=\left\{(\Delta ,x):f_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta \geq xx^{T}\right\}.}

この最後の凸最適化問題は、緩和チェビシェフ中心（RCC）として知られています。RCCには以下の重要な特性があります。

  • RCC は正確なチェビシェフ中心の上限です。
  • RCC はユニークです。
  • RCC は実現可能です。

制約付き最小二乗法

よく知られている制約付き最小二乗法（CLS）問題は、チェビシェフ中心の緩和版であることが示されています。 [引用が必要]

元の CLS 問題は次のように定式化できます。

x ^ C L S = * ⁡ arg ⁡ min x ∈ C ‖ y − A x ‖ 2 {\displaystyle {\hat {x}}_{CLS}=\operatorname {*} {\arg \min }_{x\in C}\left\|y-Ax\right\|^{2}}

と

C = { x : f i ( x ) = x T Q i x + 2 g i T x + d i ≤ 0 , 1 ≤ i ≤ k } {\displaystyle {C}=\left\{x:f_{i}(x)=x^{T}Q_{i}x+2g_{i}^{T}x+d_{i}\leq 0,1\leq i\leq k\right\}}
Q i ≥ 0 , g i ∈ R m , d i ∈ R . {\displaystyle Q_{i}\geq 0,g_{i}\in R^{m},d_{i}\in R.}

この問題は、次の最適化問題と同等であることが示されます。

max ( Δ , x ) ∈ V { − ‖ x ‖ 2 + Tr ⁡ ( Δ ) } {\displaystyle \max _{(\Delta ,{x})\in {V}}\left\{{-\left\|{x}\right\|^{2}+\operatorname {Tr} (\Delta )}\right\}}

と

V = { ( Δ , x ) : x ∈ C Tr ⁡ ( A T A Δ ) − 2 y T A T x + ‖ y ‖ 2 − ρ ≤ 0 , Δ ≥ x x T } . {\displaystyle V=\left\{{\begin{array}{c}(\Delta ,x):x\in C{\rm {}}\\\operatorname {Tr} (A^{T}A\Delta )-2y^{T}A^{T}x+\left\|y\right\|^{2}-\rho \leq 0,{\rm {{}\Delta \geq xx^{T}}}\\\end{array}}\right\}.}

この問題はチェビシェフ中心の緩和であることがわかります (ただし、上記の RCC とは異なります)。

RCC 対 CLS

RCCの解集合はCLSの解でもあるため、 となる。これは、CLS推定値がRCCよりも緩い緩和の解であることを意味する。したがって、CLSはRCCの上限であり、RCCは実チェビシェフ中心の上限である。 ( x , Δ ) {\displaystyle (x,\Delta )} T ∈ V {\displaystyle T\in V}

モデリングの制約

RCCとCLSはどちらも実実現可能性集合の緩和に基づいているため、 の定義形式は緩和版に影響を与えます。これは当然のことながら、RCCとCLSの推定値の品質に影響を与えます。簡単な例として、線形ボックス制約を考えてみましょう。 Q {\displaystyle Q} Q {\displaystyle Q}

l ≤ a T x ≤ u {\displaystyle l\leq a^{T}x\leq u}

これは次のようにも書ける。

( a T x − l ) ( a T x − u ) ≤ 0. {\displaystyle (a^{T}x-l)(a^{T}x-u)\leq 0.}

最初の表現では 2 番目の表現の上限推定値が得られることが判明しており、そのため、最初の表現を使用すると、計算された推定値の品質が大幅に低下する可能性があります。

この単純な例は、実現可能性領域の緩和が使用される場合、制約の定式化に細心の注意を払う必要があることを示しています。

線形計画問題

この問題は、領域Qが有限個の超平面の交差である限り、線形計画問題として定式化できる。 [4]以下のように定義された多面体Qが与えられれば、次の線形計画法で解くことができる。

Q = { x ∈ R n : A x ≤ b } {\displaystyle Q=\{x\in R^{n}:Ax\leq b\}}
max r , x ^ r s.t. a i x ^ + ‖ a i ‖ r ≤ b i and r ≥ 0 {\displaystyle {\begin{aligned}&\max _{r,{\hat {x}}}&&r\\&{\text{s.t.}}&&a_{i}{\hat {x}}+\|a_{i}\|r\leq b_{i}\\&{\text{and}}&&r\geq 0\end{aligned}}}

参照

参考文献

  1. ^ ab Boyd, Stephen P.; Vandenberghe, Lieven (2004). 凸最適化(PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. 2011年10月15日閲覧。
  2. ^ アミール、ダン (1984). 「最良の同時近似 (チェビシェフ中心)」。国際数値数学シリーズ / Internationale Schriftenreihe zur Numerischen Mathematik / Série internationale d'Analyse numérique。ビルクホイザー。19 ～ 35ページ 。ISBN 9783034862530。
  3. ^ Dabbene, Fabrizio; Sznaier, Mario; Tempo, Roberto (2014年8月). 「均一分布ノイズを用いた確率的最適推定」. IEEE Transactions on Automatic Control . 59 (8): 2113– 2127. doi :10.1109/tac.2014.2318092. S2CID  17857976.
  4. ^ 「アーカイブコピー」（PDF） 。 2014年9月12日時点のオリジナル（PDF）からアーカイブ。 2014年9月12日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)
  • YC Eldar、A. Beck、M. Teboulle、「有界誤差推定のためのミニマックスチェビシェフ推定量」、IEEE Trans. Signal Process.、56(4): 1388–1397 (2007)。
  • A. Beck、YC Eldar、「境界ノイズによる回帰分析における正則化：チェビシェフ中心アプローチ」、SIAM J. Matrix Anal. Appl. 29 (2): 606–625 (2007)。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Chebyshev_center&oldid=1276798766"