# Prove SVM Quadratic Programming has Hessian positive semidefinite

In SVM approach, quadratic programming is often used to minimize the error function.

\begin{align}&\min_{\Lambda} W(\Lambda)=-\Lambda^T\mathbf 1+{1\over 2}\Lambda^TD\Lambda\\ &\text{subject to}\\ &\hspace{80px}\Lambda^T\mathbf y=0\\ &\hspace{80px}\Lambda-C\mathbf 1 \le \mathbf 0\\ &\hspace{80px}-\Lambda \le \mathbf 0\\ \end{align}\\ $\hspace{500px}$[Osuna et al. 1997a]

where $\Lambda^T=[\lambda_1\dots\lambda_n]$, $\mathbf 1 \in \Bbb R^{n\times 1}$ is a column vector with all elements 1, $\mathbf y \in\Bbb R^{n\times 1}$ is a column vector that $y_i\in \{+1, -1\}$, and $C$ is a positive constant.

$D\in \Bbb R^{n\times n}$ where $D_{ij}=y_iy_jK_{ij}$ and $K$ is a kernel matrix which is positive definite or positive semidefinite.

You can totally ignore the quadratic optimization problem above, I just want to show where I came out this problem.

You can just see this question below.

Let $K\in\Bbb R^{n\times n}$ be positive semidefinite and $\mathbf y\in\{1, -1\}^{n}$, show that $D\in\Bbb R^{n\times n}$ where $D_{ij}= y_iy_jK_{ij}$

Prove that $D$ is positive semidefinite.

I've seen some papers that they only related like

[Osuba et al. 1997a]: "$D$ is a positive semi-definite matrix (the kernel function $K$ is positive definite)"

or

[Joachims 1998]: "it is guaranteed to have a positive-semidefinite Hessian $Q$"

(he use $Q$ as we use $D$ to present the same matrix)

Also, I have tried to prove myself, but I got stuck facing $\mathbf y$. So for now, I only came out a few examples to convince me that it's true.

Any prove or any ideas?

## 1 Answer

So, I'll assume you're using the definition of positive semidefinite as follows: a matrix $M$ is PSD if $x^TMx\geq 0$ for all $x$ of appropriate dimension. Well, taking some $x\in\mathbb{R}^n$ we have that $$x^TDx = \sum_{ij} x_iD_{ij}x_j = \sum_{ij}x_iy_iK_{ij}y_jx_j = (x\odot y)^T K (x\odot y)\geq0$$

where $x\odot y$ is the $\textbf{Hadamard product}$ of the vectors $x$ and $y$, i.e. the vector with $i$-th coordinate $x_iy_i$, and the last line follows by PSDness of $K$.

• I never thought it was that simple. No wonder the paper just related it by a few words! – Vito Chou Oct 19 '16 at 3:10