Chebyshev center

In geometry, the Chebyshev center of a bounded set ${\displaystyle Q}$ having non-empty interior is the center of the minimal-radius ball enclosing the entire set ${\displaystyle Q}$, or alternatively (and non-equivalently) the center of largest inscribed ball of ${\displaystyle Q}$.^[1]

In the field of parameter estimation, the Chebyshev center approach tries to find an estimator ${\displaystyle {\hat {x}}}$ for ${\displaystyle x}$ given the feasibility set ${\displaystyle Q}$, such that ${\displaystyle {\hat {x}}}$ minimizes the worst possible estimation error for x (e.g. best worst case).

There exist several alternative representations for the Chebyshev center. Consider the set ${\displaystyle Q}$ and denote its Chebyshev center by ${\displaystyle {\hat {x}}}$. ${\displaystyle {\hat {x}}}$ can be computed by solving:

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

with respect to the Euclidean norm${\displaystyle \|\cdot \|}$, or alternatively by solving:

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

Despite these properties, finding the Chebyshev center may be a hard numerical optimization problem. For example, in the second representation above, the inner maximization is non-convex if the set Q is not convex.

In inner product spaces and two-dimensional spaces, if ${\displaystyle Q}$ is closed, bounded and convex, then the Chebyshev center is in ${\displaystyle Q}$. In other words, the search for the Chebyshev center can be conducted inside ${\displaystyle Q}$without loss of generality.^[2]

In other spaces, the Chebyshev center may not be in ${\displaystyle Q}$, even if ${\displaystyle Q}$ is convex. For instance, if ${\displaystyle Q}$ is the tetrahedron formed by the convex hull of the points (1,1,1), (-1,1,1), (1,-1,1) and (1,1,-1), then computing the Chebyshev center using the ${\displaystyle \ell _{\infty }}$ norm yields^[3]

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

Consider the case in which the set ${\displaystyle Q}$ can be represented as the intersection of ${\displaystyle k}$ ellipsoids.

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

with

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

By introducing an additional matrix variable ${\displaystyle \Delta =xx^{T}}$, we can write the inner maximization problem of the Chebyshev center as:

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

where ${\displaystyle \operatorname {Tr} (\cdot )}$ is the trace operator and

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

Relaxing our demand on ${\displaystyle \Delta }$ by demanding ${\displaystyle \Delta \geq xx^{T}}$, i.e. ${\displaystyle \Delta -xx^{T}\in S_{+}}$ where ${\displaystyle S_{+}}$ is the set of positive semi-definite matrices, and changing the order of the min max to max min (see the references for more details), the optimization problem can be formulated as:

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

with

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

This last convex optimization problem is known as the relaxed Chebyshev center (RCC). The RCC has the following important properties:

• The RCC is an upper bound for the exact Chebyshev center.
• The RCC is unique.
• The RCC is feasible.

It can be shown that the well-known constrained least squares (CLS) problem is a relaxed version of the Chebyshev center.

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).