1
$\begingroup$

I was going through SVM section of Stanford CS229 course notes by Andrew Ng. On page 18 and 19, he explains Lagrangian and its dual:

He first defines the generalized primal optimization problem: $$ \begin{align} \color{red}{ \min_w } & \quad \color{red}{f(w)} \\ s.t. & \quad g_i(w)\leq 0, i=1,...,k \\ & \quad h_i(w)=0, i=1,...,l \end{align} $$ Then, he defines generalized Lagrangian: $$\mathcal{L}(w,\alpha,\beta)=f(w)+\sum_{i=1}^k\alpha_ig_i(w)+\sum_{i=1}^l\beta_ih_i(w)$$ Then, he defines primal in terms of $\mathcal{L}$ $$=\color{red}{\min}_w\underbrace{\color{red}{\max}_{\alpha,\beta:\alpha_i\geq0}\color{red}{\mathcal{L}}(w,\alpha,\beta)}_{\text{call it }\theta_\mathcal{P}(w,b)}$$ (Since $\max\mathcal{L}=f$ when constraints are satisfied, else $\infty$.)

Similarly, he defines dual optimization in terms of $\mathcal{L}$ $$=\color{blue}{\max}_{\alpha,\beta:\alpha_i\geq0}\underbrace{\color{blue}{\min}_w\color{blue}{\mathcal{L}}(w,\alpha,\beta)}_{\text{call it }\theta_\mathcal{D}(\alpha)}$$

Then, on page 21, he defines SVM's primal optimization problem:

$$ \begin{align} \color{red}{ \min_{w,b} } & \quad \underbrace{\color{red}{\frac{1}{2}\Vert w\Vert^2}}_{\text{call it}\color{red}{f}} \\ s.t. & \quad y^{(i)}(w^Tx^{(i)}+b)\geq 1, i=1,...,n \end{align} $$ Then, he defines the SVM's Lagrangian as follows: $$\mathcal{L}=\frac{1}{2}\Vert w\Vert^2-\sum_{i=1}^n\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]$$ Then, he minimizes $\mathcal{L}$ with respect to $w$ and $b$ to get: $$\mathcal{L}(w,b,\alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n y^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}\quad\quad\quad \text{...equation (1)}$$ Then, he gives SVM's dual optimization problem: $$\begin{align} \max_\alpha & \quad W(\alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n y^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)} \\ \text{s.t.} & \quad \alpha_i\geq 0, 0=1,...,n \\ & \quad \sum_{i=1}^n\alpha_iy^{(i)}=0 \\ & & \text{...equation (2)} \end{align}$$

I am unable to map / relate SVM's dual in equation (2) to the dual in blue color. So after a bit thinking, I guess equation (1) is giving

$$W(\alpha) = \theta_{\mathcal{D}}(\alpha) = \color{blue}{\min}_{w,b}\color{blue}{\mathcal{L}}(w,b,\alpha)$$ and SVM's dual is $$\max_\alpha W(\alpha) =\max_\alpha \theta_{\mathcal{D}}(\alpha) = \color{blue}{\max}_{\alpha}\color{blue}{\min}_{w,b}\color{blue}{\mathcal{L}}(w,b,\alpha)$$ I guess this correctly maps with earlier dual in blue color, right?

Rephrasing the doubt, I guess the confusion was that I felt equation (2) is simply renaming $\mathcal{L}(w,b,\alpha)$ in equation (1) as $\max_\alpha W(\alpha)$. But that is not the case right?

Again rephrasing the doubt, equation (2) is:

$$\begin{align}\max_\alpha & \quad \left[W(\alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n y^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)} \right]\\ \text{s.t.} & \quad \alpha_i\geq 0, 0=1,...,n \\ & \quad \sum_{i=1}^n\alpha_iy^{(i)}=0 \end{align} $$

and not:

$$\begin{align}\color{red}{[}\max_\alpha & \quad W(\alpha)\color{red}{]}=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n y^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)} \\ \text{s.t.} & \quad \alpha_i\geq 0, 0=1,...,n \\ & \quad \sum_{i=1}^n\alpha_iy^{(i)}=0 \end{align} $$

Am I correct with this understanding?

$\endgroup$
0
$\begingroup$

You are correct.

Sanity check: The final (incorrect) formulation of the optimization problem would not make sense because when you maximize over a certain variable, you essentially take that variable out of the expression. It's fixed.

In that vein, I think Ng's notation would be more informative in equation (1) if they wrote the lagrangian as $L(\alpha)$ rather than $L(w,b,\alpha)$, since we have already minimized over $w$ and $b$. Notice how they are not present in the expression anymore?

$\endgroup$

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.