Zero lambda, zero constraint in the complementary slackness condition of the Kuhn-Tucker problem

Question

Complementary slackness condition in the KKT theorem states that:

$\lambda_i^*\geq0; \lambda_i^*h_i(x^*)=0 $

The usual reasoning goes like this: either constraint is clack $h_i(x^*)>0$ and then corresponding $\lambda_i^*=0$ or constraint is binding ($h_i(x^*)=0$), but then the multiplier $\lambda_i^*>0$. The condition as stated doesn't rule out the $\lambda_i^* = h_i(x^*)=0$ case. How can that be? What intuition stands behind the zero-zero case? How can constraint bind and yet multiplier be zero?

Answer 1

Take an unconstrained minimizer x* and include a constraint passing through x*. Clearly, this is still a local solution of the constrained minimization problem. Clearly, this is a case of zero-zero at complementarity.

Answer 2

This can occur even in linear programming, in the presence of degeneracy. At an optimal basic solution, the slack variable for some binding constraint may be basic (but with value $0$ since it is binding). The corresponding dual variable (one of the multipliers $\lambda_i$ in the terminology of KKT) then has value $0$.

Answer 3

I always imagine the value of the multiplier $\lambda_i^*$ to tell me how badly one would like to violate the $i$-th constraint to further improve the objective function value from $x^*$.

Let us assume you have only one constraint, so you want to minimize a function $f$ over the feasible set given by $h(x) \leq 0$. Say we have a solution $x^*,\lambda^*$ to the KKT system, that is,

1. $h(x^*) \leq 0$ (feasibility),
2. $\nabla f(x^*) + \lambda^* \nabla h(x^*) = 0$ (multiplier rule), and
3. $\lambda^* \cdot h(x^*) = 0$ with $\lambda^* \geq 0$ (complementarity),

and we further suppose that $x^*$ is actually a local minimum of the constrained problem.

So, if $h(x^*) < 0$, then the constraint clearly is not active at $x^*$ and since $x^*$ was already a local minimum, there can be no incentive (at least locally, but that's all general KKT theory can do) to move away from it because we were already free to do so.

Now, say $h(x^*) = 0$ and $\lambda^* > 0$. Then moving from $x^*$ in direction $\alpha\nabla h(x^*)$ for some scaling parameter $\alpha > 0$ will improve the objective value: $$f(x^* + \alpha \nabla h(x^*)) \approx f(x^*) + \alpha \nabla f(x^*)^T \nabla h(x^*) + r = f(x^*) - \alpha\lambda \|\nabla h(x^*)\|^2 + r$$ using the multiplier rule and Taylor expansion with some remainder term $r$, from which we can show that the left hand side is smaller than $f(x^*)$ for $\alpha$ small enough. Hence, violating the constraint given by $h$ would indeed give a better objective function value.

If $h(x^*) = \lambda^* = 0$, then $h$ is active at $x^*$, but there is nothing to be gained (again, locally), since $\nabla f(x^*)$ must already be zero by the multiplier rule! So, the constraint happens to be active, but not because one is eager to leave the feasible region towards higher values of $h$, but just "by accident".

Of course, these considerations become more complicated for more constraints which are active in $x^*$, but this should be a good starting point maybe.