Lagrange Multiplier for discrete variables?

[pX]

Can anyone tell me exactly what it is. From what I gather from here it looks like a way to find extrema involving gradients or partial derivatives, but I'm not sure...

Basically I have a bonus problem in my AI class, but it looks nothing like anything I can find. It just has a function h(x) and says "investigate the extreme values of h given the constraint ||x||=1", as a hint he said to use the 'lagrange multiplier' but we have did nothing in the class with it, nor have I ever seen it before. Plus the function is a summation, i.e., h(x)=[summation over all i and j]AijXiXj ; where A is a nxn matrix and X is a vector... Wierd. I have no clue, I guess I won't do it, no problem, but I was just curious as to what it was talking about...

Anyone know?

 

[f95toli]

Lagrange multipliers are used to find the extremes of a function f(x) given the condition g(x)=0 (for example: find the maximum of f(x) along the curve g(x).

This problem can with the help of a Lagrange multiplier be written as a system of equations:

grad f(a,b)=lambda*grad g(a,b)
g(x)=0

If the problem is in two dimensions this would give you 3 equations (the grad... gives you two). You are usually not intereted in the value of lambda but with the help of these equations you can solve for x and y.

In your case I guess the problem can be written

grad h(x)=lambda*grad (||x||-1)
||x||=1

and you should solve for x

 

[oboeguy]

Your "objective function" h looks like x'Ax (x' means "x transpose"). So your problem is not a big deal: minimize a quadratic over the unit ball (||x|| = 1). Look-up the method of Lagrange multipliers in your calculus text book for starters. This is a trivial problem for me to solve (I do this stuff for a living), but I don't want to do your extra credit homework. 😀 I would say that if you're not familiar with this stuff, it would take quite a bit of effort to get going, and I wonder if it's worth it for an EC problem. But if you're motivated, look-up the Lagrange multipliers and have a go.