Modelling a gradient flow subject to geometric constraints

249 Views Asked by At

Part of the John ellipsoid problem asks the following. Let $K\in\mathbb{R}^n$ be a convex, symmetric (w.r.t origin), closed set. Find the inscribed ellipsoid of largest volume. The existence of such an ellipsoid is a simple continuity argument.

However, I would like to model the John ellipsoid problem as a gradient flow. An ellipsoid is the image of the Euclidean unit ball $\mathbb{D}$ under a (non-singular) linear transformation $T$. I want to find a $T_0\in\mathbb{R}^{n\times n}$, such that $$ \left|\det T_0\right| = \max_T \left|\det T_0\right| $$ subject to the geometric constraint $T_0\left(\mathbb{D}\right)\subset K$.

How can I modify the flow equation for $y\colon [0,\tau) \to \mathbb{R}^{n\times n}$ $$ \dot{y}(t) = \nabla \det{y(t)}\phantom{\qquad \ll 1.} \\ y(0) = r\operatorname{Id}_{\mathbb{R}^{n\times n}},\qquad r\ll 1. $$ so that the geometric constraint $T_0\left(\mathbb{D}\right)\subset K$ is modelled as well?

1

There are 1 best solutions below

2
On

Too long for a comment, but maybe a starting point. Let us name $A = \{x: x \in T(\mathcal{B})\}$ as the candidate maximiser ellipsoid, where $\mathcal{B}$ is the unit ball. A formal possibility is to consider an “energy” augmented with a penalty term as follows, $$\mathcal {E} = \det y(t) + \Gamma (A;K)$$ where $$ \Gamma (A;K) = \begin{cases} 0 \, & if \,\, A \setminus (A \cap K) = \emptyset \\ -\infty & if \,\, A \setminus (A \cap K) \neq \emptyset \end{cases} $$ Informally speaking the penalty term $\Gamma$ “intervenes” when your ellipsoid contains points outside $K$. In a numerical implementation, just use a "sufficiently" large negative number or regularise the penalty term (there is a whole lot of algorithms on the topic, for example used in Finite Element implementations to handle contact).

A possibility is as follows: $$\Gamma (A;K) = -\frac{1}{\epsilon^2} \mathcal{L} (A \setminus (A \cap K)) $$ where $\mathcal{L}$ stands for the Lebesgue measure in $\mathcal{R}^n$

EDIT: Would just like to add an idea I was toying with, in 2D. One could define a the analogous of a smooth cut-off function $\chi$, such that its value equals $1$ on $K$ and equals a large negative constant outside $K$. The area $\lvert A \rvert$ of an ellipse could be computed by using Green's Theorem, $$ \lvert A \rvert = \int_{C} x \mathrm{d}y - y \mathrm{d}x$$ where the curve $C$ is the ellipse's perimeter, relatively handy to parametrise. John's problem solution could then maybe be numerically approximated by looking for the maximum of the function $$ \lvert A \rvert = \int_{C} \chi (x,y) [x \mathrm{d}y - y \mathrm{d}x]$$