# Describing Constraints Using Linear Algebra (Convex Optimization)

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!

• Is this a two dimensional ellipsoid? – copper.hat Apr 1 at 22:05
• yes, it's a simple 2D ellipse. – JaP Apr 1 at 22:39

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