$$\begin{align}
\text{minimize} \quad & f(x) = x_1^2 + x_2^2 +x_3^2 \\
\text{subject to} \quad & 2x_1+ x_2-5\leq 0 \\
& x_1+x_3-2\leq 0 \\
& 1-x_1 \leq 0 \\
& 2-x_2 \leq 0 \\
& -x_3 \leq 0
\end{align}$$
I came across this question of NLPP which apparently has greater number of constraints (other than non negative restrictions) compared to the number of variables involved. My text book states the KKT conditions to be applicable only when the number of constraints involved is at the most equal to the number of decision variables (without loss of generality) I am just learning this concept and I got stuck in this question.
Any suggestions would be helpful.
EDIT
I tried to introduce a fourth variable $x_4$ with zero coefficient everywhere.
$$\begin{align}
& 2x_1 = -2u_1 – u_2 +u_3\\
& 2x_2 =-u_1 – u_4\\
& 2x_3=-u_2\\
& u_1(5-2x_1-x_2)=0\\
& u_2(2-x_1-x_3)=0\\
& u_3(x_1-1)=0\\
& u_4(x_2-2)=0\\
& 2-x_1-x_3 \geq 0\\
& 5-2x_1-x_2 \geq 0\\
& x_1 – 1 \geq 0\\
& x_2-2 \geq 0
\end{align}$$
This looks bulky to proceed with. Is this correct and what should I do next?
Best Answer
Adopting the convention
$$ \max_X f(X) \ \ \text{s. t.}\ \ g(X) \ge 0 $$
introducing slack variables to transform the inequalities into equations and calling
$$ f(x,y,z)=-(x^2+y^2+z^2)\\ g_1(x,y,z,s)=5-2x-y-s^2\\ g_2(x,y,z,s)=2-x-z-s^2\\ g_3(x,y,z,s)=x-1-s^2\\ g_4(x,y,z,s)=y-2-s^2\\ g_5(x,y,z,s)=z-s^2 $$
we have the lagrangian
$$ L(X,\lambda,S) = f(X)+\sum_k \lambda_k g_k(X,s_k) $$
so the stationary points are given for the solutions to
$$ \nabla L = 0 = \left\{ \begin{array}{rcl} -2 \lambda_1-\lambda_2+\lambda_3-2 x=0 \\ -\lambda_1+\lambda_4-2 y=0 \\ -\lambda_2+\lambda_5-2 z=0 \\ -2 \lambda_1 s_1=0 \\ -2 \lambda_2 s_2=0 \\ -2 \lambda_3 s_3=0 \\ -2 \lambda_4 s_4=0 \\ -2 \lambda_5 s_5=0 \\ 5-2 x-y=s_1^2 \\ 2-x-z=s_2^2 \\ x-1=s_3^2 \\ y-2=s_4^2 \\ z=s_5^2 \\ \end{array} \right. $$
Solving this system of equations we get at
$$ \left[ \begin{array}{cccccccccccccc} f & x & y & z & \lambda_1 & \lambda_2 &\lambda_3 &\lambda_4&\lambda_5&s_1^2&s_2^2&s_3^2&s_4^2&s_5^2\\ -11 & 1 & 3 & 1 & -6 & -2 & -12 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ -10 & 1 & 3 & 0 & -6 & 0 & -10 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ -\frac{13}{2} & \frac{3}{2} & 2 & \frac{1}{2} & -1 & -1 & 0 & 3 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ -\frac{25}{4} & \frac{3}{2} & 2 & 0 & -\frac{3}{2} & 0 & 0 & \frac{5}{2} & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ -6 & 1 & 2 & 1 & 0 & -2 & 0 & 4 & 0 & 1 & 0 & 0 & 0 & 1 \\ -5 & 1 & 2 & 0 & 0 & 0 & 2 & 4 & 0 & 1 & 1 & 0 & 0 & 0 \\ \\\end{array} \right] $$
Here the $s_k=0$ show the actuating restrictions at each solution.
The final qualification should be done using the KKT criteria. At each solution point $X_k^*$ we should have
$$ -\nabla f(X_k^*) = \sum_{j\in I_k}\mu_j \nabla g_j(X_k^*) $$
where $I_k$ is the set of indices for the active restrictions at $X_k^*$, and $\mu_j\ge 0, j\in I_k$
Attached a plot showing the feasible region and in blue the stationary points.
NOTE
The solution for the previous equations associated to the stationary points is quite easy to find due to the binary option at $\lambda_k s_k = 0$ The solution point is at the bottom left. Black vectors are $-\nabla f(X^*)$ and red vectors are $\nabla g_j(X^*),\, j\in I_k$