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

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

Определение

Разностью двух эллипсоидов будем называть $$\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}

и $$\lambda_{max}$$ - наибольший корень уравнения $$detQ(p) = 0$$ из интервала (0;1). Верны следующие утверждения:

Леммы

Лемма 1 Пусть $$\varepsilon(Q_{1}) \subseteq \varepsilon(Q_{2})$$, тогда справедливы следующие утверждения:

• Эллипcоид $$\varepsilon(Q(p))$$ невырожденный тогда и только тогда, когда $$p \in (\lambda_{max},1); * Для таких 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})$$. Доказательство. Из неравенства \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} для любого вектора $$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} ) ) $$.

Применим овыпукление к предыдущему неравенству:
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*} но тогда обязательно возникнет точка, которая вылезет за границу множества - такого не может быть, так как в этом случае