Maxima in the dual of hard margin and soft margin SVMs?

Question

The dual problem for hard margin SVM is: \begin{align*} &\max_{\alpha} \left( \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle \right) \\ &\text{subject to } \sum_{i=1}^{N} \alpha_i y^{(i)} = 0 \text{ and } \alpha_i \geq 0 \text{ for all } i \end{align*}

For soft margin SVM is: $$ \max_{\alpha} \left( \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle \right) $$

subject to the constraints:

$$ \sum_{i=1}^{N} \alpha_i y^{(i)} = 0, \quad 0 \leq \alpha_i \leq C \quad \text{for all } i $$

My question is about proving if these duals always have a maximum, I tried using the Hessian to see that it is negative semi-definite.

In the hard margin case, if the data is not linearly separable, then my intuition says that there may not be a solution. For the soft margin case, I was not sure.

Additionally, I am not sure if using the Hessian is the right approach here because then we assume that the function is second order differential Is there another way to show that the dual has a maximum or that a maximum does not always exist?

Answer 1

The soft margin SVM has a maximum, provided that the feasibility region is not empty. By Weierstrass' I and II theorems, continuous functions have minima and maxima over compact sets, such as the feasibility region of the soft margin problem.

As it comes to hard margins, one can construct examples without a max value. Take the data matrix $X$ as the zero matrix and\or $y^{(i)} = 0$ for $1\le i \le n$. Your problem is reduced to: $$ \max_{\alpha} \Big(\sum_{i=1}^n \alpha_i \Big)\:\text{such that } \alpha_i \ge 0 \qquad \forall 1\le i\le n $$ which is unbounded.