Using technique of Lagrange Multiplier

Question

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

My attempt:

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](https://en.wikipedia.org/wiki/Lagrange_multiplier#Example_1a). — whuber, Nov 30 '17 at 19:16
@whuber I updated the question, however, I got the bad results. — BhishanPoudel, Dec 01 '17 at 01: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 01 '17 at 01:38
@jbowman, thanks a lot, I updated the question, however, I still got the answer w =u. — BhishanPoudel, Dec 01 '17 at 02:38
You only need the derivatives w.r.t. $w$ and $a$, the other terms you have above $(z,u)$ are just parameters, i.e., for any specific problem, constants. You need to pay attention to which symbols refer to variables you are solving for and which symbols are parameters! If you try writing out the two derivatives - w.r.t. $w$ and $a$ - it may be clearer what to do next. — jbowman, Dec 01 '17 at 02:58
@jbowman, Good morning and thanks for the valuable suggestion. I attempted a short solution below, it is correct now? — BhishanPoudel, Dec 01 '17 at 15:06

BhishanPoudel · Answer 1 · 2017-12-01T16:08:18.190

1

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:

edited Dec 01 '17 at 16:08

answered Dec 01 '17 at 14:55

BhishanPoudel

215
2
8

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 01 '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*. – BhishanPoudel Dec 01 '17 at 16:11

Using technique of Lagrange Multiplier

1 Answers1