# Complementary slackness conditions (Kuhn-Tucker)

Consider the problem of maximising a smooth function subject to the inequality constraint that $$g(x) \leq b$$. The complementary slackness condition says that

$$\lambda[g(x) - b] = 0$$

It is often pointed out that, if the constraint is slack at the optimum (i.e. $$g(x^*) < b$$), then this condition tells us that the multiplier $$\lambda = 0$$. I agree with this. However, it has also been said that, if the constraint 'binds' (which implies that $$g(x^*) - b = 0$$), we must have $$\lambda > 0$$. Is this true? As a logical matter, it is not immediately implied by the complimentary slackness condition: we could have both $$g(x^*) - b = 0$$ and also $$\lambda = 0$$.

Edit: it has been demonstrated here why we can have both $$\lambda = 0$$ and $$g(x^*) - b = 0$$ (thanks to @markleeds for the pointer). I am wondering, however, whether we can have $$\lambda = 0$$ while the constraint also binds (i.e. makes a difference to the solution -- note that this is subtly different from the constraint holding with equality). I suspect that the answer is 'no' given that $$\lambda$$ reflects the effect of slightly relaxing the constraint on the objective function. However, I would appreciate confirmation of this.

• Hi: I don't't have time to try to understand it but I think the last answer at the link below may be helpful. mathoverflow.net/questions/248314/… – mark leeds Mar 2 at 21:01
• Thanks I think that answers it! – user17900 Mar 2 at 21:07
• Somewhat, at least: my feeling is that if the constraints binds (i.e. makes a difference to the solution), we must have $\lambda > 0$, even though the fact that the constraint holds with equality ($g(x^*) = 0$) does not imply that $\lambda > 0$. – user17900 Mar 2 at 21:08

Your intuition is correct. Say you know that $$Z=X\cdot Y=0$$ You don't know if $$X=0$$ or $$Y=0$$ or both are zero. Even if you know that $$X=0$$ you have no idea if $$Y=0$$, $$Y<0$$ , or $$Y>0$$.

Consider the potentially satiated utility function: $$\max_{X,Y} U(X,Y) = min(X+Y, 5)$$ $$S.T. \:p_x X + p_y Y + p_z Z\leq M$$ Assume, for simplicity, that $$p_x = p_y = p_z =1$$. In lagrangian form this is: $$\max_{X,Y} U(X,Y) = min(X+Y, 5) - \lambda (X+Y+Z-M)$$ Z is the free disposal good, in that it uses up extra money but provides no utility. If $$M>5$$ then the budget constraint binds. Under this condition, $$\lambda$$ is the shadow value of more income, and is also zero.

Or, if that utility function doesn't suit you, consider: $$\max_{X,Y} U(X,Y) = -(X+Y-5)^2 - \lambda (X+Y+Z-M)$$
If $$X+Y>5$$ then the household wants to use free disposal and set $$X+Y=5$$. The budget constraint doesn't bind and the MU of income is zero: $$MU_{X+Y+Z=5}=-2(X+Y-5)=0$$.

• Right, but is the following true: if the constraint binds (i.e. makes a difference to the solution), then we must have $\lambda > 0$? I suspect that the answer is 'yes' – user17900 Mar 2 at 21:18

You are right. The second statement is logically incorrect. To make the point, let me write for convenience sake $$\tilde{g}(x):=g(x) - b$$. Then by the complementary slackness condition, we have

$$\lambda \cdot \tilde{g}(x) = 0$$

which comes from the Kuhn-Tucker optimality conditions $$\tilde{g}(x) \le 0$$ (primal feasibility of the solution) and $$\lambda \ge 0$$ (dual feasibility of the solution). By these constraints, we realize that both can hold as equalities, but not as inequalities. However, if $$\lambda > 0$$, then $$\tilde{g}(x) =0$$. This statement is equivalent to the contra-positive statement that if $$\tilde{g}(x) <0$$, then $$\lambda = 0$$. We observe that we can infer from an inequality constraint that the other constraint must hold by equality. However, we cannot infer that if a constraint holds by equality, then the other must be an inequality. This is a fallacy.

• I definitely believe that both of you are correct but I'm pretty sure that I also remember reading what a@freelunch pointed out. how could so many texts have this incorrect statement ? – mark leeds Mar 3 at 14:17
• @markleeds Unfortunately, wrong logic is a great issue in the literature. In this respect, the following link arxiv.org/abs/1908.00409 might be of interest to clarify the problem. – Holger I. Meinhardt Mar 3 at 17:13
• thanks. I'll check it out. – mark leeds Mar 3 at 22:23