Centro Chebyshev

En geometría , el centro de Chebyshev de un conjunto acotado${\displaystyle Q}$El centro de la bola de radio mínimo que encierra todo el conjunto tiene un interior no vacío.${\displaystyle Q}$, o alternativamente (y no equivalentemente) el centro de la bola inscrita más grande de${\displaystyle Q}$. ^{[ 1 ]}

En el campo de la estimación de parámetros , el enfoque del centro de Chebyshev intenta encontrar un estimador.${\displaystyle {\hat {x}}}$para${\displaystyle x}$dado el conjunto de viabilidad${\displaystyle Q}$, de tal manera que${\displaystyle {\hat {x}}}$minimiza el peor error de estimación posible para x (por ejemplo, el mejor peor caso).

Existen varias representaciones alternativas para el centro de Chebyshev. Consideremos el conjunto${\displaystyle Q}$y denotar su centro de Chebyshev por${\displaystyle {\hat {x}}}$.${\displaystyle {\hat {x}}}$se puede calcular resolviendo:

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

con respecto a la norma euclidiana${\displaystyle \|\cdot \|}$o bien resolviendo:

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

A pesar de estas propiedades, encontrar el centro de Chebyshev puede ser un problema de optimización numérica difícil . Por ejemplo, en la segunda representación anterior, la maximización interna no es convexa si el conjunto Q no es convexo .

En espacios de producto interno y espacios bidimensionales, si${\displaystyle Q}$es cerrado, acotado y convexo, entonces el centro de Chebyshev está en${\displaystyle Q}$En otras palabras, la búsqueda del centro de Chebyshev puede realizarse dentro${\displaystyle Q}$sin pérdida de generalidad . ^{[ 2 ]}

En otros espacios, el centro Chebyshev puede no estar en ${\displaystyle Q}$, incluso si ${\displaystyle Q}$es convexa. Por ejemplo, si${\displaystyle Q}$es el tetraedro formado por la envoltura convexa de los puntos (1,1,1), (-1,1,1), (1,-1,1) y (1,1,-1), luego calculando el centro de Chebyshev usando el${\displaystyle \ell _{\infty }}$La norma produce ^{[ 3 ]}

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

Consideremos el caso en el que el conjunto${\displaystyle Q}$puede representarse como la intersección de${\displaystyle k}$elipsoides.

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

con

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

Al introducir una variable matricial adicional${\displaystyle \Delta =xx^{T}}$Podemos escribir el problema de maximización interna del centro de Chebyshev como:

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

dónde${\displaystyle \operatorname {Tr} (\cdot )}$es el operador de traza y

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

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

Relajando nuestra exigencia en${\displaystyle \Delta }$exigiendo${\displaystyle \Delta \geq xx^{T}}$, es decir${\displaystyle \Delta -xx^{T}\in S_{+}}$dónde${\displaystyle S_{+}}$es el conjunto de matrices semidefinidas positivas , y cambiando el orden de min max a max min (consulte las referencias para obtener más detalles), el problema de optimización se puede formular como:

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

con

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

Este último problema de optimización convexa se conoce como el centro de Chebyshev relajado (RCC). El RCC tiene las siguientes propiedades importantes:

• El RCC es un límite superior para el centro exacto de Chebyshev.
• El RCC es único.
• El RCC es factible.

Se puede demostrar que el conocido problema de mínimos cuadrados restringidos (CLS, por sus siglas en inglés) es una versión relajada del problema del centro de Chebyshev.

El problema CLS original se puede formular de la siguiente manera:

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

con

${\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\}}$

${\displaystyle Q_{i}\geq 0,g_{i}\in R^{m},d_{i}\in R.}$

Se puede demostrar que este problema es equivalente al siguiente problema de optimización:

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

con

${\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\}.}$

Se puede observar que este problema es una relajación del centro de Chebyshev (aunque diferente del RCC descrito anteriormente).

Un conjunto de soluciones${\displaystyle (x,\Delta )}$para el RCC también es una solución para el CLS y por lo tanto${\displaystyle T\in V}$Esto significa que la estimación CLS es la solución de una relajación menos restrictiva que la del RCC. Por lo tanto, la CLS es una cota superior para el RCC , que a su vez es una cota superior para el centro de Chebyshev real.

Dado que tanto el RCC como el CLS se basan en la relajación del conjunto de factibilidad real${\displaystyle Q}$, la forma en que${\displaystyle Q}$su definición afecta a sus versiones relajadas. Esto, por supuesto, afecta a la calidad de los estimadores RCC y CLS. Como ejemplo sencillo, consideremos las restricciones de caja lineales:

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

que alternativamente puede escribirse como

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

Resulta que la primera representación arroja un estimador de límite superior para la segunda, por lo que su uso puede disminuir drásticamente la calidad del estimador calculado.

Este sencillo ejemplo nos muestra que se debe prestar mucha atención a la formulación de las restricciones cuando se utiliza la relajación de la región de viabilidad.

Este problema puede formularse como un problema de programación lineal , siempre que la región Q sea una intersección de un número finito de hiperplanos. ^{[ 4 ]} Dado un politopo , Q, definido como sigue, entonces puede resolverse mediante el siguiente programa lineal.

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

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

• YC Eldar, A. Beck y M. Teboulle, "Un estimador de Chebyshev minimax para la estimación de errores acotados", IEEE Trans. Signal Process., 56(4): 1388–1397 (2007).
• A. Beck y YC Eldar, "Regularización en regresión con ruido acotado: un enfoque del centro de Chebyshev", SIAM J. Matrix Anal. Appl. 29 (2): 606–625 (2007).