En geometría , el centro de Chebyshev de un conjunto acotadotener el interior no vacío es el centro de la bola de radio mínimo que encierra todo el conjunto, o alternativamente (y no equivalentemente) el centro de la bola inscrita más grande de . [1]
En el campo de la estimación de parámetros , el enfoque del centro de Chebyshev intenta encontrar un estimador por dado el conjunto de viabilidad , tal que minimiza el peor error de estimación posible para x (por ejemplo, el peor de los casos).
Representación matemática
Existen varias representaciones alternativas para el centro Chebyshev. Considere el conjunto y denotar su centro Chebyshev por . se puede calcular resolviendo:
o alternativamente resolviendo:
A pesar de estas propiedades, encontrar el centro de Chebyshev puede ser un difícil problema de optimización numérica . Por ejemplo, en la segunda representación anterior, la maximización interna no es convexa si el conjunto Q no es convexo .
Propiedades
En espacios interiores de productos y espacios bidimensionales, si es cerrado, acotado y convexo, entonces el centro de Chebyshev está en . En otras palabras, la búsqueda del centro Chebyshev se puede realizar dentrosin pérdida de generalidad. [2]
En otros espacios, el centro Chebyshev puede no estar en , incluso si es convexo. Por ejemplo, sies el tetraedro formado por el casco convexo de los puntos (1,1,1), (-1,1,1), (1, -1,1) y (1,1, -1), luego calculando el Chebyshev centro usando elrendimiento normal [3]
Centro Chebyshev relajado
Considere el caso en el que el conjunto se puede representar como la intersección de elipsoides.
con
Introduciendo una variable matricial adicional , podemos escribir el problema de maximización interna del centro de Chebyshev como:
dónde es el operador de rastreo y
Relajando nuestra demanda en exigiendo , es decir dónde es el conjunto de matrices semidefinidas positivas , y cambiando el orden del mínimo máximo al máximo mínimo (consulte las referencias para obtener más detalles), el problema de optimización se puede formular como:
con
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.
Mínimos cuadrados restringidos
Se puede demostrar que el conocido problema de mínimos cuadrados restringidos (CLS) es una versión relajada del centro de Chebyshev. [ cita requerida ]
El problema de CLS original se puede formular como:
con
Se puede demostrar que este problema es equivalente al siguiente problema de optimización:
con
Se puede ver que este problema es una relajación del centro de Chebyshev (aunque diferente al CCR descrito anteriormente).
RCC frente a CLS
Un conjunto de soluciones para el RCC es también una solución para el CLS, y por lo tanto . Esto significa que la estimación CLS es la solución de una relajación más floja que la del RCC. Por lo tanto, el CLS es un límite superior para el RCC , que es un límite superior para el centro real de Chebyshev.
Restricciones de modelado
Dado que tanto el RCC como el CLS se basan en la relajación del conjunto de factibilidad real , la forma en que se define afecta a sus versiones relajadas. Por supuesto, esto afecta la calidad de los estimadores RCC y CLS. Como ejemplo simple, considere las restricciones de caja lineal:
que alternativamente se puede escribir como
Resulta que la primera representación da como resultado un estimador de límite superior para la segunda, por lo que su uso puede disminuir drásticamente la calidad del estimador calculado.
Este simple ejemplo nos muestra que se debe prestar mucha atención a la formulación de restricciones cuando se usa la relajación de la región de factibilidad.
Problema de programación lineal
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 de la siguiente manera, puede resolverse mediante el siguiente programa lineal.
Ver también
Referencias
- ↑ a b Boyd, Stephen P .; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3. Consultado el 15 de octubre de 2011 .
- ^ Amir, Dan (1984). "Mejor Aproximación Simultánea (Centros Chebyshev)". Serie internacional de matemáticas numéricas / Internationale Schriftenreihe zur Numerischen Mathematik / Série internationale d'Analyse numérique . Birkhäuser. págs. 19–35. ISBN 9783034862530.
- ^ Dabbene, Fabrizio; Sznaier, Mario; Tempo, Roberto (agosto de 2014). "Estimación óptima probabilística con ruido distribuido uniformemente". Transacciones IEEE sobre control automático . 59 (8): 2113–2127. doi : 10.1109 / tac.2014.2318092 .
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 12 de septiembre de 2014 . Consultado el 12 de septiembre de 2014 .CS1 maint: copia archivada como título ( enlace )
- YC Eldar, A. Beck y M. Teboulle, "Un estimador Minimax Chebyshev para la estimación de errores acotados", IEEE Trans. Proceso de señales., 56 (4): 1388-1397 (2007).
- A. Beck y YC Eldar, "Regularización en regresión con ruido limitado: un enfoque de centro Chebyshev", SIAM J. Matrix Anal. Apl. 29 (2): 606–625 (2007).