Minimize a matrix

Question

Given

\begin{equation} X^TAX = \left({\begin{array}{cc} x_1 & x_2 \end{array}}\right) \left(\begin{array}{cc} 1.5 & 1\\ 1 & 2 \end{array}\right) \left(\begin{array}{c} x_1 \\ x_2 \end{array}\right) = \end{equation}

Find $x_1$ and $x_2$ ratios that will minimize $X^TAX$ subject to $x_1+x_2=1$

Answer 1

Guide:

The quesiton is equivalent to

$$\min 1.5x_1^2 + 2x_1x_2 + 2x_2^2$$

subject to $x_1+x_2=1$.

Once we perform a substitution, reduce the problem to a one dimensional quadratic optimization problem.

$$\min 1.5x_1^2 + 2x_1(1-x_1) + 2(1-x_1)^2$$

Answer 2

Another way is to write

$$x_1+x_2=1$$ as $${\bf SX}-1=0, \text{ where } {\bf S} = [1,1]$$

This will be solved where $\min_X\{\|{\bf SX}-1\|_2^2\}$

So you can add this term to the minimization:

$${\bf X_o} = \min_X\{{\bf X}^T{\bf AX} + \epsilon\|{\bf SX}-1\|_2^2\}$$

---

Edit Sloppily, I forgot to mention that we need parameter $\epsilon$ to say how much more important the fit to equality is than to minimize the first term. $\epsilon=10^3$ seems to work well enough here.

If you are still skeptical, we can derive the solution and type it into Octave:

 A = [1.5,1;1,2];
 S = [1,1];
 lhs = A + 1e3*S'*S;
 rhs = [1e3*S'*1];
 Xo = [lhs\rhs]'

displays result

    0.66578   0.33289

pretty close to the real solution [2/3 1/3]. If you don't have Octave and you can't install it, there apparently exists something called Octave Online, where you can type it in.

---

This approach is useful in case you have more similar constraints or costs you want to enforce at the same time. You can systematically stuff the linear combinations into such $\bf S$ matrices. Nice if you have like 1000 000 dimensions and 1000 constraints to keep track of.