Using Kuhn-Tucker to determine if constraint is binding

1k Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.

enter image description here

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.