# Finding and recognizing infeasible Lagrange multiplier points

1. Dec 26, 2011

### clustro

Maximize: 3*v*m
subject to:
L - m - v >= 0
V - v >= 0
m - 6 >= 0
M - m >= 0

Where L, M, and V are positive integers.

Lagrangian (call it U):

U = 3vm + K1(L - m - v) + K2(V - v) + K3(m - 6) + K4(M - m)

Where K1-K4 are the slack variables/inequality Lagrange multipliers.
Which yield the KKT conditions:

dU/dv = 3m - K1 - K2 = 0
dU/dm = 3v - K1 + K3 - K4 = 0
K1(L - m - v) = 0
K2(V - v) = 0
K3(m - 6) = 0
K4(M - m) = 0
K1-K4 >= 0

Now, suppose we assume K1 = K2 = 0, K3 and K4 != 0.

This yields:

m - 6 = 0
M - m = 0
(so m = M)

3(M) - K1 - K2 = 0

but we assumed K1 = K2 = 0, and plugging into the second KKT condition yields:

3(M) - K1 - K2 = 0, 3M = 0, which is not true.

I do not understand if I have made an error, or if this result is to be interpreted in some fashion. Does this simply mean that the point is infeasible? It just seems strange to obtain the result that way; other times I can solve for all variables and clearly see that K1-K4 are not all positive, or that another constraint is being violated.

2. Dec 26, 2011

### AlephZero

A good place to start is K3(m - 6) = 0, which means either K3 = 0 or m = 6.
If K3 != 0, the first equation says K1 + K2 = 18.

You don't say why you chose to assume K1 = K2 = 0, K3 and K4 != 0, but that assumption isn't consistent with the equations you are trying to solve.

3. Dec 27, 2011

### clustro

Well the reason I assumed it, is because from what I read, that is how these types of problems are solved. You do not know a priori which K's will be zero, and which will be nonzero. The only way to find out is to assume some of them are zero, and then plug in and see the results. If it leads to constraint violations, then the point is infeasible.

Its just several times when I discovered infeasible points, I solved for v and m, but discovered that one of the K values with be negative (all K's must be >= 0 for a correct solution). In this case, I found 3M = 0. It was different, and I wasn't sure if that result was correctly interpreted as an "infeasible point."

edit:

By K1 - K4 >= 0, I meant "K1 thru K4 >=0". Sorry!

Last edited: Dec 27, 2011
4. Dec 28, 2011

### clustro

Does nobody know? :(

5. Dec 28, 2011

### AntsyPants

These problems are rarely straightforward.

First of all, you shouldn't solve a problem in a certain way just because it's how it's usually done. That usually means you don't understand what you're doing. If there is a solution to this optimization problem then there must be a set of {m,v,K1,K2,K3,K4}, which satisfy the conditions.

Second, I doubt anyone's going to solve this for you. From what I can see you made no mistake except for starting with the wrong set of assumptions. Try a different set until you eventually reach the solution.

There are obviously many assumptions to make, and you've failed to try them all, so just keep going.

6. Dec 29, 2011

### clustro

I have not asked anyone to solve the problem for me. That is not what I am looking for. I probably won't solve it all the way myself, because there are too many permutations and the solution is not direly important. The question I am asking is more theoretical.
I am simply asking if this would be considered an infeasible point, since you obtain 3M = 0, which contradicts the assumptions made.

I am assuming it is, but maybe someone who knows more/has more experience with the KKT conditions/Lagrange multipliers has more insight.

What leads you to believe that this is what I am doing? Indeed, I read that you make various assumptions about the Lagrange multipliers, but that makes sense/seems like the only real way to solve these problems, e.g. by assuming that various constraints are either slacking or riding, and trying to find the optimum over all points that obey the constraints.