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!
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$.