Non-linear optimization problem using Lagrange’s method/K.K.T. conditions

convex optimizationkarush kuhn tuckerlagrange multipliernonlinear optimizationoperations research

We are given the following problem:

$$\text{minimize }
2x_1^2 + x_2^2 + 3x_3^2
\text{ subject to }
x_1+x_2+x_3=10,
x_1\le5,
\text{ and }
x_1,x_2,x_3\ge0$$

I understand that I have to check all possible combinations for $\lambda_1$ and $\lambda_2$ and then choose the one that matches the conditions. I am pretty sure that the correct one is $\lambda_1\gt0, \lambda_2=0$, however I cannot prove it.

This is my progress so far:

$L(x_1, x_2, x_3,z_1;λ_1, λ_2)=2x_1^2+x_2^2+3x_3^2+λ_1(x_1+x_2+x_3-10)+λ_2(x_1+z_1-5)$

K.K.T. Conditions:

i. $4x_1+λ_1+λ_2=0, 2x_2+λ_1=0, 6x_3+λ_1=0$

ii. $x_1+x_2+x_3=10, x_1\le5$

iii. $λ_1\ge0, λ_2\ge0$

iv. $λ_2(x_1-5)=0$

Best Answer

The KKT conditions are \begin{align} 4x_1+\lambda_1+\lambda_2 &=0\\ 2x_2+\lambda_1 &= 0\\ 6x_3+\lambda_1 &= 0\\ x_1+x_2+x_3 &= 10\\ x_1 &\le 5 \\ x_i &\ge 0 \\ \lambda_2 &\ge 0 \\ \lambda_2(x_1-5) &= 0\\ \end{align} The complementary slackness constraint implies two cases: $\lambda_2=0$ or $x_1=5$. The first case yields solution $x=(30/11,60/11,20/11)$, with objective value $600/11$. The second case yields solution $x=(5,15/4,5/4)$, with objective value $275/4>600/11$.

Find the optimal solution by the dual simplex algorithm

Add the artificial constraint $x_1 + x_3 \le M$ to the problem.
Write the problem in canonical form.
Add a slack variable to each inequality.
Write a simplex tableau for the problem. \begin{equation*} \begin{array}{lrrrl} \max & z = 2 x_1 & - x_2 & + x_3 & \\ \text{s.t.} & - 2 x_1 & - 3 x_2 & + 5 x_3 & \le - 4 \\ & x_1 & - 9 x_2 & + x_3 & \le - 3 \\ & 4 x_1 & + 6 x_2 & + 3 x_3 & \le 8 \\ & x_1 & & + x_3 & \le M \end{array} \\ x_1, x_2, x_3 \ge 0 \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & -2 & -3 & -5 & 1 & 0 & 0 & 0 & -4 \\ x_5 & 1 & -9 & 1 & 0 & 1 & 0 & 0 & -3 \\ x_6 & 4 & 6 & 3 & 0 & 0 & 1 & 0 & 8 \\ x_7 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & -2 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \end{array} \end{equation*} Perform a pivot operation using $y_{7?}$ as a pivot to make all entries in the last row positive. \begin{equation*} \begin{array}{rrrrrrrr|l} x_7 & \color{red}{1} & 0 & \color{red}{1} & 0 & 0 & 0 & 1 & M \\ \hline & \color{red}{-2} & 1 & \color{red}{-1} & 0 & 0 & 0 & 0 & 0 \\ \text{ratio} & \color{red}{2/1=2} & & \color{red}{1/1=1} & & & & & \end{array} \end{equation*} Here, we should choose the maximum ratio. Therefore, we choose $y_{71}$ as a pivot element in the initial tableau. \begin{equation*} \begin{array}{rrrrrrrr|l} x_7 & 1^* & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & -2 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \end{equation*} We apply the dual simplex algorithm to the following tableau. \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & -3 & 7 & 1 & 0 & 0 & 2 & 2M -4 \\ x_5 & 0 & -9 & 0 & 0 & 1 & 0 & -1 & -M -3 \\ x_6 & 0 & 6 & -1 & 0 & 0 & 1 & -4^* & -4M +8 \\ x_1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & 0 & 1 & 1 & 0 & 0 & 0 & 2 & 2M \\ \text{ratio} & & & 1 & & & & 1/2 & \end{array} \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & 0 & 13/2 & 1 & 0 & 1/2 & 0 & 0 \\ x_5 & 0 & -21/2^* & 1/4 & 0 & 1 & -1/4 & 0 & -5 \\ x_7 & 0 & -3/2 & 1/4 & 0 & 0 & -1/4 & 1 & M -2 \\ x_1 & 1 & 3/2 & 3/4 & 0 & 0 & 1/4 & 0 & 2 \\ \hline & 0 & 4 & 1/2 & 0 & 0 & 1/2 & 0 & 4 \\ \text{ratio} & & 8/21 & & & & 2 & & \end{array} \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & 0 & 13/2 & 1 & 0 & 1/2 & 0 & 0 \\ x_2 & 0 & 1 & -1/42 & 0 & -2/21 & 1/42 & 0 & 10/21 \\ x_7 & 0 & 0 & 3/14 & 0 & -1/7 & -3/14 & 1 & M-9/7 \\ x_1 & 1 & 0 & 11/14 & 0 & 1/7 & 3/14 & 0 & 9/7 \\ \hline & 0 & 0 & 25/42 & 0 & 8/21 & 17/42 & 0 & 44/21 \end{array} \end{equation*} Hence, the optimal solution of the primal problem is $(\dfrac97,\dfrac{10}{21},0)^T$, with an optimal value of $\dfrac{44}{21}$.

Find the optimal solution by GNU Octave

I post the Octave code for you to verify the optimal solution shown above.

octave:1> c = [2 -1 3]';
octave:2> A = [2 3 -5; -1 9 -1; 4 6 3];
octave:3> b = [4 3 8]';
octave:4> [x_max,z_max] = glpk(c,A,b,[0,0,0]',[],"UUL","CCC")
x_max =

   1.28571
   0.47619
   0.00000

z_max =  2.0952

[Math] KKT condition with equality and inequality constraints

Note that the general form of KKT you wrote is $$ \nabla f(x^{*})-\sum_{j=1}^{l}\gamma_j^*\nabla g_j(x^*)-\color{red}{\sum_{i=1}^m\lambda_i^*\nabla h_i(x^*)}=0 $$ while for this problem you have got $$ \begin{bmatrix} 2(x_1-3)\\ 2(x_2-2)\\ \end{bmatrix}-\gamma_1\begin{bmatrix} -2x_1\\ -2x_2\\ \end{bmatrix}-\gamma_2\begin{bmatrix} 1\\ 0\\ \end{bmatrix}-\gamma_3\begin{bmatrix} 0\\ 1\\ \end{bmatrix}=0 $$ that is without the equlity part. The right equation is $$ \begin{bmatrix} 2(x_1-3)\\ 2(x_2-2)\\ \end{bmatrix}-\gamma_1\begin{bmatrix} -2x_1\\ -2x_2\\ \end{bmatrix}-\gamma_2\begin{bmatrix} 1\\ 0\\ \end{bmatrix}-\gamma_3\begin{bmatrix} 0\\ 1\\ \end{bmatrix}-\color{red}{\lambda\begin{bmatrix} 1\\ 2\\ \end{bmatrix}}=0 $$ together with $x_1+2x_2=4$.

Now $x_2=0$ gives $x_1=4$ which is infeasible point ($x_1^2+x_2^2>5$), hence $x_2>0$ and $\gamma_3=0$.

Similarly, $x_1=0$ gives $x_2=2$ (and $\gamma_3=0$), $x_1^2+x_2^2<5$ (and $\gamma_1=0$), which leads to $\lambda=0$ and $\gamma_2=-6$. It is impossible as $\gamma_2\ge 0$, hence, $x_1>0$ and $\gamma_2=0$.

Next step is to try $\gamma_1=0$, it will give after some algebra $\lambda=-6/5$ and an infeasible point ($x_1^2+x_2^2>5$), then $\gamma_1>0$ and $x_1^2+x_2^2=5$.

Solving two equations \begin{align} x_1+2x_2&=4,\\ x_1^2+x_2^2&=5 \end{align} gives only one feasible point $(2,1)$. Check that all KKT conditions are satisfied ($\gamma_1=1/3$, $\lambda=-2/3$), then it is a KKT point.

Best Answer

Related Solutions

[Math] How to solve this operation research problem using dual simplex method

Find the optimal solution by the dual simplex algorithm

Find the optimal solution by GNU Octave

[Math] KKT condition with equality and inequality constraints

Related Question