2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thilo Nov 16 '12 at 15:34
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! And yes, it was as obvious as I feared... $\endgroup$ – Thilo Nov 16 '12 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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