Чебышев центр

В геометрии чебышёвский центр ограниченного множества $Q$ имеющий непустую внутреннюю часть, является центром шара минимального радиуса, охватывающего все множество. $Q$ или, альтернативно (и неэквивалентно), центр наибольшего вписанного шара $Q$ . ^[1]

В области оценки параметров подход центра Чебышева пытается найти оценщик ${\hat {x}}$ для $x$ учитывая набор осуществимых возможностей $Q$ , такой, что ${\hat {x}}$ минимизирует наихудшую возможную ошибку оценки x (например, лучший худший случай).

Математическое представление

Существует несколько альтернативных представлений чебышевского центра.Рассмотрим набор $Q$ и обозначим его чебышевский центр через ${\hat {x}}$ . ${\hat {x}}$ можно вычислить, решив:

\min _{{\hat {x}},r}\left\{r:\left\|{\hat {x}}-x\right\|^{2}\leq r,\forall x\in Q\right\}

относительно евклидовой нормы $\|\cdot \|$ или, альтернативно, решив:

\operatorname {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\|^{2}.

^[1]

Несмотря на эти свойства, нахождение центра Чебышева может оказаться сложной задачей численной оптимизации . Например, во втором представлении выше внутренняя максимизация невыпуклая, если множество Q не является выпуклым .

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

В пространствах внутреннего продукта и двумерных пространствах, если $Q$ замкнуто, ограничено и выпукло, то чебышевский центр находится в $Q$ . Другими словами, поиск центра Чебышева можно вести внутри $Q$ без потери общности. ^[2]

В других пространствах Чебышевского центра может не быть. $Q$ , даже если $Q$ является выпуклым. Например, если $Q$ — тетраэдр, образованный выпуклой оболочкой точек (1,1,1), (-1,1,1), (1,-1,1) и (1,1,-1), затем вычисление Чебышева центр с помощью $\ell _{\infty }$ норма дает ^[3]

0=\operatorname {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\|_{\infty }^{2}.

Расслабляющий центр Чебышева

Рассмотрим случай, когда множество $Q$ можно представить как пересечение $k$ эллипсоиды.

\min _{\hat {x}}\max _{x}\left\{\left\|{\hat {x}}-x\right\|^{2}:f_{i}(x)\leq 0,0\leq i\leq k\right\}

с

f_{i}(x)=x^{T}Q_{i}x+2g_{i}^{T}x+d_{i}\leq 0,0\leq i\leq k.\,

Введя дополнительную матричную переменную $\Delta =xx^{T}$ , мы можем записать внутреннюю задачу максимизации центра Чебышева как:

\min _{\hat {x}}\max _{(\Delta ,x)\in G}\left\{\left\|{\hat {x}}\right\|^{2}-2{\hat {x}}^{T}x+\operatorname {Tr} (\Delta )\right\}

где $\operatorname {Tr} (\cdot )$ является оператором трассировки и

G=\left\{(\Delta ,x):{\rm {f}}_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta =xx^{T}\right\}

f_{i}(\Delta ,x)=\operatorname {Tr} (Q_{i}\Delta )+2g_{i}^{T}x+d_{i}.

Ослабление нашего спроса на $\Delta$ требуя $\Delta \geq xx^{T}$ , то есть $\Delta -xx^{T}\in S_{+}$ где $S_{+}$ представляет собой набор положительных полуопределенных матриц , и меняя порядок min max на max min (более подробную информацию см. в ссылках), задачу оптимизации можно сформулировать как:

RCC=\max _{(\Delta ,x)\in {T}}\left\{-\left\|x\right\|^{2}+\operatorname {Tr} (\Delta )\right\}

с

{T}=\left\{(\Delta ,x):f_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta \geq xx^{T}\right\}.

Эта последняя задача выпуклой оптимизации известна как расслабленный центр Чебышева (RCC).ПКР обладает следующими важными свойствами:

RCC является верхней границей точного центра Чебышева.
РЦК уникален.
ПКР возможен.

Ограниченные наименьшие квадраты

Можно показать, что известная задача наименьших квадратов с ограничениями (CLS) представляет собой ослабленную версию центра Чебышева. ^{[ нужна ссылка ]}

Исходную задачу CLS можно сформулировать так:

{\hat {x}}_{CLS}=\operatorname {*} {\arg \min }_{x\in C}\left\|y-Ax\right\|^{2}

с

{C}=\left\{x:f_{i}(x)=x^{T}Q_{i}x+2g_{i}^{T}x+d_{i}\leq 0,1\leq i\leq k\right\}

Q_{i}\geq 0,g_{i}\in R^{m},d_{i}\in R.

Можно показать, что эта задача эквивалентна следующей задаче оптимизации:

\max _{(\Delta ,{x})\in {V}}\left\{{-\left\|{x}\right\|^{2}+\operatorname {Tr} (\Delta )}\right\}

с

V=\left\{{\begin{array}{c}(\Delta ,x):x\in C{\rm {}}\\\operatorname {Tr} (A^{T}A\Delta )-2y^{T}A^{T}x+\left\|y\right\|^{2}-\rho \leq 0,{\rm {{}\Delta \geq xx^{T}}}\\\end{array}}\right\}.

Видно, что эта проблема представляет собой релаксацию центра Чебышева (хотя и отличается от описанного выше ПКР).

RCC против CLS

Набор решений $(x,\Delta )$ ибо ПКР - это тоже решение для СЛС, а значит $T\in V$ .Это означает, что оценка CLS является решением более слабой релаксации, чем оценка RCC.Следовательно, CLS является верхней оценкой для RCC , которая является верхней оценкой для реального чебышевского центра.

Ограничения моделирования

Поскольку и RCC, и CLS основаны на смягчении реального набора реализуемых возможностей. $Q$ , форма, в которой $Q$ определено, влияет на его расслабленные версии. Это, конечно, влияет на качество оценщиков RCC и CLS.В качестве простого примера рассмотрим ограничения линейного блока:

l\leq a^{T}x\leq u

что альтернативно можно записать как

(a^{T}x-l)(a^{T}x-u)\leq 0.

Оказывается, что первое представление дает оценку верхней границы для второго, поэтому его использование может значительно снизить качество вычисляемой оценки.

Этот простой пример показывает нам, что при использовании ослабления области выполнимости следует уделять большое внимание формулированию ограничений.

Задача линейного программирования

Эту задачу можно сформулировать как задачу линейного программирования при условии, что область Q является пересечением конечного числа гиперплоскостей. ^[4] Учитывая многогранник Q, определенный следующим образом, его можно решить с помощью следующей линейной программы.

Q=\{x\in R^{n}:Ax\leq b\}

{\begin{aligned}&\max _{r,{\hat {x}}}&&r\\&{\text{s.t.}}&&a_{i}{\hat {x}}+\|a_{i}\|r\leq b_{i}\\&{\text{and}}&&r\geq 0\end{aligned}}

См. также

Ограничивающая сфера
Задача наименьшего круга
Описанная окружность (охватывает центр описанной окружности )
Центр (геометрия)
центроид

Ссылки

^ Перейти обратно: ^а ^б Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 октября 2011 г.
^ Амир, Дэн (1984). «Наилучшее одновременное приближение (центры Чебышева)». Международная серия по вычислительной математике / Международная серия по вычислительной математике / Международная серия по численному анализу . Биркхойзер. стр. 19–35. ISBN 9783034862530 .
^ Даббене, Фабрицио; Снайер, Марио; Темпо, Роберто (август 2014 г.). «Вероятностная оптимальная оценка с равномерно распределенным шумом». Транзакции IEEE при автоматическом управлении . 59 (8): 2113–2127. дои : 10.1109/tac.2014.2318092 . S2CID 17857976 .
^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 сентября 2014 г. Проверено 12 сентября 2014 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

Ю. К. Эльдар, А. Бек и М. Тебулль, «Минимаксный оценщик Чебышева для оценки ограниченной ошибки», IEEE Trans. Signal Process., 56(4): 1388–1397 (2007).
А. Бек и Ю. К. Эльдар, «Регуляризация в регрессии с ограниченным шумом: подход центра Чебышева», SIAM J. Matrix Anal. Прил. 29 (2): 606–625 (2007).

[BV-1] Перейти обратно: ^а ^б Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 октября 2011 г.

[2] Амир, Дэн (1984). «Наилучшее одновременное приближение (центры Чебышева)». Международная серия по вычислительной математике / Международная серия по вычислительной математике / Международная серия по численному анализу . Биркхойзер. стр. 19–35. ISBN 9783034862530 .

[3] Даббене, Фабрицио; Снайер, Марио; Темпо, Роберто (август 2014 г.). «Вероятностная оптимальная оценка с равномерно распределенным шумом». Транзакции IEEE при автоматическом управлении . 59 (8): 2113–2127. дои : 10.1109/tac.2014.2318092 . S2CID 17857976 .

[4] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 сентября 2014 г. Проверено 12 сентября 2014 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[1]

[2]

[3]

[4]