0
$\begingroup$

$$\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?

$\endgroup$
8
  • $\begingroup$ Also just in case if translation of the required axes would help in this question to reduce the number of constraints? $\endgroup$ Jun 14 '19 at 20:13
  • 1
    $\begingroup$ It is rather difficult to read the problem. $\endgroup$
    – copper.hat
    Jun 14 '19 at 20:26
  • 1
    $\begingroup$ @copper.hat Is it better now? $\endgroup$ Jun 14 '19 at 20:51
  • 1
    $\begingroup$ What if you just added a new variable $x_4$ that has a coefficient of 0 in the objective function and every constraint? $\endgroup$ Jun 15 '19 at 1:36
  • 1
    $\begingroup$ I bet you That's one of those "without lost of generality" assumptions, read your text book again and carefully. $\endgroup$
    – Red shoes
    Jun 15 '19 at 4:57
1
$\begingroup$

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.

enter image description here

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$

enter image description here

$\endgroup$
3
  • $\begingroup$ Is there any easy way to plot those region in computer? $\endgroup$
    – Red shoes
    Jun 16 '19 at 18:42
  • $\begingroup$ Just a minor point, I think you need to discus that a constraint qualification holds after adding nonlinear slack variables. otherwise there's no guarantee the solution you get from KKT system is optimal for above convex optimization. $\endgroup$
    – Red shoes
    Jun 16 '19 at 18:50
  • $\begingroup$ @Redshoes The feasible region was plotted with the MATHEMATICA command RegionPlot3D[ 2 x1 + x2 < 5 && x1 + x3 < 2 && 1 < x1 && 2 < x2 && 0 < x3, {x1, 0.5, 1.8}, {x2, 1.4, 3.2}, {x3, -0.3, 1.5}, Mesh -> False, PlotStyle -> Directive[Yellow, Opacity[0.3]], PlotPoints -> 100] $\endgroup$
    – Cesareo
    Jun 16 '19 at 19:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.