幾何学 において 、 空でない 内部 を持つ有界集合の チェビシェフ中心は 、集合全体を囲む最小半径の球の中心 、または（非等価であるが）最大の内接球の中心である 。 [1]
質問
{\displaystyle Q}
質問
{\displaystyle Q}
質問
{\displaystyle Q}
パラメータ推定 の分野において 、チェビシェフ中心アプローチは、 実現可能性集合が与えられた場合 に 、 x の最悪の推定誤差を最小化する（つまり、最悪ケース）ような の推定値を見つけようとします。
x ^
{\displaystyle {\hat {x}}}
x
{\displaystyle x}
質問
{\displaystyle Q}
x ^
{\displaystyle {\hat {x}}}
数学的表現 チェビシェフ中心には、いくつかの代替表現が存在します。集合 を考え 、そのチェビシェフ中心を で表します 。は 、次を解くことで計算できます。
質問
{\displaystyle Q}
x ^
{\displaystyle {\hat {x}}}
x ^
{\displaystyle {\hat {x}}}
分
x ^
、 r
{
r :
‖
x ^
− x
‖
2
≤ r 、 ∀ x ∈ 質問
}
{\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}.}
に対する要求を緩和する ために 、 （つまり、 は 半正定値行列 の集合）を要求し 、 min max の順序を max min に変更すると（詳細については参考文献を参照）、最適化問題は次のように定式化できます。
Δ
{\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}}}
参照
参考文献
^ ab Boyd, Stephen P.; Vandenberghe, Lieven (2004). 凸最適化 (PDF) . ケンブリッジ大学出版局. ISBN 978-0-521-83378-3 . 2011年 10月15日 閲覧 。 ^ アミール、ダン (1984). 「最良の同時近似 (チェビシェフ中心)」。 国際数値数学シリーズ / Internationale Schriftenreihe zur Numerischen Mathematik / Série internationale d'Analyse numérique 。ビルクホイザー。 19 ～ 35 ページ 。ISBN 9783034862530 。 ^ 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 。 ^ 「アーカイブコピー」 （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)。 
