0
$\begingroup$

I've been learning Convex Optimization but one thing that really confused me in class was how exactly to recast a given set of constraints in matrix form, so that it can be solved using CVX. For example, I'm supposed to find the dimensions of the maximum volume inscribed ellipsoid in a quadrilateral bounded by the vertices (0,0), (0,100), (150,150) and (300,0).

I understand that the solution is to write this in the form

$$\text{minimize} -\log \det B$$ $$\text{subject to} \quad ||B * a_i||_2 + a^T_i d \leq b_i, \quad i=1,...,m $$

But I have a really hard time conceptualizing the four vertices in terms of $a, d, b$ etc. Any help would be highly appreciated!

$\endgroup$
  • $\begingroup$ Is this a two dimensional ellipsoid? $\endgroup$ – copper.hat Apr 1 at 22:05
  • $\begingroup$ yes, it's a simple 2D ellipse. $\endgroup$ – JaP Apr 1 at 22:39
  • $\begingroup$ Did the answer below address your concerns? $\endgroup$ – copper.hat Apr 6 at 16:33
1
$\begingroup$

Here is one approach. The quadrilateral area can be described as $Q= \{ x | v_k^T x \le \alpha_k , k=1,...,4\}$.

Define your ellipsoid by $E=\{ c+Px | x \in B \}$ where $B$ is the closed unit ball in the $\|\cdot \|_2$ norm.

It is straightforward to show that $mE = |\det P| mB$.

Let the SVD of $P$ be $U \Sigma V^T$, we see that $PB = U \Sigma U^T B$, so we can presume that $P\ge 0$ (in fact, we can assume $P>0$. (And symmetric!)

Since $-\log$ is strictly decreasing, we see that maximising the volume ($\det P$) is the same as minimising $-\log \det P$.

The containment constraint is $v_k^T(c+Px) \le \alpha_k$ for all $x \in B$, and since $\max_{x \in B} v_k^TPx = \|P v_k\|$, we see that the constraints are $P \ge 0$, $P=P^T$ and $v_k^T c + \|Pv_k\| \le \alpha_k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.