Elipsoide de juan

Elipsoide exterior de Löwner-John que contiene un conjunto de puntos en R ²

En matemáticas , el elipsoide de John o elipsoide de Löwner–John E ( K ) asociado a un cuerpo convexo K en el espacio euclidiano n -dimensional R n puede ^referirse al elipsoide n -dimensional de volumen máximo contenido dentro de K o al elipsoide de volumen mínimo que contiene a K .

A menudo, el elipsoide de volumen mínimo se denomina elipsoide de Löwner y el elipsoide de volumen máximo se denomina elipsoide de John (aunque John trabajó con el elipsoide de volumen mínimo en su artículo original). ^[1] También se puede hacer referencia al elipsoide circunscrito de volumen mínimo como elipsoide de Löwner–John exterior y al elipsoide inscrito de volumen máximo como elipsoide de Löwner–John interior . ^[2]

El matemático germano-estadounidense Fritz John demostró en 1948 que cada cuerpo convexo en R ⁿ está circunscrito por un único elipsoide de volumen mínimo, y que la dilatación de este elipsoide por el factor 1/ n está contenida dentro del cuerpo convexo. ^[3] Es decir, el elipsoide de Lowner-John exterior es mayor que el interior por un factor de como máximo n . Para un cuerpo equilibrado , este factor se puede reducir a . ${\displaystyle {\sqrt {n}}}$

Propiedades

El elipsoide interior de Löwner-John E ( K ) de un cuerpo convexo K  ⊂  R ⁿ es una bola unitaria cerrada B en R ⁿ si y solo si B  ⊆  K y existe un entero m  ≥  n y, para i  = 1, ..., m , números reales c _i  > 0 y vectores unitarios u _i  ∈  S ^{n −1}  ∩ ∂ K tales que ^[4]

${\displaystyle \sum _{i=1}^{m}c_{i}u_{i}=0}$

y, para todo x  ∈  R ⁿ

${\displaystyle x=\sum _{i=1}^{m}c_{i}(x\cdot u_{i})u_{i}.}$

Cálculo

En general, calcular el elipsoide de John de un cuerpo convexo dado es un problema difícil. Sin embargo, para algunos casos específicos, se conocen fórmulas explícitas. Algunos casos son particularmente importantes para el método del elipsoide . ^{[5] : 70–73}

Sea E( A , a ) un elipsoide en R ⁿ , definido por una matriz A y centro a . Sea c un vector distinto de cero en R ⁿ . Sea E'( A , a , c ) el semielipsoide derivado de cortar E( A , a ) en su centro utilizando el hiperplano definido por c . Entonces, el elipsoide de Lowner-John de E'( A , a , c ) es un elipsoide E( A' , a' ) definido por:

${\displaystyle a'=a-{\frac {1}{n+1}}b}$ ${\displaystyle A'={\frac {n^{2}}{n^{2}-1}}\left(A-{\frac {2}{n+1}}bb^{T}\right)}$

donde b es un vector definido por:

${\displaystyle b={\frac {1}{\sqrt {c^{T}Ac}}}Ac}$

De manera similar, existen fórmulas para otras secciones de elipsoides, no necesariamente a través de su centro.

Aplicaciones

El cálculo de elipsoides de Löwner-John (y en general, el cálculo de conjuntos de nivel polinomial de volumen mínimo que encierran un conjunto) ha encontrado muchas aplicaciones en control y robótica . ^[6] En particular, el cálculo de elipsoides de Löwner-John tiene aplicaciones en la detección de colisiones de obstáculos para sistemas robóticos, donde la distancia entre un robot y su entorno circundante se estima utilizando un ajuste óptimo de elipsoide. ^[7]

Los elipsoides de Löwner-John también se han utilizado para aproximar la política óptima en problemas de optimización de cartera con costos de transacción. ^[8]

Véase también

• Banach-Mazur compactum  - Concepto en análisis funcional
• Método del elipsoide
• Elipse interna de Steiner , caso especial del elipsoide interno de Löwner-John para un triángulo.
• Objeto gordo , relacionado con el radio de la bola más grande contenida.

Referencias

1. Güler, Osman; Gürtuna, Filiz (2012). "Simetría de conjuntos convexos y sus aplicaciones a los elipsoides extremos de cuerpos convexos". Métodos de optimización y software . 27 (4–5): 735–759. CiteSeerX  10.1.1.664.6067 . doi :10.1080/10556788.2011.626037. ISSN  1055-6788. S2CID  2971340.
2. Ben-Tal, A. (2001). Lecciones sobre optimización convexa moderna: análisis, algoritmos y aplicaciones de ingeniería. Nemirovskiĭ, Arkadiĭ Semenovich. Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 0-89871-491-5.OCLC 46538510  .
3. John, Fritz. "Problemas extremos con desigualdades como condiciones subsidiarias". Estudios y ensayos presentados a R. Courant en su 60.º cumpleaños , 8 de enero de 1948, 187-204. Interscience Publishers, Inc., Nueva York, NY, 1948. OCLC  1871554 MR 30135
4. Ball, Keith M. (1992). "Elipsoides de volumen máximo en cuerpos convexos". Geom. Dedicata . 41 (2): 241–250. arXiv : math/9201217 . doi :10.1007/BF00182424. ISSN  0046-5755. S2CID  18330466.
5. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, Sr.  1261419
6. Dabbene, Fabrizio; Henrion, Didier; Lagoa, Constantino M. (2017). "Aproximaciones simples de conjuntos semialgebraicos y sus aplicaciones al control". Automatica . 78 : 110–118. arXiv : 1509.04200 . doi :10.1016/j.automatica.2016.11.021. S2CID  5778355.
7. Rimon, Elon; Boyd, Stephen (1997). "Detección de colisiones de obstáculos utilizando el mejor ajuste elipsoide". Revista de sistemas inteligentes y robóticos . 18 (2): 105–126. doi :10.1023/A:1007960531949. S2CID  10505238.
8. Shen, Weiwei; Wang, Jun (2015). "Optimización de carteras teniendo en cuenta los costes de transacción mediante una aproximación rápida de elipsoide de Lowner-John" (PDF) . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 29 : 1854–1860. doi :10.1609/aaai.v29i1.9453. S2CID  14746495. Archivado desde el original (PDF) el 16 de enero de 2017.

• Gardner, Richard J. (2002). "La desigualdad de Brunn-Minkowski". Bull. Amer. Math. Soc. (NS) . 39 (3): 355–405 (electrónico). doi : 10.1090/S0273-0979-02-00941-2 . ISSN  0273-0979.