0
$\begingroup$

Consider a Classification set up where there are $n$ covariates represented by $x_i \in \mathbb{R^{n+1}}$ and $x_{i1} =1$ . While $y_i \in {\{-1,1\}}$ defines the class where $x_i$ belongs to and there are $m$ such training examples. i.e $ i \in {\{1,2,3...m\}}$

Now in order to derive the SVM classifier I started out with the first optimization defined below. Following the lecture notes of CS229 (Andrew Ng) I realized I need to somehow move to the second optimization problem from the first to make the job easier.

Now it is intuitively clear to me that both the optimization problems are equivalent. I was looking for a mathematical way of moving from problem 1 to problem 2. Or a mathematical argument that both the problems are essentially the same one.

First optimization problem :

$\underset{\beta}{max} \quad \lambda$

$\quad st \quad y_i\frac{x_i'\beta}{\sqrt{\beta' \beta}} \geq \lambda \qquad \forall i \in {\{1,2,3...m\}}$

Second optimization problem :

$\underset{\beta}{max} \quad \frac{\lambda}{\sqrt{\beta' \beta}}$

$\quad st \quad y_i{x_i'\beta} \geq \lambda \qquad \forall i \in {\{1,2,3...m\}}$

$\endgroup$
2
$\begingroup$

It is just a variable change. In the first one, the constraint is actually $y_ix_i'\beta\geq \sqrt{\beta'\beta}\lambda$; and we maximize $\lambda$. Let $\gamma=\sqrt{\beta'\beta}\lambda$. Then, optimization objective becomes $\gamma \over \sqrt{\beta'\beta}$ and the constraint becomes $y_ix_i'\beta\geq\gamma$. The $\gamma$ represents the $\lambda$ in the second formulation. By the way, the maximization indices should be both $\beta,\lambda$, i.e. $\max_{\beta,\lambda}$.

$\endgroup$
  • $\begingroup$ thanks that was so trivial. Idk how I missed it. $\endgroup$ – Vishaal Sudarsan Jun 19 '19 at 5:33

Your Answer

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

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