3
$\begingroup$

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

enter image description here 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?

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber
    Nov 30, 2017 at 19:16
  • 1
    $\begingroup$ If you get confused, try solving it in 2 dimensions first. $\endgroup$
    – Alex R.
    Nov 30, 2017 at 21:08
  • $\begingroup$ @whuber I updated the question, however, I got the bad results. $\endgroup$ Dec 1, 2017 at 1:29
  • 1
    $\begingroup$ 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! $\endgroup$
    – jbowman
    Dec 1, 2017 at 1:38
  • $\begingroup$ @jbowman, thanks a lot, I updated the question, however, I still got the answer w =u. $\endgroup$ Dec 1, 2017 at 2:38

1 Answer 1

1
$\begingroup$

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:
enter image description here

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – jbowman
    Dec 1, 2017 at 15:20
  • $\begingroup$ 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*. $\endgroup$ Dec 1, 2017 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.