# Formulation of SVM optimization problem

I need help in verifying/understanding a step in formulating an optimization problem used for support vector machines (though this question doesn't need any background in SVM). Consider a bunch of $$m$$ points $$x_1, x_2,\ldots,x_m\in\mathbb{R}^n$$, a vector $$w\in\mathbb{R}^n$$ and let $$\gamma_i=\frac{\langle x_i,w\rangle}{\|w\|} + \frac{b}{\|w\|}$$

where $$b=-c\|w\|$$ and $$c$$ is a constant. For this question, assume that $$\gamma_i$$ is positive for all $$i$$. Define $$\gamma\equiv \min_{i=1,\ldots,m} \gamma_i$$ and consider the optimization problem

$$\max_{w,b} \gamma \\\text{subject to}\ \frac{\langle x_i,w\rangle}{\|w\|} + \frac{b}{\|w\|}\geq\gamma$$

Letting $$\hat \gamma=\gamma\|w\|$$, the above can be rephrased as:

$$\max_{w,b} \frac{\hat\gamma}{\|w\|} \\\text{subject to}\ \langle x_i,w\rangle + b\geq\hat\gamma$$

Now we have $$\hat\gamma=\min_i (\langle x_i,w\rangle + b)$$ and assuming that $$w'=w/\hat\gamma$$ (which implies $$b'=b/\hat\gamma$$ since $$w$$ and $$b$$ are proportional), we see that $$\min_i (\langle x_i,w'\rangle + b')=1$$. So we can finally rephrase the optimization problem as (note that earlier we were maximizing w.r.t. $$w, b$$; now we're maximizing w.r.t. $$w',b'$$)

$$\max_{w',b'} \frac{1}{\|w'\|} \\\text{subject to}\ \langle x_i,w'\rangle + b'\geq 1$$

Is this chain of reasoning correct or have I missed something/made an error in any step? Also, this problem is based on the following lecture. The optimization problem is stated on page 6 and the objective is $$\max_{\gamma, w, b}\gamma$$. Shouldn't it be $$\max_{w,b}\gamma$$, since we're only allowed to freely change $$w$$ and $$b$$?

The idea of this proof is essentially correct, the confusion about the difference between maximizing over $$\gamma, w, b$$ and over $$w, b$$ seems to be because there are two different possible ways to formulating the problem: One where you define $$\gamma = \min_i \gamma_i$$, as you do above. The other way is to specify constraints where $$\gamma \le \gamma_i$$ for all $$i$$ and optimize over $$\gamma$$ (which is essentially equivalent since the optimal choice of $$\gamma$$ will be the minimum of the $$\gamma_i$$).
The optimization problem as you have written it is sort of redundant, since $$\frac{\langle x_i,w\rangle}{\|w\|} + \frac{b}{\|w\|} \ge \gamma$$ is true just by your definition, and there is no need to write it out as a constraint. For it to be a linear program, technically you would have to do away with the definition that $$\gamma = \min_i \gamma_i$$, and just let $$\gamma$$ be a variable you optimize over.
• Sorry for the late reply and thanks for the answer! Could you please elaborate on your first paragraph a bit more? The second paragraph makes complete sense. If you refer to this: cs229.stanford.edu/notes/cs229-notes3.pdf , then basically what I'm struggling to understand is the jump from the second last formulation (as in my question) with $\hat\gamma/\|w\|$ to the last formulation in which $\hat\gamma$ is replaced by $1$. This jump is described at the end of page 6 and the start of page 7 in the linked notes. If that makes sense to you, could you please explain that to me as well? – Shirish Kulhari May 25 at 10:23
• Pg.5 in the same notes lines 14-21 describes about scaling factor for $(w,b)$ s.t $\hat \gamma = 1$.The idea is since you deal with $\frac{w}{\|w\|}$ unit vector and such the $\gamma$ is really an invariant when you replace say $w$ with $3w$ etc. What it says you choose appropriate values of $w$ and $b$ such that $\hat \gamma = 1$ – Gopal Anantharaman May 30 at 19:26