2
$\begingroup$

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

enter image description here

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.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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