# 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 '20 at 21:01
• Thanks I think that answers it! – user17900 Mar 2 '20 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 '20 at 21:08

It is possible to have

$$g(x^*) = b\; {\rm and}\; \lambda^* = 0$$.

When the multiplier is zero and the constraint is equal to zero, then

a) The constraint does not really "bind"

b) That's why the multiplier is zero.

What does it mean "the constraint does not really bind"?

It means that the solution $$x^*$$, that makes $$g(x^*) = b$$, would be chosen even if the constraint was not imposed. In that sense, the constraint is not really binding, because it does not really forbid us to go where we wanted to be, because we are already there.

Consider the simple example

$$\max_x \{-ax^2 + bx\},\qquad s.t. \;x \geq \frac{b}{2a}$$

The Lagrangean is

$$\Lambda = -ax^2 + bx + \lambda \left(x -\frac{b}{2a}\right)$$

and the f.o.c is

$$x = \frac{b+\lambda}{2a}$$.

Try cases:

a) $$\lambda^* = 0$$ leads to $$x^* = \frac{b}{2a}$$, which is the unconstrained f.o.c. also.

b) $$\lambda^* > 0$$ the f.o.c. initially indicates that $$x^* > b/2a$$. But then the constraint is not binding and we should have $$\lambda^* =0$$ : contradiction.

So we see that in this case the solution is

$$x^* = \frac{b}{2a},\;\;\; \lambda^* = 0.$$

So the constraint appears to be binding, but it really is not.

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 '20 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 '20 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 '20 at 17:13
• thanks. I'll check it out. – mark leeds Mar 3 '20 at 22:23