4
$\begingroup$

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

$\endgroup$

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.