2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – mark leeds Mar 2 at 21:01
  • $\begingroup$ Thanks I think that answers it! $\endgroup$ – user17900 Mar 2 at 21:07
  • $\begingroup$ 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$. $\endgroup$ – user17900 Mar 2 at 21:08
0
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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' $\endgroup$ – user17900 Mar 2 at 21:18
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – mark leeds Mar 3 at 14:17
  • $\begingroup$ @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. $\endgroup$ – Holger I. Meinhardt Mar 3 at 17:13
  • $\begingroup$ thanks. I'll check it out. $\endgroup$ – mark leeds Mar 3 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy