Эллипсоид Джона

^{Внешний эллипсоид Лёвнера–Джона ,} содержащий множество точек в R2

В математике эллипсоид Джона или эллипсоид Лёвнера–Джона E ( K ), связанный с выпуклым телом K в n - мерном евклидовом пространстве R ^{n ,} может относиться к n -мерному эллипсоиду максимального объема , содержащемуся в K , или к эллипсоиду минимального объема, содержащему K .

Часто эллипсоид минимального объема называют эллипсоидом Лёвнера , а эллипсоид максимального объема — эллипсоидом Джона (хотя Джон работал с эллипсоидом минимального объема в своей оригинальной статье). ^[1] Также можно называть описанный эллипсоид минимального объема внешним эллипсоидом Лёвнера–Джона , а вписанный эллипсоид максимального объема — внутренним эллипсоидом Лёвнера–Джона . ^[2]

Немецко-американский математик Фриц Джон доказал в 1948 году, что каждое выпуклое тело в R ⁿ описывается уникальным эллипсоидом минимального объема, и что расширение этого эллипсоида в 1/ n раз содержится внутри выпуклого тела. ^[3] То есть внешний эллипсоид Лоунера-Джона больше внутреннего не более чем в n раз . Для сбалансированного тела этот раз можно уменьшить до . ${\displaystyle {\sqrt {n}}}$

Характеристики

Внутренний эллипсоид Лёвнера–Джона E ( K ) выпуклого тела K  ⊂  R ⁿ является замкнутым единичным шаром B в R ⁿ тогда и только тогда, когда B  ⊆  K и существует целое число m  ≥  n и, для i  = 1, ..., m , действительные числа c _i  > 0 и единичные векторы u _i  ∈  S ^{n −1}  ∩ ∂ K такие, что ^[4]

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

и для всех x  ∈  R ⁿ

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

Вычисление

В общем, вычисление эллипсоида Джона заданного выпуклого тела является сложной задачей. Однако для некоторых конкретных случаев известны явные формулы. Некоторые случаи особенно важны для метода эллипсоида . ^{[5] : 70–73}

Пусть E( A , a ) — эллипсоид в R ⁿ , определяемый матрицей A и центром a . Пусть c — ненулевой вектор в R ⁿ . Пусть E'( A , a , c ) — полуэллипсоид, полученный путем разрезания E( A , a ) в его центре с помощью гиперплоскости, определяемой c . Тогда эллипсоид Лоунера-Джона E'( A , a , c ) — это эллипсоид E( A' , a' ), определяемый следующим образом:

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

где b — вектор, определяемый формулой:

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

Аналогично существуют формулы для других сечений эллипсоидов, не обязательно проходящих через его центр.

Приложения

Вычисление эллипсоидов Лёвнера–Джона (и, в более общем смысле, вычисление множеств полиномиального уровня минимального объема, охватывающих множество) нашло множество применений в управлении и робототехнике . ^[6] В частности, вычисление эллипсоидов Лёвнера–Джона имеет приложения в обнаружении столкновений с препятствиями для робототехнических систем, где расстояние между роботом и его окружающей средой оценивается с использованием наилучшего соответствия эллипсоида. ^[7]

Эллипсоиды Лёвнера–Джона также использовались для аппроксимации оптимальной политики в задачах оптимизации портфеля с транзакционными издержками. ^[8]

Смотрите также

• Компакт Банаха – Мазура  - Концепция функционального анализа.
• Метод эллипсоида
• Эллипс Штейнера , частный случай внутреннего эллипсоида Лёвнера–Джона для треугольника.
• Толстый объект , связанный с радиусом наибольшего содержащегося в нем шара.

Ссылки

1. Гюлер, Осман; Гюртуна, Филиз (2012). «Симметрия выпуклых множеств и ее приложения к экстремальным эллипсоидам выпуклых тел». Методы и программное обеспечение оптимизации . 27 (4–5): 735–759. CiteSeerX  10.1.1.664.6067 . doi :10.1080/10556788.2011.626037. ISSN  1055-6788. S2CID  2971340.
2. Бен-Тал, А. (2001). Лекции по современной выпуклой оптимизации: анализ, алгоритмы и инженерные приложения. Немировский, Аркадий Семенович. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. ISBN 0-89871-491-5. OCLC  46538510.
3. Джон, Фриц. «Экстремальные задачи с неравенствами в качестве вспомогательных условий». Исследования и эссе, представленные Р. Куранту в день его 60-летия , 8 января 1948 г., 187—204. Interscience Publishers, Inc., Нью-Йорк, штат Нью-Йорк, 1948. OCLC  1871554 MR 30135
4. Болл, Кит М. (1992). «Эллипсоиды максимального объема в выпуклых телах». Geom. Dedicata . 41 (2): 241–250. arXiv : math/9201217 . doi :10.1007/BF00182424. ISSN  0046-5755. S2CID  18330466.
5. Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, г-н  1261419
6. Даббене, Фабрицио; Энрион, Дидье; Лагоа, Константино М. (2017). «Простые аппроксимации полуалгебраических множеств и их приложения к управлению». Automatica . 78 : 110–118. arXiv : 1509.04200 . doi :10.1016/j.automatica.2016.11.021. S2CID  5778355.
7. Раймон, Элон; Бойд, Стивен (1997). «Обнаружение столкновений с препятствиями с использованием наилучшего соответствия эллипсоида». Журнал интеллектуальных и робототехнических систем . 18 (2): 105–126. doi :10.1023/A:1007960531949. S2CID  10505238.
8. Шен, Вэйвэй; Ван, Цзюнь (2015). «Оптимизация портфеля с учетом транзакционных издержек с помощью быстрой аппроксимации эллипсоида Лоунера-Джона» (PDF) . Труды конференции AAAI по искусственному интеллекту . 29 : 1854–1860. doi :10.1609/aaai.v29i1.9453. S2CID  14746495. Архивировано из оригинала (PDF) 2017-01-16.

• Гарднер, Ричард Дж. (2002). «Неравенство Брунна-Минковского». Bull. Amer. Math. Soc. (NS) . 39 (3): 355–405 (электронный). doi : 10.1090/S0273-0979-02-00941-2 . ISSN  0273-0979.