# Using technique of Lagrange Multiplier

How can we use the technique of Lagrange multipliers to find a new vector of parameters $w$ which solves the optimization problem:

minimize J(w) = $\frac{1}{2} || w -u ||^2$

such that:
$w^T (x − y) ≥ 1$

Here $u$ is the current vector of parameters and $x$ and $y$ are two training examples such that $u^T(x-y) < 1$.

I rewrote the constraints as
$1 -wx -wy \leq 0$
$ux -uy -1 < 0$

Then the Lagrangian is,
$L = \frac{1}{2} (w-u)^2 + a(1-wx-wy) + b(ux-uy-1)$
where, $a,b \geq 0$ are Lagrange multipliers.

But, when I set gradient to zero:
$0 = \frac{dL}{dw} = \frac{dL}{du} = \frac{dL}{dx} = \frac{dL}{dy} = \frac{dL}{da} = \frac{dL}{db}$

I got $w^* = 0$, but I have to solve for w and I assume zero is not the correct answer here.

What am I doing wrong?

Update
Following the idea of jbowman, I got this,
$z = x-y$
minimize J(w) = $\frac{1}{2} || w -u ||^2$

with constraint $1 - wz \leq 0$
Primal Lagrangian $L_P = \frac{1}{2} (w-u)^2 + a(1-wz)$
$0 = \frac{dL}{dw} = \frac{dL}{du} = \frac{dL}{dz} = \frac{dL}{da}$

Another attempt,
I did not include dL/du and take only
$0 = \frac{dL}{dw} = \frac{dL}{dz} = \frac{dL}{da}$

Then I got
Dual Lagrangian,
$L_D = infimum_a L_P(w,u,z,a) = \frac{1}{2} a^2 z^2 +a$

Again, I got w = u.

This is problem of Large Margin Perceptron, but I got answer w equal to u. Whatever I initialize the values to u, the final weight vector w will be u.

Certainly, something is wrong. I am wondering what I did wrong?

• This must be among the very first examples in any multivariate Calculus textbook, so consult your favorite. It is the dual of the first example in the Wikipedia article. – whuber Nov 30 '17 at 19:16
• If you get confused, try solving it in 2 dimensions first. – Alex R. Nov 30 '17 at 21:08
• @whuber I updated the question, however, I got the bad results. – Bhishan Poudel Dec 1 '17 at 1:29
• First, note that $x-y$ is just a vector of numbers, so you may as well do away with it and replace it with $z$. You then have $w^Tz \geq 1$, and only one multiplier to deal with. Second, note that $u$ is irrelevant as you aren't optimizing over it - it's just a constant. Whether or not it satisfies $u^Tz \leq 1$ is irrelevant, so no Lagrangian needed. Similarly for $x$ and $y$, or $z$ as I prefer. That should simplify things for you considerably! – jbowman Dec 1 '17 at 1:38
• @jbowman, thanks a lot, I updated the question, however, I still got the answer w =u. – Bhishan Poudel Dec 1 '17 at 2:38

Following the suggestion of jbowman, I derived the gradient w.r.t. only w and a and got the quadratic solution for w. Optimization problem:

minimize J(w) = $\frac{1}{2} || w -u ||^2$

such that:
$w^T (x − y) ≥ 1$

Constraint:
$1 - wz \le 0$, where z = x-y.

Primal Lagrangian:
$L_P = \frac{1}{2} (w-u)^2 + \alpha(1-wz)$ where $\alpha \ge 0$ is the Lagrange multiplier.

Set gradient w.r.t. w and a to zero:
$0 = \frac{dL}{dw} ==> w = u + \alpha z$
$0 = \frac{dL}{d\alpha} ==> z = 1/w$

Solving these two equations, I got

$w^* =\frac{u \ \pm \sqrt(u^2 + 4\alpha) }{2}$

This is the answer I came with, but not sure its right or not.

Supplementary materials: • Not quite. Try writing out the derivative w.r.t. $w$, I think you have that wrong. Then note that the gradient w.r.t. $a$ doesn't have to equal zero, for example, assume that at $w=u$ the constraint was satisfied; $a$ would equal 0 but the derivative wouldn't. But you're getting closer! – jbowman Dec 1 '17 at 15:20
• Sorry for bugging multiple times, but still I could not solve the problem properly. I tried derivative w.r.t. w multiple times but came with the same solution ( i could not see any mistake calculating w = u + az). Also, If I take z >= 1/w instead of z = 1/w, I will not get the closed form solution of w. I am not sure entirely, but I assume there might be closed form solution of w*. – Bhishan Poudel Dec 1 '17 at 16:11