How to make an hyperellipsoid touch a hyperplane

34 Views Asked by At

Let's say we have an hyperellipsoid $\mathcal{E}$ defined by the symmetric, positive definite matrix $P$, i.e.,

$$\mathcal{E} = \{ x \in \mathbb{R}^n \mid x^\top P x = c \}$$

where $c>0$. I would like to find the biggest $c$ possible to make $\mathcal{E}$ touch the hyperplane $\{x \in \mathbb{R}^n \mid a^\top x = b\}$. According to a German book I read, this problem can be solved using Lagrange multipliers. Stated as an optimization problem, this should read $$ \begin{align} &\max_{x \in \mathbb{R}^n} x^\top P x = c \\ &\mathrm{s.t.} \: a^\top x = b \end{align} $$ The corresponding Lagrangian is $\mathcal{L} = x^\top P x - \lambda (a^\top x-b)$ with $\lambda$ being the Lagrange multiplier. The necessary condition for optimality leads to the linear system $$ \underbrace{\begin{bmatrix} -a & 2P \\ 0 & a^\top \end{bmatrix}}_{ =A} \begin{pmatrix} \lambda \\ x \end{pmatrix} = \begin{pmatrix} 0 \\ b \end{pmatrix} $$ and I have no idea how to invert $A$. Am I even on the right track? Any hint/help would be greatly appreciated.

Remark: The aforementioned book states that the solution is $c = {b^2 \over a^\top P^{-1} a }$ if that helps.

2

There are 2 best solutions below

0
On

Ok, it's much easier than I initially thought. Should I delete the question (and the following solution)?

By switching $\lambda$ and $x$ in the above linear system, we can use the ansatz $$ \begin{bmatrix} 2P & -a \\ a^\top & 0 \end{bmatrix} \begin{bmatrix} D & e \\ f^T & g \end{bmatrix} = \begin{bmatrix} I & 0 \\ 0 & 1 \end{bmatrix} $$ where $D \in \mathbb{R}^{n\times n}$, $e,f \in \mathbb{R}^n$, $g \in \mathbb{R}$ and $I$ is the $n\times n$ identity matrix. Solving this provides us with $e=\frac{P^{-1}a}{a^\top P^{-1} a}$ and $x=b e$. Inserting the so found $x$ into $c=x^\top P x$ yields the desired result.

0
On

No need to maximize. We know that at tangency

$$ 2 P x = \mu a\Rightarrow 2x^{T}P x = \mu x^T a\Rightarrow 2c=\mu b\Rightarrow \mu = 2\frac cb $$

substituting the last result into $2 P x = \mu a$ we get $x = \frac cb P^{-1}a$ and finally substituting this result into $a^T x = b$ we obtain the solution

$$ c=\frac{b^2}{a^T P^{-1}a} $$