Centrum Czebyszewa - Chebyshev center

W geometrii , środek Czebyszewa zbioru ograniczonego posiadającego niepuste wnętrze jest środkiem kuli o minimalnym promieniu obejmującej cały zbiór , lub alternatywnie (i nierównoważnie) środkiem największej wpisanej kuli . ${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$

W dziedzinie estymacji parametrów podejście ośrodka Czebyszewa próbuje znaleźć estymator dla danego zbioru wykonalności , taki, który minimalizuje najgorszy możliwy błąd estymacji dla x (np. najlepszy najgorszy przypadek). ${\displaystyle {\kapelusz {x}}}$${\displaystyle x}$${\displaystyle Q}$${\displaystyle {\kapelusz {x}}}$

reprezentacja matematyczna

Istnieje kilka alternatywnych reprezentacji ośrodka Czebyszewa. Rozważmy zbiór i oznaczmy jego centrum Czebyszewa przez . można obliczyć, rozwiązując: ${\displaystyle Q}$${\displaystyle {\kapelusz {x}}}$${\displaystyle {\kapelusz {x}}}$

${\ Displaystyle \ min _ {{\ kapelusz {x}} r} \ lewo \ {r: \ lewo \ | {\ kapelusz {x}} -x \ prawo \ | ^ {2} \ leq r \ dla wszystkich x\w Q\w prawo\}}$

w odniesieniu do normy euklidesowej lub alternatywnie rozwiązując: ${\displaystyle \|\cdot \|}$

${\ Displaystyle \ operatorname {\ underset {\ mathit {\ kapelusz {x}}} {argmin}} \ max _ {x \ w Q} \ po lewej \ | x-{\ kapelusz {x}} \ po prawej \ | ^ {2}.}$

Pomimo tych właściwości znalezienie centrum Czebyszewa może być trudnym problemem optymalizacji numerycznej . Na przykład w drugiej reprezentacji powyżej wewnętrzna maksymalizacja jest niewypukła, jeśli zbiór Q nie jest wypukły .

Nieruchomości

W przestrzeniach produktowych wewnętrznych i przestrzeniach dwuwymiarowych, jeśli jest zamknięty, ograniczony i wypukły, to centrum Czebyszewa znajduje się w . Innymi słowy, poszukiwania ośrodka Czebyszewa można prowadzić wewnątrz bez utraty ogólności. ${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$

Na innych polach centrum Czebyszewa może nie znajdować się w , nawet jeśli jest wypukłe. Na przykład, jeśli czworościan jest utworzony przez wypukłą powłokę punktów (1,1,1), (-1,1,1), (1,-1,1) i (1,1,-1), następnie obliczenie centrum Czebyszewa przy użyciu plonów norm ${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle \ell_{\infty}}$

${\ Displaystyle 0 = \ operatorname {\ underset {\ mathit {\ kapelusz {x}}} {argmin}} \ max _ {x \ w Q} \ po lewej \ | x-{\ kapelusz {x}} \ po prawej \ |_{\infty }^{2}.}$

Zrelaksowane centrum Czebyszewa

Rozważmy przypadek, w którym zbiór można przedstawić jako przecięcie elipsoid. ${\displaystyle Q}$${\displaystyle k}$

${\ Displaystyle \ min _ {\ kapelusz {x}} \ max _ {x} \ lewo \ {\ lewo \ | {\ kapelusz {x}} -x \ po prawej \ | ^ {2}: f_ {i} ( x)\leq 0,0\leq i\leq k\prawo\}}$

z

${\ Displaystyle f_ {i} (x) = x ^ {T} Q_ {i} x + 2 g_ {i} ^ {T} x + d_ {i} \ równoważnik 0,0 \ równoważnik i \ równoważnik k. \, }$

Wprowadzając dodatkową zmienną macierzową , możemy zapisać problem wewnętrznej maksymalizacji centrum Czebyszewa jako: ${\ Displaystyle \ Delta = xx ^ {T}}$

${\ Displaystyle \ min _ {\ kapelusz {x}} \ max _ {(\ delta, x) \ w G} \ lewo \ {\ lewo \ | {\ kapelusz {x}} \ po prawej \ | ^ {2} -2{\hat {x}}^{T}x+\nazwa operatora {Tr} (\Delta )\right\}}$

gdzie jest operator śledzenia i ${\ Displaystyle \ Operatorname {Tr} (\ cdot)}$

${\ Displaystyle G = \ lewo \ {(\ delta, x): {\ rm {f}} _ {i} (\ delta, x) \ równoważnik 0,0 \ równoważnik ja \ równoważnik k \ delta = xx ^ {T}\prawo\}}$

${\ Displaystyle f_ {i} (\ Delta, x) = \ operatorname {Tr} (Q_ {i} \ Delta) + 2g_ {i} ^ {T} x + d_ {i}.}$

Relaksując nasze wymagania poprzez wymaganie , tj. gdzie jest zbiór dodatnich macierzy półokreślonych i zmieniając kolejność od min max do max min (więcej szczegółów w odnośnikach), problem optymalizacji można sformułować jako: ${\ Displaystyle \ Delta}$${\ Displaystyle \ Delta \ geq xx ^ {T}}$${\ Displaystyle \ Delta -xx ^ {T} \ w S_ {+}}$${\displaystyle S_{+}}$

${\ Displaystyle RCC = \ max _ {(\ Delta, x) \ w {T}} \ lewo \ {- \ lewo \ | x \ prawo \ | ^ {2} + \ operatorname {Tr} (\ Delta) \ Prawidłowy\}}$

z

${\ Displaystyle {T} = \ lewo \ {(\ delta, x): {\ rm {{f} _ {i} (\ delta, x) \ równoważnik 0,0 \ równoważnik ja \ równoważnik k \ delta \ geq xx^{T}}}\right\}.}$

Ten ostatni wypukły problem optymalizacji jest znany jako zrelaksowane centrum Czebyszewa (RCC). RCC ma następujące ważne właściwości:

• RCC to górna granica dokładnego centrum Czebyszewa.
• RCC jest wyjątkowy.
• RCC jest wykonalne.

Ograniczone najmniejsze kwadraty

Można wykazać, że dobrze znany problem najmniejszych kwadratów z ograniczeniami (CLS) jest rozluźnioną wersją centrum Czebyszewa.

Oryginalny problem CLS można sformułować jako:

${\ Displaystyle {\ kapelusz {x}} _ {CLS} = \ nazwa operatora {*} {\ arg \ min} _ {x \ w C} \ po lewej \ | y-Ax \ po prawej \ | ^ {2}}$

z

${\ Displaystyle {C} = \ lewo \ {x: f_ {i} (x) = x ^ {T} Q_ {i} x + 2 g_ {i} ^ {T} x + d_ {i} \ równoważnik 0, 1\leq i\leq k\prawo\}}$

${\ Displaystyle Q_ {i} \ geq 0, g_ {i} \ w R ^ {m} d_ {i} \ w R.}$

Można wykazać, że ten problem jest równoznaczny z następującym problemem optymalizacyjnym:

${\ Displaystyle \ max _ {(\ Delta {x}) \ w {V}} \ lewo \ {{- \ lewo \ | {x} \ prawo \ | ^ {2} + \ nazwa operatora {Tr} (\ Delta )}\prawo\}}$

z

${\ Displaystyle V = \ lewo \ {{\ zacząć {tablicę} {c} (\ delta, x): x \ w 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\}.}$

Widać, że problemem tym jest rozluźnienie ośrodka Czebyszewa (choć inne niż opisane powyżej RCC).

RCC a CLS

Zestaw rozwiązań dla RCC jest również rozwiązaniem dla CLS, a więc . Oznacza to, że oszacowanie CLS jest rozwiązaniem luźniejszej relaksacji niż RCC. Stąd CLS jest górną granicą RCC , która jest górną granicą rzeczywistego centrum Czebyszewa. ${\displaystyle (x,\delta)}$${\ Displaystyle T \ w V}$

Modelowanie ograniczeń

Ponieważ zarówno RCC, jak i CLS opierają się na rozluźnieniu rzeczywistego zbioru wykonalności , forma, w której jest zdefiniowana, wpływa na jego złagodzone wersje. To oczywiście wpływa na jakość estymatorów RCC i CLS. Jako prosty przykład rozważmy liniowe ograniczenia pudełkowe: ${\displaystyle Q}$${\displaystyle Q}$

${\ Displaystyle l \ leq a ^ {T} x \ leq u}$

który można alternatywnie zapisać jako

${\ Displaystyle (a ^ {T} xl) (a ^ {T} xu) \ równa 0.}$

Okazuje się, że pierwsza reprezentacja daje estymator górnej granicy dla drugiej, stąd jej użycie może drastycznie obniżyć jakość obliczonego estymatora.

Ten prosty przykład pokazuje nam, że należy zwrócić szczególną uwagę na sformułowanie ograniczeń, gdy stosuje się rozluźnienie obszaru wykonalności.

Problem programowania liniowego

Problem ten można sformułować jako problem programowania liniowego , pod warunkiem, że obszar Q jest przecięciem skończenie wielu hiperpłaszczyzn. Mając wielotop, Q, zdefiniowany w następujący sposób, można go rozwiązać za pomocą następującego programu liniowego.

${\ Displaystyle Q = \ {x \ w R ^ {n}: Ax \ leq b \}}$

${\ Displaystyle {\ zacząć {wyrównany} & \ max & R \ \ & {\ tekst {st}} i & A_ {i} x + \ | A_ {i} \ | r \ leq b_ {i} \ \ & {\ tekst { i}}&&r\geq 0\end{wyrównany}}}$

Zobacz też

• Kula ograniczająca
• Problem z najmniejszym okręgiem
• Okrąg opisany (obejmuje środek okręgu )
• Centrum (geometria)
• Centroid

Bibliografia

• YC Eldar, A. Beck i M. Teboulle, „A Minimax Chebyshev Estimator for Bounded Error Estimation”, IEEE Trans. Proces sygnałowy, 56(4): 1388-1397 (2007).
• A. Beck i YC Eldar, „Regularyzacja w regresji z ograniczonym hałasem: podejście centrum Czebyszewa”, SIAM J. Matrix Anal. Zał. 29 (2): 606–625 (2007).