Concavity of SVM dual formulation These notes have derived the following dual formulation of the SVM optimisation problem using KKT conditions that I have followed

It then states that the objective function is quadratic and concave (in alpha) which I find is in no way obvious. The i, j th entry of the Hessian is easy to calculate and only depends on the datapoints, so I don't see why this has to be negative semidefinite. Would appreciate any help.
 A: Yes, it's not obvious, but this is not limited to SVMs. Assuming we have a convex primal problem, the dual problem's objective function is naturally concave. It's probably why your source takes it as granted. Reiterating page 2 of this notes, we can write the general Lagrangian equation as follows: 
$$L(x,\lambda,v)=f_0(x)+\sum_{i=1}^m\lambda_i f_i(x)+\sum_{i=1}^pv_ih_i(x)$$
where $m$ is the number of inequality constraints, and $p$ is the number of equality constraints (we don't have this in SVM formulation by the way, so simplifying a bit below). The dual function is the infimum of the Lagrangian over the feasible set of $x$, $\mathcal D$, i.e.
$$g(\lambda)=\inf_{x\in \mathcal D} L(x,\lambda)$$
The Lagrangian is an affine function of $\lambda$, i.e. $L(x,\lambda)=A(x)\lambda+b(x)$ and we're taking the pointwise infimum (i.e. fix $\lambda$ and take the infimum of the function values wrt $x$ in the feasible set) of this function. And, pointwise infimum of affine functions is concave.
A: The problem can be formularized as follow:
$$
\begin{aligned}
maximize\quad F_D(\alpha) = \mathbf1_n^T\alpha-\frac{1}{2}\alpha^TH\alpha, \\
where\quad H_{ij} = y_iy_j(x_i^Tx_j),\quad \alpha = (\alpha_1, ..., \alpha_n)^T
\end{aligned}
$$
First I prove that $H$ is positive semi-definite, where $H_{ij} = y_iy_j{x_i}^Tx_j$.
Let $X$ be the sample matrix,
$$
X = \begin{pmatrix}
x_1^T \\ \vdots \\ x_n^T
\end{pmatrix}. 
$$
Then $H$ can be represented as
$$
\begin{aligned}
H = (I_yX)(I_yX)^T = I_yXX^TI_y( = (y{\mathbf1_n}^T)XX^T(y{\mathbf1_n}^T) ), \\ 
where \quad\mathbf1_n = \begin{pmatrix} 1 \\ \vdots \\ 1\end{pmatrix},\quad y  = \begin{pmatrix} y_1 \\ \vdots \\ y_2\end{pmatrix},\quad I_y  = \begin{pmatrix} y_1 && \\ &\ddots& \\ &&y_n\end{pmatrix}.
\end{aligned}
$$
$XX^T$ is positive semi-definite because for any $\alpha$, $$\alpha^TXX^T\alpha = (X^T\alpha)^TX^T\alpha \geq 0. $$
Therefore $H$ is positive semi-definite.
Then I prove that $$\theta F_D(\alpha) + (1-\theta)F_D(\beta) - F_D(\theta\alpha+(1-\theta)\beta)\leq 0, $$ so that $F_D(\alpha)$ is concave and has a maximum.
$$
\begin{aligned}
& 2(\theta F_D(\alpha) + (1-\theta)F_D(\beta) - F_D(\theta\alpha+(1-\theta)\beta) \\
= & \theta(\theta-1)(\alpha^TH\alpha+\beta^TH\beta-2\alpha^TH\beta)\\ 
= & \theta(\theta-1)((\alpha-\beta)^TH(\alpha-\beta))\leq0
\end{aligned} 
$$
since $H\geq0$ and $\theta\in(0,1)$.
Thus $$\theta F_D(\alpha) + (1-\theta)F_D(\beta) - F_D(\theta\alpha+(1-\theta)\beta)\leq 0, $$ and $F_D(\alpha)$ is concave.
