Эллипсоид и его основные свойства

Данная глава посвящена рассмотрению эллипсоида и его основных свойств.

Определения

Эллипсоид

Эллипсоидом $$\mathcal{E} (q, Q)$$ с центром в точке $$q \in \mathbb{R}^n$$ и матрицей $$Q \in \mathbb{R}^{n \times n}$$, такой, что $$Q' = Q > 0$$, будем называть множество точек: \begin{equation} \mathcal{E} (q, Q) = \{x \in \mathbb{R}^n | \langle x - q, Q^{-1}(x-q) \rangle \leqslant 1 \}. \end{equation}

Эллипсоид

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

Опорная функция

Опорной функцией выпуклого замкнутого множества $$A$$ в направлении $$l \neq 0$$ называется функция: \begin{equation} \rho(l|A) = \sup\limits_{x \in A} \langle l, x \rangle. \end{equation}

Основная часть

Утверждение 1

Опорной функцией эллипсоида является функция: \begin{equation}\label{eq2} \rho(l|\mathcal{E}) = \langle l, q \rangle + \sqrt{\langle l, Ql \rangle}, \end{equation} а опорный вектор в направлении $$l$$ равен: \begin{equation}\label{eq3} x^*(l) = q + \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. \end{equation}

Доказательство 1

Пусть для начала $$q = 0$$ (рассмотрим эллипсоид, расположенный в нуле). Тогда требуется минимизировать скалярное произведение $$\langle l, x \rangle$$ при условии: \begin{equation}\label{eq1} \langle x, Q^{-1}x \rangle = 1. \end{equation} Выпишем лагранжиан для данной задачи: \[ \mathcal{L} = \langle l, x \rangle + \lambda(\langle x, Q^{-1}x \rangle -1). \] Отсюда получим: \[ \frac{\partial \mathcal{L}}{\partial x} = l + 2 \lambda Q^{-1}x. \] Приравняв правую часть к нулю, выразим опорный вектор: \[ x^* = -\frac{Ql}{2\lambda}. \] Тогда, подставив его в $$\eqref{eq1}$$, найдем $$\lambda$$ и получим опорный вектор: \[ x^* = \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. \] Следовательно, опорная функция в направлении $$l \neq 0$$ равна: \[ \rho(l|\mathcal{E}) = \bigg\langle l, \frac{Ql}{\sqrt{\langle l, Ql \rangle}} \bigg\rangle = \sqrt{\langle l, Ql \rangle}. \] Очевидно, что при смещении центра эллипсоида в точку $$q \neq 0$$, выражения для опорной функции и соответствующего ей вектора также сместятся, т.е. мы получим $$\eqref{eq2}$$ и $$\eqref{eq3}$$. Утверждение доказано.

Замечание 1

Поскольку выпуклое множество однозначно определяется своей опорной функцией, то эллипсоид можно определить как: \[ \mathcal{E}(q, Q) = \{ x \in \mathbb{R}^n| \langle x, l \rangle\ \leqslant \langle l, q \rangle\ + \langle l, Ql \rangle^{\frac{1}{2}} \}, \] где $$q \in \mathbb{R}^n, Q \in \mathbb{R}^{n \times n}, Q' = Q > 0$$.

Аффинное преобразование

Аффинное преобразование - одна из простейших операций над эллипсоидами. Пусть дан эллипсоид $$\mathcal{E}(q,Q) \subseteq \mathbb{R}^n$$, матрица $$A \in \mathbb{R}^{m \times n}$$, вектор $$b \in \mathbb{R}^m$$. Тогда: \[ A\mathcal{E}(q,Q) + b = \mathcal{E}(Aq + b, AQA^T), \forall A \in \mathbb{R}^{n \times n}, b \in \mathbb{R}^n. \]