Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Well, finding a counterexample isn't that hard - the first example I tried was one. Seeing my problem seems to be hard, however - the example didn't help me with that. –  Thilo Nov 16 '12 at 15:34
add comment

1 Answer

up vote 2 down vote accepted

In the equivalence of $$ \min_{x} \frac 12 x^tQx - c^t x $$ with $Qx = c$ we use the symmetry of $Q$ (otherwise in doesn't hold). Note that for $q(x) = \frac 12 x^tQx - c^tx$ we have \begin{align*} q(x+h) &= \frac 12 (x+h)^tQ(x+h) -c^t x - c^th\\ &= q(x) + \frac 12 x^t(Q+Q^t)h - c^th + \frac 12 h^tQh \end{align*} so $q'(x) = \frac 12 x^t(Q+Q^t) - c^t$ and $x$ being critical is equivalent to $\frac 12(Q + Q^t)x = c$. Note that your $Q'$ fulfills $Q^t + Q = (Q')^t + Q'$.

share|improve this answer
    
Thanks! And yes, it was as obvious as I feared... –  Thilo Nov 16 '12 at 15:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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