Chebyshev centrum

I geometri är Chebyshev -centrum för en avgränsad uppsättning $Q$ med icke-tom inre mitten av kulan med minimal radie som omsluter hela uppsättningen ${\displaystyle Q} ,$ eller alternativt (och icke-ekvivalent) mitten av den största inskrivna kulan av $Q$ .

Inom området för parameteruppskattning försöker Chebyshevs centrummetod hitta en skattare ${\hat {x}}$ för $x$ givet genomförbarhetsuppsättningen $Q$ , så att ${\hat {x}}$ minimerar det värsta möjliga uppskattningsfelet för x (t.ex. bästa värsta fallet).

Matematisk representation

Det finns flera alternativa representationer för Chebyshev-centret. Betrakta mängden $Q$ och beteckna dess Chebyshev-centrum med ${\hat {x}}$ . ${\hat {x}}$ kan beräknas genom att lösa:

$\min _{{\hat {x}},r}\left\{r:\left\| {\hat {x}}-x\right\|^{2}\leq r,\forall x\in Q\right\}$

med avseende på den euklidiska normen $\|\cdot \|$ , eller alternativt genom att lösa:

$\operatorname {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\|^ {2}.$

numeriskt optimeringsproblem att hitta Chebyshev-centret . Till exempel, i den andra representationen ovan, är den inre maximeringen icke-konvex om mängden Q inte är konvex .

Egenskaper

I inre produktutrymmen och tvådimensionella utrymmen, om $Q$ är stängd, avgränsad och konvex, så är Chebyshev-centrum i $Q$ . Med andra ord kan sökningen efter Chebyshev-centret utföras inuti $Q$ utan förlust av allmänhet.

I andra utrymmen kanske Chebyshev-centrum inte är i $Q$ , även om $Q$ är konvex. Till exempel, om $Q$ är tetraedern som bildas av det konvexa skrovet av punkterna (1,1,1), (-1,1,1), (1,-1,1) och (1, 1,-1), beräkna Chebyshev-centret med ${\displaystyle \ell _{\infty }}-$ normen

$0=\operatörsnamn {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\ |_{\infty }^{2}.$

Avslappnat Chebyshev centrum

Betrakta fallet där mängden $Q$ kan representeras som skärningspunkten mellan $k$ ellipsoider.

$\min _{\hat {x}}\max _{x}\left\{\ vänster\|{\hat {x}}-x\right\|^{2}:f_{i}(x)\leq 0,0\leq i\leq k\right\}$

med

$f_{i}(x)=x^{T}Q_{i}x+2g_{i}^{T}x+d_{i}\leq 0,0\leq i\leq k.\,$

Genom att introducera en extra matrisvariabel $\Delta =xx^{T}$ kan vi skriva det inre maximeringsproblemet för Chebyshev-centret som:

$\min _{\hat {x}}\max _{(\Delta ,x)\in G}\left\{\left\|{\hat {x}}\right\|^{2}-2{\hat {x}}^{T}x+\operatörsnamn {Tr} ( \Delta )\right\}$

där $\operatorname {Tr} (\cdot )$ är spårningsoperatorn och

$G=\left\{(\Delta ,x):{\rm {f }}_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta =xx^{T}\right\}$

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

Att slappna av vårt krav på $\Delta$ genom att kräva ${\displaystyle \Delta \geq xx^{T}},$ dvs $\Delta -xx^{ T}\in S_{+}$ där $S_{+}$ är uppsättningen positiva semidefinita matriser , och ändra ordningen på min max till max min (se referenserna för mer information), optimeringsproblemet kan formuleras som:

$RCC=\max _{(\Delta ,x)\in {T}}\left\{ -\left\|x\right\|^{2}+\operatörsnamn {Tr} (\Delta )\right\}$

med

${T}=\left\{(\Delta ,x):f_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta \geq xx^{T}\ höger\}.$

Detta sista konvexa optimeringsproblem är känt som det avslappnade Chebyshev-centret (RCC). RCC har följande viktiga egenskaper:

• RCC är en övre gräns för det exakta Chebyshev-centret.
• RCC är unik.
• RCC är genomförbart.

Begränsade minsta kvadrater

Det kan visas att det välkända problemet med begränsade minsta kvadrater (CLS) är en avslappnad version av Chebyshev-centret.

Det ursprungliga CLS-problemet kan formuleras som:

${\hat {x}}_{CLS}=\operatörsnamn {*} {\arg \min }_{x \in C}\left\|y-Ax\right\|^{2}$

med

${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}\geq 0,g_{i}\in R^{m},d_{i}\in R.$

Det kan visas att detta problem motsvarar följande optimeringsproblem:

$\max _{(\Delta ,{x})\in {V}}\left\{{-\left \|{x}\right\|^{2}+\operatörsnamn {Tr} (\Delta )}\right\}$

med

$V=\left\{{\begin{array}{c}(\Delta ,x):x\in C{\rm {}}\\\operatörsnamn {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\}.$

Man kan se att detta problem är en avslappning av Chebyshev-centret (även om det är annorlunda än RCC som beskrivs ovan).

RCC vs. CLS

En lösningsuppsättning $(x,\Delta )$ för RCC är också en lösning för CLS, och därmed $T\in V$ . Detta innebär att CLS-uppskattningen är lösningen för en lösare relaxation än den för RCC. Därför är CLS en övre gräns för RCC, vilket är en övre gräns för det verkliga Chebyshev-centret.

Modelleringsbegränsningar

Eftersom både RCC och CLS är baserade på relaxering av den verkliga genomförbarhetsuppsättningen ${\displaystyle Q}, påverkar$ formen i vilken $Q$ definieras dess avslappnade versioner. Detta påverkar givetvis kvaliteten på RCC- och CLS-uppskattningarna. Som ett enkelt exempel betrakta de linjära boxbegränsningarna:

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

som alternativt kan skrivas som

$(a^{T}xl)(a^{T}xu)\leq 0.$

Det visar sig att den första representationen resulterar med en övre gräns estimator för den andra, varför användning av den kan dramatiskt minska kvaliteten på den beräknade estimatorn.

Detta enkla exempel visar oss att stor noggrannhet bör ägnas åt formuleringen av begränsningar när uppluckring av genomförbarhetsregionen används.

Linjärt programmeringsproblem

Detta problem kan formuleras som ett linjärt programmeringsproblem , förutsatt att regionen Q är en skärning av ändligt många hyperplan. Givet en polytop, Q, definierad enligt följande, kan den lösas via följande linjära program.

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

${\begin{aligned}&\max _{r,{\hat {x}}}&&r\\&{\text{st} }&&a_{i}{\hat {x}}+\|a_{i}\|r\leq b_{i}\\&{\text{and}}&&r\geq 0\end{aligned}}$

Se även

• Avgränsande sfär
• Problem med minsta cirkel
• Omskriven cirkel (täcker omkretscentrum )
• Centrum (geometri)
• Centroid

• YC Eldar, A. Beck och M. Teboulle, " A Minimax Chebyshev Estimator for Bounded Error Estimation," IEEE Trans. Signal Process., 56(4): 1388–1397 (2007).
• A. Beck och YC Eldar, "Regularization in Regression with Bounded Noise: A Chebyshev Center Approach," SIAM J. Matrix Anal. Appl. 29 (2): 606–625 (2007).