In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq \eta \leq e} \min_{w,\xi} &\frac{\beta}{2}\Vert w\Vert^2 + e^T \xi+ e^T (e-\eta)\cr \text{s.t} &\xi \geq 0, \xi \geq diag(\eta) (e-YX^T w)\cr =\min_{0\leq \eta \leq e}\max_{0\leq \alpha \leq e} &\eta^T (\alpha-e)-\frac{1}{2\beta} \alpha^T (XX^T\odot yy^T \odot \eta \eta^T)\alpha \cr \end{align} The equality comes from strong duality. Where $e$ is the vector of ones and$\odot$ is the componentwise multiplication. In order to make it convex, the paper, uses a convex relaxation $M\succeq \eta \eta^T$. The covex relax of the problem then becomes,($G=XX^T\odot yy^T$) \begin{align} \min_{0\leq \eta \leq e,M\succeq \eta\eta^T}\max_{0\leq \alpha \leq e} &\eta^T (\alpha-e)-\frac{1}{2\beta} \alpha^T (G\odot M)\alpha \tag{I}\cr \end{align} This is equivalent to : \begin{align} \min_{\eta,M,\nu,\omega,\delta} \delta \text{ ,s.t.} \nu \geq 0, \omega \geq 0, 0\leq \eta \leq 1, M \succeq \eta \eta^T,\tag{II}\cr \begin{bmatrix} &G\odot M, &\eta+\nu-\omega\\ &(\eta+\nu-\omega)^T,&\frac{2}{\beta}(\delta-\omega^T e+\eta^T e)\end{bmatrix} \succeq 0 \end{align}

1- how can we derive dual of this equivalent form, problem $II$? So that it shows that the original problem is not unbounded if it's not.

2- What's wrong in the following dual derivation for the problem?

Dual derivation for the problem:

In deriving the dual for the problem $I$, it seems it is infeasible, which is in contradiction with the code I wrote using Yalmip (for the equivalent form). First I wrote $I$ in the following form, \begin{align} \min_{t,\eta,M} &t\cr \text{s.t.} & M \succeq \eta \eta^T\cr &t\geq \eta^T (\alpha-e)-\frac{1}{2\beta} \alpha^T (G \odot M)\alpha,\forall \alpha \epsilon [0,1] \end{align} Now, The lagrangian can be written for the above problem using standard techniques, \begin{align} \mathsf{L}(t,\eta,M;Z,z,v,u,w,s)=&t-tr(\begin{bmatrix} Z,z\\z^T,v\\ \end{bmatrix}^T\begin{bmatrix} M,\eta\\\eta^T,1\\ \end{bmatrix})+u\Big(\eta^T (\alpha-e)-\frac{1}{2\beta} \alpha^T (G \odot M)\alpha-t\Big)\cr&-s^T \eta+w^T (\eta-e)\cr =&(1-u)t-tr((Z+\frac{1}{2\beta}u(G\odot \alpha\alpha^T))^TM)+\cr&\{-2z+u(\alpha-e)-s+w\}^T\eta-v-w^Te \end{align} We have $u=1$, and $M$ is positive definite, then we must have $Z+\frac{1}{2\beta}u(G\odot \alpha\alpha^T)=0$ in order to above problem have bounded value.

What's the problem? Some of my works for this problem is

In writing the optimization problem in epigraph form, $max$ is eliminated. In this way, it is assumed that $\alpha$ is fixed. We have eliminated $\forall \epsilon [0,1]$.

I think $\forall \alpha\epsilon [0,1]$, $M$ can grow without bound for any value of $\alpha$ in a way that preserves $M\succeq \eta\eta^T$. So the problem is unbounded below. I thought that paper, forget some constraints about $M$ which makes problem bounded. Something like $diag(M)=e$. And after that with suggestion from a friend, I code the equivalent problem $II$ using Yalmip, but it is primal-dual feasible and isn't unbounded. So, the above analysis some how is wrong.

A related question was asked here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.