0
$\begingroup$

I am trying to write a quadratic program to minimize a sum of squares. My goal is to obtain a "smooth" vector $x$, so I'm trying to minimize $(x_1-x_2)^2 + (x_2-x_3)^2 + (x_3-x_4)^2 + (x_4 + x_5)^2$ (with some restrictions).

If I understood correctly, the quadratic program representation is then:

$\min x^\top A x$, where $A=D^\top D$.

The first order difference matrix is $D = \begin{pmatrix} -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & -1 & 1 \end{pmatrix}$

Then, $A$ will be $A = D^\top D = \begin{pmatrix} 1 & -1 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & 0 \\ 0 & -1 & 2 & -1 & 0 \\ 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & -1 & 1 \end{pmatrix}$

This matrix $A$ is not positive definite (but semi-definite) according to my quadratic program solver, which throws an error. On Wikipedia, though, it says that all gram matrices of the form $D^\top D$ are positive definite.

I seem to have a mistake somewhere. My hunch is that my matrix $A$ does not represent what I want, which is to minimize $(x_1-x_2)^2 + (x_2-x_3)^2 + (x_3-x_4)^2 + (x_4 + x_5)^2$.

So, my question: Where is my mistake? My sum of squares is clearly positive for all $x$, but my matrix $A$ is not positive definite.

Wikipedia also gives an example that a matrix $\begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}$ is positive definite. This one differs in my version only in the top left and lower right elements. Does that have anything to do with what I'm trying to solve?

$\endgroup$
  • 1
    $\begingroup$ The dimensions of your matrices seem to be off. A doesn't look square to me. And $D^TD$ will only be positive definite if the vectors of D are linearly independent, which is not the case, since you seem to have $n+1$ vectors in $\mathbb{R}^n$. $\endgroup$ – mlk May 23 '17 at 8:17
  • $\begingroup$ Should your $\mathbf{D}$ matrix not be the negative of what you have written? As in: $$\mathbf{D} = \begin{pmatrix}1 & -1 & \dots & 0 \\ 0 & 1 & -1 & \dots \\ \vdots & \ddots & &\vdots \end{pmatrix}$$ $\endgroup$ – Thomas Russell May 23 '17 at 8:17
  • $\begingroup$ @mlk: $D$ is a 4x5 matrix, and $A=D^\top D$ is always square, as far as I know. If $A$ is not positive definite, then $x^\top A x$ does not equal my sum of squares I want to minimize, right? $\endgroup$ – Alexander Engelhardt May 23 '17 at 8:30
  • $\begingroup$ @Thomas: Maybe, but $A$ is the same regardless if I use $D$ or $-D$. $\endgroup$ – Alexander Engelhardt May 23 '17 at 8:30
2
$\begingroup$

$D$ is $4\times 5$ matrix, rank of $D$ $\le 4$. $D^t$ is $5\times 4$ matrix, thus $A$ is a $5 \times 5$. Rank $A$ $\le $ Rank $D$ $= 4 $. Thus $A$ is a $5 \times 5$ matrix of rank $\le 4$. Thus $\exists \ v \in \mathbb{R}^{5}$ such that $Av =0$. So $A$ is not positive definite and only semi-definite.

$\endgroup$
  • $\begingroup$ Explained this way, I understand how $A$ is not positive definite. But if I write out $x^\top A x$, it becomes the sum of squares I wrote down above, which is clearly positive for all nonzero $x$. That means $A$ should be positive definite, doesn't it? $\endgroup$ – Alexander Engelhardt May 23 '17 at 8:57
  • 1
    $\begingroup$ sum of squares can be zero, you see $Dx$ can be zero for a non-zero $x$. Therefore only positive semidefinite($<v,v> \ge 0 $) but not positive definite (<v,v> > 0 ).. $\endgroup$ – Affineline May 23 '17 at 9:03
  • $\begingroup$ Oh god, you're right. I completely missed that. If all $x_i$ are the same value, the sum of squares is zero. Thanks for the help! $\endgroup$ – Alexander Engelhardt May 23 '17 at 9:05

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.