Consider the C-SVM Dual Problem:
$$ \text{minimize}_{\lambda} \quad \mathbf{q}^{T} \lambda + \frac{1}{2} \lambda \mathbf{P} \lambda $$ $$ \text{subject to} \quad \mathbf{y}^{T} \lambda = 0 $$ $$ \quad \quad \quad \quad \quad 0 \leq \lambda \leq C$$
where $q = -\mathbf{1}_{M}$, $M$ is the number of examples in the data, $\mathbf{y} \in \{0, 1\}^{M}$ is the label vector, $\mathbf{P}$ is the kernel matrix, $\lambda$ is the dual variable and $C$ is the error weight.
- Question 1: Does strong duality hold?
My thought is that it does not, because the constraint $0 \leq \lambda \leq C$ violates Slater's condition. Is that true?
- Question 2: How can we adapt the standard interior point algorithm for this case?
The IP algorithm says that we need to take a step $\lambda_{k+1} = \lambda_{k} + \alpha_{k} d_{k}$, where $d_{k}$ is the direction and $\alpha_{k}$ is the stepsize. When $C = \infty$, $\alpha_{k}$ is chosen such that we ensure $0 \leq \lambda$. Because $C \neq \infty$, does this mean we can simply use:
$$ \lambda_{k+1} = \text{min} \{C , \lambda_{k} + \alpha_{k} d_{k} \}$$
In other words, just project our step onto the box constraint set?
This is a very well-studied problem in machine learning literature and IMO you may want to go for standard approaches unless you have specific reasons. If the objective is convex quadratic and constraints are affine/linear, then strong duality holds(see theorem 2 in here). For $C-$SVM, you can use the standard approach of Sequential minimal optimization (wiki) which is well-studied for the problem you are specifying.