В геометрии , то центр Чебышева ограниченного множестваимеющий непустую внутренность, является центром шара минимального радиуса, охватывающего все множество, или, альтернативно (и неэквивалентно) центр самого большого вписанного шара . [1]
В области оценки параметров подход центра Чебышева пытается найти оценку для учитывая набор технико-экономических обоснований , такое что минимизирует наихудшую возможную ошибку оценки для x (например, наихудший случай).
Математическое представление
Существует несколько альтернативных представлений чебышевского центра. Рассмотрим множество и обозначим его чебышёвский центр через . можно вычислить, решив:
или, альтернативно, решив:
Несмотря на эти свойства, поиск чебышевского центра может оказаться сложной задачей численной оптимизации . Например, во втором представлении выше внутренняя максимизация невыпукла, если множество Q не является выпуклым .
Характеристики
Во внутренних пространствах продукта и двумерных пространствах, если замкнуто, ограничено и выпукло, то чебышёвский центр лежит в . Другими словами, поиск чебышевского центра можно вести внутрине теряя общий смысл. [2]
В других местах Чебышевского центра может не быть. , даже если выпуклый. Например, если- тетраэдр, образованный выпуклой оболочкой точек (1,1,1), (-1,1,1), (1, -1,1) и (1,1, -1), то вычисление чебышевского центр с помощьюнормальная доходность [3]
Расслабленный чебышевский центр
Рассмотрим случай, когда множество можно представить как пересечение эллипсоиды.
с участием
Путем введения дополнительной матричной переменной , мы можем записать внутреннюю задачу максимизации чебышевского центра в виде:
где - оператор трассировки и
Ослабляя наш спрос на требуя , т.е. где - это набор положительных полуопределенных матриц , и при изменении порядка от min max до max min (см. ссылки для получения более подробной информации), задача оптимизации может быть сформулирована как:
с участием
Эта последняя задача выпуклой оптимизации известна как расслабленный чебышевский центр (RCC). ПКР обладает следующими важными свойствами:
- RCC - это верхняя граница точного центра Чебышева.
- РКЦ уникален.
- ПКР осуществима.
Метод наименьших квадратов с ограничениями
Можно показать, что хорошо известная задача наименьших квадратов с ограничениями (CLS) является ослабленной версией чебышевского центра. [ необходима цитата ]
Исходную проблему CLS можно сформулировать так:
с участием
Можно показать, что эта проблема эквивалентна следующей задаче оптимизации:
с участием
Видно, что это проблема релаксации чебышевского центра (хотя и отличная от описанной выше ПКР).
RCC против CLS
Набор решений для RCC также является решением для CLS, и, следовательно, . Это означает, что оценка CLS является решением более слабой релаксации, чем оценка RCC. Следовательно, CLS - это верхняя граница для RCC , которая является верхней границей для реального Чебышевского центра.
Ограничения моделирования
Поскольку как RCC, так и CLS основаны на ослаблении набора реальной осуществимости , форма, в которой определено, влияет на его расслабленные версии. Это, конечно, влияет на качество оценок RCC и CLS. В качестве простого примера рассмотрим ограничения линейного блока:
который в качестве альтернативы можно записать как
Оказывается, первое представление приводит к оценке верхней границы для второго, поэтому его использование может значительно снизить качество вычисляемой оценки.
Этот простой пример показывает нам, что следует уделять большое внимание формулировке ограничений, когда используется ослабление области выполнимости.
Задача линейного программирования
Эта проблема может быть сформулирована как задача линейного программирования при условии, что область Q является пересечением конечного числа гиперплоскостей. [4] Для многогранника Q, определенного следующим образом, его можно решить с помощью следующей линейной программы.
Смотрите также
Рекомендации
- ^ a b Бойд, Стивен П .; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3. Проверено 15 октября 2011 года .
- ^ Амир, Дэн (1984). «Наилучшее одновременное приближение (центры Чебышева)». International Series of Numerical Mathematics / Internationale Schriftenreihe zur Numerischen Mathematik / Série internationale d'Analyse numérique . Birkhäuser. С. 19–35. ISBN 9783034862530.
- ^ Даббене, Фабрицио; Снайер, Марио; Темпо, Роберто (август 2014). «Вероятностно-оптимальная оценка с равномерно распределенным шумом». IEEE Transactions по автоматическому контролю . 59 (8): 2113–2127. DOI : 10,1109 / tac.2014.2318092 .
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 12 сентября 2014 года . Проверено 12 сентября 2014 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- YC Eldar, A. Beck, и M. Teboulle, "Минимаксная оценка Чебышева для оценки ограниченной ошибки", IEEE Trans. Сигнальный процесс., 56 (4): 1388–1397 (2007).
- А. Бек и YC Эльдар, "Регуляризация в регрессии с ограниченным шумом: подход центра Чебышева", SIAM J. Matrix Anal. Прил. 29 (2): 606–625 (2007).