# 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.

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.

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.