Find the Lagrangian dual solution for the primal $\min_{x,y,z}(x+y-z)$ subject to $x-y-3z=1$ and $x,y,z\ge0$

calculuslagrange multipliernonlinear optimizationoptimization

I want to solve the dual problem of the given primal

\begin{equation*}
\begin{array}{ll@{}ll}
{\underset{x,y,z}{minimize}} & x+y-z &\\
\text{subject to}& x-y-3z=1 \\
& x,y,z \geq 0
\end{array}
\end{equation*}

The Lagrangian is
\begin{equation*}
L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = (x+y-z) – \lambda_1x -\lambda_2y – \lambda_3z + \kappa(x-y-3z-1)
\end{equation*}

and the dual function is

\begin{equation*}
L_{dual}(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = \max_{x,y,z}(x+y-z) – \lambda_1x -\lambda_2y – \lambda_3z + \kappa(x-y-3z-1)
\end{equation*}

So the dual problem is
\begin{array}{ll} \text{minimize} & L_{dual}(\lambda_1,\lambda_2, \lambda_3, \kappa) \\
\text{subject to} & \lambda_1,\lambda_2,\lambda_3 \geq 0
\end{array}

KKT conditions are:

\begin{equation*}
\begin{array}{ll@{}ll}
&\nabla_x L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = 1 – \lambda_1 + \kappa = 0\\
&\nabla_y L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = 1 – \lambda_2 – \kappa = 0\\
&\nabla_z L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -1 – \lambda_3 – 3 \kappa = 0\\
&\\
&\nabla_{\lambda_1} L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -x \leq 0\\
&\nabla_{\lambda_2} L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -y \leq 0\\
&\nabla_{\lambda_3} L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -z \leq 0\\
&\nabla_{\kappa} L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = x-y-3z-1 = 0 \\
&\\
&\lambda_1(-x) = 0 \\
&\lambda_2(-y) = 0 \\
&\lambda_3(-z) = 0 \\
&\\
&\lambda_1,\lambda_2,\lambda_3 \ge 0
\end{array}
\end{equation*}

Now I want to get $x,y,z$ to set them into the dual function and this is where my problem is, because I don't know what I'm doing here.

First I solved the first 3 derivatives after $\lambda_1,\lambda_2,\lambda_3$, so I get

\begin{equation*}
\begin{array}{ll@{}ll}
&\lambda_1 = 1+\kappa \\
&\lambda_2 = 1-\kappa \\
&\lambda_3 = -(1+\kappa)
\end{array}
\end{equation*}

and put them into the complementary condition

\begin{equation*}
\begin{array}{ll@{}ll}
&(1+\kappa)(-x) = 0 \\
&(1-\kappa)(-y) = 0 \\
&(-(1+\kappa))(-z) = 0
\end{array}
\end{equation*}

Normally this should help, but I don't know further, could someone help a little bit?

Best Answer

By drawing the feasible region, it was possible to see that the maximum couldn't be reached. We have that, for $t>0$, $(x_{t},y_{t},z_{t}) = (2,1,0)^{T} + t (1,1,0)^{T} \geq (0,0,0)^{T}$ is feasible, but the objective function's value is $x_{t}+y_{t}-z_{t}=3+2t$, which increases indefinitely.

Related Question