# Using Kuhn-Tucker to determine if constraint is binding

Let $$f(x,y,z)=xyz+z$$ be the objective function, and suppose that $$0\leq6-x^2-y^2-z$$, $$0\leq x$$, $$0\leq y$$, $$0\leq z$$ are the four constraint functions. I must determine if the constraint $$0\leq 6-x^2-y^2-z$$ is binding for any solution to this maximization problem, i.e. if there is a solution $$w_0=(x_0,y_0,z_0)$$ for which $$6=x_0^2+y_0^2+z_0$$.

Because the objective function and the constraint functions are both weakly concave and differentiable, and since the interior of the constraint set is non-empty, Kuhn-Tucker tells us that $$w_0$$ solves the maximization problem iff $$w_0$$ satisfies the first-order conditions (FOCs) of the Lagrangian.

Hence, to see if this particular constraint is binding, I feel like I need to first find the set of points that solve the Lagrangian FOCs. However, solving this system of equations is nearly impossible by hand, and so I'm wondering if there is another method to check if this constraint is binding for some solution.

• Have you tried substituting the (potentially) binding constraint into the objective function and maximizing the result two variable system? Are any of those also maxima of the given system? – Eric Towers Jul 3 '19 at 19:34
• If I were to substitute the constraint into the objective function and maximize, wouldn't I just be maximizing over a subset of the original constraint set? – David Jul 3 '19 at 19:44
• You would be finding the maximum on the boundary of the feasible set where that constraint is binding. Your constraints after substitution are $0 \leq x, 0 \leq y, 0 \leq 6 - x^2 - y^2$ (where I have omitted the substituted version of your first constraint since it is satisfied everywhere on this part of the boundary of the feasible set). – Eric Towers Jul 3 '19 at 19:48
• So I could find the maximum over this subset of the feasible set, and then plug it into the FOCs of the original Lagrangian and if it satisfies these FOCs, it would be the solution to the original problem. Is this the idea? – David Jul 3 '19 at 19:54
• Yes. (and some meaningless words to meet the minimum character limit for comments) – Eric Towers Jul 3 '19 at 19:55

It is easy to determine restriction binding with the help os slack variables $$(s_k)$$. Considering the Lagrangian

$$L(x,y,z,\Lambda,S) = xyz+z +\lambda_1(x^2+y^2+z-6+s_1^2)+\lambda_2(x-s_2^2)+\lambda_3(y-s_3^2)+\lambda_4(z-s_4^2)$$

and solving for the stationary points

$$\nabla L = 0 = \left\{ \begin{array}{rcl} \lambda_2&=&2 \lambda_ x+y z \\ \lambda_3&=&2 \lambda_1 y+x z \\ \lambda_1+x y+1&=&\lambda_4 \\ \lambda_1 s_1&=&0 \\ \lambda_2 s_2&=&0 \\ \lambda_3 s_3&=&0 \\ \lambda_4 s_4&=&0 \\ s_1^2+x^2+y^2+z&=&6 \\ s_2^2&=&x \\ s_3^2&=&y \\ s_4^2&=&z \\ \end{array} \right.$$

we obtain

$$\left[ \begin{array}{cccccccccccc} f & x & y & z & s_1^2 & s_2^2& s_3^2& s_4^2&\lambda_1&\lambda_2&\lambda_3 & \lambda_4\\ 0 & 0 & 0 & 0 & 36 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 6 & 0 & 0 & 6 & 0 & 0 & 0 & 36 & -1 & 0 & 0 & 0 \\ 0 & 0 & \sqrt{6} & 0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 & 1 \\ 8 & 1 & 1 & 4 & 0 & 1 & 1 & 16 & -2 & 0 & 0 & 0 \\ 0 & \sqrt{6} & 0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right]$$

now examining the values for $$s_1^2$$ as the corresponding slack variable to $$x^2+y^2+z\le 6$$ we conclude that at least $$5$$ stationary points are at the constraint border because for them $$s_1^2 = 0$$. Now the qualification can be done according to KKT criterion, examining the attached plot.

Here black dots and blue curves indicates stationary points/sets. In red the gradient of the actuating restrictions at each stationary point and in black the objective function gradient at each point. In light yellow the feasible region boundary.