Просмотр кода страницы Геометрическая разность двух эллипсоидов. Внутренние и внешние оценки

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

Пусть $$ q \in \mathbb{R}^{n}, Q \in \mathbb{R}^{n \times n} $$ и $$Q$$ неотрицательно определена. Эллипсоидом $$\varepsilon (q, Q) $$ с центром q и матрицей Q называется выпуклое замкнутое множество точек $$\mathcal{R}^{n}$$, опорная функция $$\rho (l | \varepsilon (q, Q)$$ которого равна $$\langle l, q \rangle + \langle l, Ql \rangle^{\frac{1}{2}}$$.

В случае, когда центр $$q$$ не упоминается будем считать, что он находится в центре координат.<br>

Разностью двух эллипсоидов будем называть $$\mathcal{E}_{1} \dot{—} \mathcal{E}_{2}$$
\begin{gather*}
    \rho (l | \mathcal{E}_{1} \dot{—} \mathcal{E}_{2}) = conv( \rho(l | \mathcal{E}_{1}) - \rho (l | \mathcal{E}_{2} ))
\end{gather*}
== Внутренние эллипсоидальные оценки ==
Пусть $$Q_{2}$$ - положительно определена, а $$Q_{1}$$ - неотрицательно определенная матрицы. Для оценивания разности эллипсоидов $$\mathcal{E} (q_{2}, Q_{2}) \dot{—} \mathcal{E} (q_{21}, Q_{1})$$ введем некоторые обозначения. Введем семейство параметрических матриц
\begin{gather}
Q(p) = (1-p)Q_{2} - (1 - \frac{1}{p})Q_{1}.
\end{gather}
Также рассмотрим уравнение
\begin{gather}
det (Q_{2} - \lambda Q_{1}) = 0
\end{gather}
и обозначим корни этого уравнения
\begin{gather}
\lambda_{min} = \lambda_{1} \leqslant \lambda_{2} \leqslant \ldots \leqslant \lambda_{n} = \lambda_{max}, (\lambda_{1} > 0, lambda_{n} < \infty).
\end{gather}
Также обозначим
\begin{gather}
Pi^{+} = \left[ \lambda_{min}^{1/2}, \lambda_{max}^{1/2} \right], \\
Pi^{-} = Pi^{+} \cap (1, \lambda_{min}).
\end{gather}
'''Лемма 1'''
Пусть $$\mathcal{E} (Q_{1}) \subseteq \mathcal{E} (Q_{2})$$, тогда справедливы следующие утверждения:

* Эллипcоид $$\mathcal{E} (q_{2} - q_{1}, Q(p))$$ невырожденный тогда и только тогда, когда $$p \in (1, \lambda_{min})$$. Для таких $$p$$ эллипсоид является внутренней аппроксимацией разности $$\mathcal{E} (q_{2} - q_{1}, Q(p)) \subseteq \mathcal{E} (Q_{1}) \cdot{-} \mathcal{E} (Q_{2})$$

* Для фиксированного вектора $$l \in \mathbb{R}^{n}, ||l|| = 1$$ выражение
\begin{gather}
p = \langle l, Q_{1}l \rangle^{\frac{1}{2}} \langle l, Q_{2}l \rangle^{-\frac{1}{2}}
\end{gather} 
определяет параметр $$p$$. Если параметр $$p \in Pi^{-}$$, то
\begin{gather}
\rho(l|\mathcal{E} (q_{1} + q_{2},Q(p))) = \rho(l|\mathcal{E}  (q_{1},Q_{1}) + \mathcal{E} (q_{2},Q_{2})).
\end{gather}
Также верно обратное: при заданном параметре $$p \in Pi^{-}$$ существует вектор $$l \in \mathbb{R}^{n}, ||l|| = 1$$ который обеспечивает верность равенств.

'''Лемма 2'''
Пусть C положительно определенная симметричная матрица с элементами \( {c_{ij}} \).
Для фиксированного вектора $$l \in \mathbb{R}^{n}, ||l|| = 1$$ и предположим, что для некоторого $$m \in [0,n]$$ имеем
\begin{gather}
l_j = 0,\text{ }если\text{ } j \in \overline{1,m};\\
l_j \neq 0,\text{ }если\text{ } j = \overline{m+1,n}.
\end{gather}
Помимо этого будем считать, что $$\mathcal{E}_{1} = \mathcal{E}(0,Q_{1}), \mathcal{E}_{2} = \mathcal{E}(0,Q_{2})$$, а матрицы $$Q_{1}, Q_{2}, Q$$ диагональные. Если выполнено:
\begin{gather}
\mathcal{E}(0, Q) \subseteq \mathcal{E}(0, C) \subseteq \mathcal{E}_{1} \cdot{-} \mathcal{E}_{2},
\end{gather}
и 
\begin{gather}
\rho(l|\mathcal{E}(0, Q)) = \rho(l|\mathcal{E}_{1} \cdot{-} \mathcal{E}_{2}).
\end{gather}
Тогда 
\begin{gather}
c_{ij} = 0, \text{ для всех } i \neq j,\text{ } i \in \overline{m+1,n}.
\end{gather}

'''Лемма 3'''

Считаем эллипсоиды $$\mathcal{E}(0, C), \mathcal{E}_{1} = \mathcal{E}(0,Q_{1}), \mathcal{E}_{2} = \mathcal{E}(0,Q_{2})$$ невырожденными, а матрицы $$Q_{1}$$ и $$Q_{2}$$ диагональными. Также пусть задан вектор $$l \in \mathbb{R}^{n}, ||l|| = 1$$, параметр $$p$$ считается известным ввиду Леммы 1. В таком случае если эллипсоид корректно определен, тогда из следующих утверждений:
\begin{gather}
  \mathcal{E}(0, Q(-p)) \subseteq  \mathcal{E}(0, C) \subseteq \mathcal{E}_{1} cdot{-} \mathcal{E}_{2} 
\end{gather}
и
\begin{gather}
\rho(l|\mathcal{E}(0, Q(-p))) = \rho(l|\mathcal{E}_1 cdot{-} \mathcal{E}_2),
\end{gather}
следует
\begin{gather}
\mathcal{E}(0,Q(p)) = \mathcal{E}(0, C)\text{ и }p\in\Pi^{+} .
\end{gather}


'''Теорема 1'''
Предполагая, что $$\mathcal{E}_{2} = \mathcal{E}(q_{2}, Q_{2})\in int \mathcal{E}_{1} = \mathcal{E}(q_{1}, Q_{1})$$.
Тогда максимальное по включению множество, оценивающее разность $$ \mathcal{E}_{1} \cdot{-} \mathcal{E}_{2}$$, состоит из эллипсоидов вида 
\begin{gather}
 \mathcal{E}(q_{1} - q_{2}, Q(-p)),  p \in \Pi^{-}.
\end{gather}

'''Доказательство'''
Не ограничивая общности, ссылаясь на Лемму из первого раздела, мы можем предложить, что все центры эллипсоидов находятся в нуле, т.е.$$q_{1} = q_{2} = 0$$. <br> 
Пусть есть такой эллипсоид, что $$ \mathcal{E}(0, Q) \subseteq \mathcal{E}_{1} \cdot{-} \mathcal{E}_{2}$$.Найдем такой параметр $$p$$, что  для эллипсоида $$\mathcal{E}(0, Q(-p))$$ будет выполнено:
\begin{gather}
\mathcal{E}(0, Q) \subseteq \mathcal{E}(0, Q(-p)) \subseteq \mathcal{E}_{1} \cdot{-} \mathcal{E}_{2}.
\end{gather}
Мы можем считать, что $$\mathcal{E}(0, Q)$$ касательно к $$mathcal{E}_{1} \cdot{-} \mathcal{E}_{2}$$, и что будет существовать вектор $$l = \overline{l} \in \mathbb{R}^{n}, ||\overline {l}|| = 1$$, такой, что
\begin{gather}\label{eq1}
\rho(\overline l|\mathcal{E}(0, Q)) = \rho(\overline l|\mathcal{E}_{1} \cdot{-} \mathcal{E}_{2}).
\end{gather}
Возьмем $$\mathcal{E}(0, Q(- \overline{p}))$$, где
\begin{gather}
\overline{p} = \langle \overline{l}, Q_{1}\overline{l} \rangle^{\frac{1}{2}} \langle \overline{l}, Q_{2}\overline{l} \rangle^{-\frac{1}{2}}
\end{gather}
и докажем, что матрица $$\mathcal{E}(0, Q(- \overline{p}))$$ положительно определенная. Для этого определим матрицу
\begin{gather*}
D(p^{*}) = (1 + (p^{*})^{-1})Q + (1 + p^{*})Q_{2}
\end{gather*}
или
\begin{gather}\label{eq2}
Q = (1 - p^{-1})D(p^{*}) + (1 - p)Q_{2}
\end{gather}
где
\begin{gather*}
p^{*} = \langle \overline{l}, Q\overline{l} \rangle^{\frac{1}{2}} \langle \overline{l}, Q_{2}\overline{l} \rangle^{-\frac{1}{2}}
\end{gather*}
и
\begin{gather*}
p = p^{*} + 1.
\end{gather*}
Из Теоремы мы получаем
\begin{gather*}
\mathcal{E} (0, Q) + \mathcal{E}_{2} \subseteq \mathcal{E} (0, D(p^{*})) \subseteq \mathcal{E}_{1}
\end{gather*} 
или иначе $$ D(p^{*}) \leqslant Q_{1}$$. Более того,
\begin{gather}
\rho(\overline l|\mathcal{E}(0,  D(p^{*}))) =  \rho(\overline l|\mathcal{E}(0,  Q)) + \rho(\overline l|\mathcal{E}(0,  Q_{2})).
\end{gather}
Из \ref{eq1} получаем
\begin{gather*}
 \rho(\overline l|\mathcal{E}(0,  Q)) + \rho(\overline l|\mathcal{E}_{2}) \leqslant \rho(\overline l|\mathcal{E}_{1})
\end{gather*}
или
\begin{gather*}
\langle \overline{l}, Q\overline{l} \rangle^{\frac{1}{2}} + \langle \overline{l}, Q_{2}\overline{l} \rangle^{\frac{1}{2}} \leqslant \langle \overline{l}, Q_{1}\overline{l} \rangle^{\frac{1}{2}},
\end{gather*}
так что 
\begin{gather*}
p = p^{*} + 1  = ( \langle \overline{l}, Q\overline{l} \rangle^{\frac{1}{2}} + \langle \overline{l}, Q_{2}\overline{l} \rangle^{\frac{1}{2}} )\langle \overline{l}, Q_{2}\overline{l} \rangle^{-\frac{1}{2}} = 
( \langle \overline{l}, D(p^{*})\overline{l} \rangle^{\frac{1}{2}})\langle \overline{l}, Q_{2}\overline{l} \rangle^{\frac{1}{2}} \leqslant ( \langle \overline{l}, Q_{1}\overline{l} \rangle^{\frac{1}{2}})\langle \overline{l}, Q_{2}\overline{l} \rangle^{-\frac{1}{2}} = \overline{p}.
\end{gather*} 
Вместе с \ref{eq2} и неравенством $$ p \leqslant \overline{p}$$ это позволяет заключить, что $$Q \leqslant Q(- \overline{p})$$, что также доказывает, что $$Q(- \overline{p}) > 0$$, что означает, что $$\overline{p} \in (1, \lambda_{min})$$/. С другой стороны, в силу Леммы 1 мы имеем $$ \mathcal{E}(0,  Q(- \overline{p})) \in \mathcal{E}(0,  Q_{1})  \cdot{-} \mathcal{E}(0,  Q_{2}) $$/. Отсюда получаем желаемый результат.

== Внешние эллипсоидальные оценки. ==