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

Материал из sawiki
Перейти к навигации Перейти к поиску
Строка 31: Строка 31:
 
Пусть $$\varepsilon(Q_{1}) \subseteq \varepsilon(Q_{2})$$, тогда справедливы следующие утверждения:
 
Пусть $$\varepsilon(Q_{1}) \subseteq \varepsilon(Q_{2})$$, тогда справедливы следующие утверждения:
  
−
* Эллипcоид $$\varepsilon(Q(p))$$ невырожденный тогда и только тогда, когда $$p \in (\lambda_{max},1)$$;
+
* Эллипcоид $$\varepsilon(q_{2} - q_{1}, Q(p))$$ невырожденный тогда и только тогда, когда $$p \in (1, \lambda_{min})$$. Для таких p эллипсоид является внутренней аппроксимацией разности $$\varepsilon(q_{2} - q_{1}, Q(p)) \subseteq \varepsilon(Q_{1}) \cdot{-} \varepsilon(Q_{2})$$
  
−
* Для таких p эллипсоид $$\varepsilon(Q(p))$$  - внутренняя оценка разности $$\varepsilon(q_{2}, Q_{2}) \dot{—} \varepsilon(q_{21}, Q_{1})$$, то есть $$\varepsilon(Q(p)) \subseteq \varepsilon(q_{2}, Q_{2}) \dot{—} \varepsilon(q_{21}, Q_{1})$$.
+
* Для фиксированного вектора $$l \in \mathbb{R}^{n}, ||l|| = 1$$ выражение
 +
\begin{gather}
 +
\displaystyle p = \frac{\langle l, Q_{2} l \rangle^{1/2}}{\langle l, Q_{2} l \rangle^{1/2}} > 1.
 +
\end{gather}  
 +
определяет параметр p. Если параметр $$p \in Pi^{-}$$, то
 +
\begin{gather}
 +
\rho(l|\varepsilon (q_{1} + q_{2},Q(p))) = \rho(l|\varepsilon (q_{1},Q_{1}) + \varepsilon(q_{2},Q_{2})).
 +
\end{gather}
 +
Также верно обратное: при заданном параметре $$p \in Pi^{-}$$ существует вектор $$l \in \mathbb{R}^{n}, ||l|| = 1$$ который обеспечивает верность равенств.
  
 
'''Доказательство.'''
 
'''Доказательство.'''
Строка 44: Строка 52:
 
\langle l, Q_{1} l \rangle < \langle l, Q_{2} l \rangle
 
\langle l, Q_{1} l \rangle < \langle l, Q_{2} l \rangle
 
\end{gather}
 
\end{gather}
−
для любого вектора $$l \in \mathbb{R}^{n}$$ из чего можно вывести неравенство
 
−
\begin{gather}
 
−
\displaystyle p = \frac{\langle l, Q_{2} l \rangle^{1/2}}{\langle l, Q_{2} l \rangle^{1/2}} > 1.
 
−
\end{gather}
 
−
 
−
 
−
Будем оценивать разность эллипсоидами.
 
−
\begin{gather*}
 
−
    \varepsilon_{1} = \varepsilon (0, Q_{1}); \\
 
−
    \varepsilon_{2} = \varepsilon (0, Q_{2}); \\
 
−
    \varepsilon_{-} \displaystyle = \varepsilon (0, Q_{-}), \, где \, Q_{-} = (p_{1} - p_{1}) ( \frac{Q_{1}}{p_{1}} - \frac{Q_{2}}{p_{2}} );
 
−
\end{gather*}
 
−
Оценим опорной функцией:
 
−
\begin{gather*}
 
−
    \rho^{2} ( l | \varepsilon_{-} ) \displaystyle = \langle l, Q_{1}l \rangle + \langle l, Q_{2}l \rangle - \frac{p_{2}}{p_{1}}  \langle l, Q_{1}l \rangle - \frac{p_{1}}{p_{2}}  \langle l, Q_{2}l \rangle \leq \\
 
−
\displaystyle \leq \langle l, Q_{1}l \rangle + \langle l, Q_{2}l \rangle - 2 \sqrt{ \frac{p_{2}}{p_{1}} \langle l, Q_{1}l \rangle \frac{p_{1}}{p_{2}} \langle l, Q_{2}l \rangle } = \\
 
−
= \displaystyle \langle l, Q_{1}l \rangle - 2 \langle l, Q_{1}l \rangle^{0.5} \langle l, Q_{2}l \rangle^{0.5} = \\
 
−
\displaystyle = [ \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) ]^{2}
 
−
\end{gather*}
 
−
равенство достигается при
 
−
\begin{gather*}
 
−
    p_{1} = \langle l, Q_{1}l \rangle^{0.5}; \\
 
−
    p_{2} = \langle l, Q_{2}l \rangle^{0.5}.
 
−
\end{gather*}.
 
−
Необходимо, чтобы $$Q_{-} \geqslant 0 $$. Это достигается при
 
−
\begin{gather*}
 
−
    \begin{cases}
 
−
        \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) \geqslant 0,
 
−
        ( \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) ) = conv( \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) ).
 
−
    \end{cases}
 
−
\end{gather*}
 
−
При этом если известно, что $$Q_{-} \geqslant 0 $$, то
 
−
\begin{gather*}
 
−
    \rho ( l | \varepsilon_{-} ) \geqslant \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ).
 
−
\end{gather*}
 
−
Из этого получаем, что $$ \rho ( l | \varepsilon_{1} \dot{-} \varepsilon_{2} ) $$ - максимальная выпуклая функция, не превосходящая $$ conv ( \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) ) $$.
 
−
Применим овыпукление к предыдущему неравенству: <br />
 
−
I способ.
 
−
\begin{gather*}
 
−
    conv( \rho ( l | \varepsilon_{-} ) \geqslant \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) ) \\
 
−
    conv( \rho ( l | \varepsilon_{-} )  ) \geqslant conv( \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) ) \Rightarrow \\
 
−
    \text{ \{ так как} \rho ( l | \varepsilon_{-} ) \text{выпуклая функция \} } \Rightarrow \\
 
−
    \rho ( l | \varepsilon_{-} )  \geqslant conv( \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) )
 
−
\end{gather*}
 
−
II способ.
 
−
\begin{gather*}
 
−
    \rho ( l | \varepsilon_{-} ) - \text{выпуклая функция}  \geqslant conv( \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ) \\
 
−
    \text{Выбираем эллипсоид} \rho ( l | \varepsilon_{-} ) = \rho ( l | \varepsilon_{1} ) - \rho ( l | \varepsilon_{2} ), \\
 
−
    \text{но тогда обязательно возникнет точка, которая вылезет за границу множества}
 
−
\end{gather*}
 
−
но тогда обязательно возникнет точка, которая вылезет за границу множества - такого не может быть, так как в этом случае
 
  
 
== Внешние эллипсоидальные оценки. ==
 
== Внешние эллипсоидальные оценки. ==

Версия 01:42, 3 марта 2023

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

Определение

Разностью двух эллипсоидов будем называть $$\varepsilon_{1} \dot{—} \varepsilon_{2}$$ \begin{gather*} \rho (l | \varepsilon_{1} \dot{—} \varepsilon_{2}) = conv( \rho(l | \varepsilon_{1}) - \rho (l | \varepsilon_{2} )) \end{gather*}

Основные понятия

Пусть $$ 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$$ не упоминается будем считать, что он находится в центре координат.

Внутренние эллипсоидальные оценки

Пусть $$Q_{2}$$ - положительно определена, а $$Q_{1}$$ - неотрицательно определенная матрицы. Для оценивания разности эллипсоидов $$\varepsilon(q_{2}, Q_{2}) \dot{—} \varepsilon(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 Пусть $$\varepsilon(Q_{1}) \subseteq \varepsilon(Q_{2})$$, тогда справедливы следующие утверждения:

  • Эллипcоид $$\varepsilon(q_{2} - q_{1}, Q(p))$$ невырожденный тогда и только тогда, когда $$p \in (1, \lambda_{min})$$. Для таких p эллипсоид является внутренней аппроксимацией разности $$\varepsilon(q_{2} - q_{1}, Q(p)) \subseteq \varepsilon(Q_{1}) \cdot{-} \varepsilon(Q_{2})$$
  • Для фиксированного вектора $$l \in \mathbb{R}^{n}, ||l|| = 1$$ выражение

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

Доказательство. Из неравенства \begin{gather} \varepsilon(Q_{1}) \subseteq \varepsilon(Q_{2}) \end{gather} следует \begin{gather} \langle l, Q_{1} l \rangle < \langle l, Q_{2} l \rangle \end{gather}

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

Источник — http://sawiki.cs.msu.su/index.php?title=Геометрическая_разность_двух_эллипсоидов._Внутренние_и_внешние_оценки&oldid=2797