Do you know the feeling when you have proven something totally incredible? In fact, it is so incredible you do not believe it yourself. So you start looking for your mistake, for the one, small logical flaw that turns all your believes upside down. And you just can't find it...
That pretty much describes my problem. Your task: Find my mistake and make me hit my head against some imaginary wall. (A real-world-wall would hurt to much, wouldn't it?)
Suppose we have some quadratic program: $ \min_{x\in \mathbb{R}^d} \frac{1}{2}x^T Q x - c^Tx $ with positive semidefinite $Q$. It is well known that we can solve that program by solving $Qx = c$.
Now, if $x=[x_1,\ldots, x_d]$ and $Q=[q_{i,j}]_{i,j=1,\ldots,d}$, we have the following relation: $ x^TQx=\sum_{j=1}^d\sum_{i=1}^dq_{i,j}x_ix_j=\sum_{j=1}^{d-1}\sum_{i=j+1}^d(q_{i,j}+q_{j,i})x_ix_j+\sum_{i=1}^nq_{i,i}x_i^2=x^TQ'x $ with $ Q'=[q'_{i,j}]_{i,j=1,\ldots, d}\quad q'_{i,j}=\begin{cases}q_{i,j}& \text{if }i = j\\ q_{i,j}+q_{j,i}&\text{if }i > j\\ 0&\text{if }i < j\end{cases} $
Thus, $Q'$ is a triangular matrix, and as $x^TQx=x^TQ'x$, solving our quadratic program is equivalent to solving the problem $ \min_{x\in \mathbb{R}^d} \frac{1}{2}x^T Q' x - c^Tx, $ which is rather trivial, as $Q'$ is triangular and $Q'x=c$ therefore easy to solve.
So, I propose that solving $Q'x=c$ is equivalent to solving $Qx=c$ - that has to be the fastest triangularization method I have ever seen...
What am I doing wrong?