Джон эллипсоид
В математике — эллипсоид Джона или эллипсоид Лёвнера–Джона E ( K ), сопоставленный выпуклому телу K в n - мерном евклидовом пространстве R. н может относиться к n -мерному эллипсоиду максимального объема, содержащемуся внутри K , или к эллипсоиду минимального объема, который содержит K .
Часто эллипсоид минимального объема называют эллипсоидом Лёвнера , а эллипсоид максимального объема называют эллипсоидом Джона (хотя Джон работал с эллипсоидом минимального объема в своей оригинальной статье). [1] Можно также назвать описанный эллипсоид минимального объема внешним эллипсоидом Лёвнера – Джона , а вписанный эллипсоид максимального объема - внутренним эллипсоидом Лёвнера – Джона . [2]
Немецко-американский математик Фриц Джон доказал в 1948 году, что каждое выпуклое тело в R н описан единственным эллипсоидом минимального объема и что расширение этого эллипсоида в 1/ n раз содержится внутри выпуклого тела. [3] То есть внешний эллипсоид Лоунера-Джона больше внутреннего не более чем в n раз . Для сбалансированного тела этот коэффициент можно уменьшить до .
Свойства [ править ]
Внутренний эллипсоид Лёвнера–Джона E ( K ) выпуклого тела K ⊂ R н — замкнутый единичный шар B в R н тогда и только тогда, когда B ⊆ K и существует целое число m ≥ n и для i = 1, ..., действительные m числа c i > 0 и единичные векторы u i ∈ S п -1 ∩ ∂ K такой, что [4]
и для всех x ∈ R н
Вычисление [ править ]
В общем, вычисление эллипсоида Джона заданного выпуклого тела является сложной задачей. Однако для некоторых конкретных случаев известны явные формулы. Некоторые случаи особенно важны для метода эллипсоидов . [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' ), определяемым следующим образом:
где b — вектор, определяемый следующим образом:
Аналогично существуют формулы и для других сечений эллипсоида, не обязательно через его центр.
Приложения [ править ]
Вычисление эллипсоидов Лёвнера-Джона (и, в более общем плане, вычисление полиномиальных множеств минимального объема, охватывающих набор) нашло множество приложений в управлении и робототехнике . [6] В частности, вычисление эллипсоидов Лёвнера – Джона находит применение в обнаружении столкновений с препятствиями в робототехнических системах, где расстояние между роботом и окружающей его средой оценивается с использованием наилучшего соответствия эллипсоида. [7]
Эллипсоиды Лёвнера – Джона также использовались для аппроксимации оптимальной политики в задачах оптимизации портфеля с транзакционными издержками. [8]
См. также [ править ]
- Компакт Банаха – Мазура - концепция функционального анализа.
- Эллипсоидный метод
- Эллипс Штейнера , частный случай внутреннего эллипсоида Лёвнера – Джона для треугольника.
- Толстый объект , соответствующий радиусу наибольшего содержащегося в нем шара.
Ссылки [ править ]
- ^ Гюлер, Осман; Гюртуна, Филиз (2012). «Симметрия выпуклых множеств и ее приложения к экстремальным эллипсоидам выпуклых тел» . Методы оптимизации и программное обеспечение . 27 (4–5): 735–759. CiteSeerX 10.1.1.664.6067 . дои : 10.1080/10556788.2011.626037 . ISSN 1055-6788 . S2CID 2971340 .
- ^ Бен-Тал, А. (2001). Лекции по современной выпуклой оптимизации: анализ, алгоритмы и инженерные приложения . Немировский Аркадий Семенович. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. ISBN 0-89871-491-5 . OCLC 46538510 .
- ^ Джон, Фриц. «Экстремальные задачи с неравенствами как вспомогательными условиями». Этюды и очерки, подаренные Р. Куранту к его 60-летию , 8 января 1948 г., 187—204. Interscience Publishers, Inc., Нью-Йорк, 1948 год. OCLC 1871554 МР 30135
- ^ Болл, Кейт М. (1992). «Эллипсоиды максимального объема в выпуклых телах». Геом. Дедиката . 41 (2): 241–250. arXiv : math/9201217 . дои : 10.1007/BF00182424 . ISSN 0046-5755 . S2CID 18330466 .
- ^ Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419
- ^ Даббене, Фабрицио; Анрион, Дидье; Лагоа, Константино М. (2017). «Простые аппроксимации полуалгебраических множеств и их приложения к управлению» . Автоматика . 78 : 110–118. arXiv : 1509.04200 . дои : 10.1016/j.automatica.2016.11.021 . S2CID 5778355 .
- ^ Римон, Илон; Бойд, Стивен (1997). «Обнаружение столкновений с препятствиями с использованием наилучшего соответствия эллипсоида». Журнал интеллектуальных и робототехнических систем . 18 (2): 105–126. дои : 10.1023/А:1007960531949 . S2CID 10505238 .
- ^ Шен, Вэйвэй; Ван, июнь (2015). «Оптимизация портфеля с учетом транзакционных издержек с помощью быстрого эллипсоидного приближения Лоунера-Джона» (PDF) . Материалы конференции AAAI по искусственному интеллекту . 29 : 1854–1860. дои : 10.1609/aaai.v29i1.9453 . S2CID 14746495 . Архивировано из оригинала (PDF) 16 января 2017 г.
- Гарднер, Ричард Дж. (2002). «Неравенство Брунна-Минковского» . Бык. амер. Математика. Соц. (НС) . 39 (3): 355–405 (электронный). дои : 10.1090/S0273-0979-02-00941-2 . ISSN 0273-0979 .