0
$\begingroup$

I have a toy question on SVM , where i have to find the weight $w$ by solving the Lagrangian multiplier method by hand . I know Lagrangain with equalities only . Here I have to deal with inequalities and I dont know how to proceed .

We have to minimize $$Q(\alpha)=\alpha_1+\alpha_2+\alpha_3+\alpha_4-\frac{1}{2}(\alpha_2^2-4\alpha_2\alpha_3+4\alpha_3^2+4\alpha_4^2)$$

subjected to $$\alpha_1+\alpha_2-\alpha_3-\alpha_4 = 0 $$ and $$\alpha_i\ge0,\ \ \ \ \ i=1,2,3,4$$ .

$\endgroup$
2
  • $\begingroup$ for personal background : i am from electrical background (junior), i had a course on calculus in my freshman year , there i studied lagrangian with equalities only . $\endgroup$ – abkds Feb 28 '14 at 0:58
  • $\begingroup$ Can you check if your function needs to be maximized? $\endgroup$ – suresh Feb 28 '14 at 14:56
1
$\begingroup$

I believe this problem is unbounded. Let $\alpha_2=\alpha_3=0$. Then, your objective function reduces to:

$$ \alpha_1+\alpha_4−2\alpha_4^2 $$

and your constraint reduces to

$$ \alpha_1-\alpha_4 = 0. $$

Note, since $\alpha_2=\alpha_3=0$ we also have $\alpha_2\geq 0$ and $\alpha_3\geq 0$. Now, set $\alpha_1=\alpha_4$ and let both go to infinity. We remain feasible $\alpha_1-\alpha_4=0$ and $\alpha_1\geq 0$ and $\alpha_4\geq 0$. However, the objective function goes to $-\infty$ since $-2\alpha_4^2$ grows to $-\infty$ much faster than $\alpha_1+\alpha_4$ grows to $\infty$.

$\endgroup$
1
$\begingroup$

This is a partial answer (as I do not have the time to work it out to completion):

Eliminate $\alpha_4$ using the constraint in the form of an equality but add a new inequality $\alpha_1+\alpha_2-\alpha_3\geq 0$ that replaces $\alpha_4\geq0$. Call the function $Q(\alpha)$ after the elimination of $\alpha_4$, $P(\alpha)$. The problem now reduces to minimizing $P(\alpha)$ in a region $R$ in the positive $(\alpha_1,\alpha_2,\alpha_3)$ octant bounded by the plane $\alpha_1+\alpha_2-\alpha_3=0$.

The next steps are as follows: (i) Solve for $dP=0$ and see if there are any solutions in the region $R$. (ii) Compare the value for any such solution that you obtain with values on the boundaries of $R$ and pick the minimum one. The boundaries of $R$ are the $(\alpha_i=0)\cap R$ for $i=1,2,3$ and $(\alpha_1+\alpha_2-\alpha_3=0)\cap R$.

$\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.