0
$\begingroup$

Hi just as a test I'm trying to solve the following LP with Lagrange multipliers.

$min -x_1$

$s.t$

$x_2 \leq 1 - x_1$

$x_1, x_2 \geq 0 $

I add slack variables to have a equality constrained LP

$min -x_1$

$s.t$

$x_2 +x_1 +s_1 -1 =0$

$x_1 -s_2 = 0 $

$x_2 - s_3=0$

I then look at the gradients and find the following system

$-1 + \lambda_1 + \lambda_2 =0 $

$\lambda_1 + \lambda_3 =0 $

$\lambda_1 =0 $

$-\lambda_2 =0 $

$-\lambda_3 =0 $

This system is not consistent though, since it says $-1=0$

If this happens, that is there is no $\lambda_i$ such that the system is satisfied then the problem is unbounded. That is not the case though, since we see that the optimal of $x_1=1,x_2=0$ is optimal with objective value $-1$. I've messed something up here basic. Some feedback would be much appreciated.

$\endgroup$
  • 1
    $\begingroup$ Do you need $s_3$? Given $x_1+x_2+s_1-1=0$ and $x_1-s_2=0$ then you have $x_2+s_1+s_2-1=0$. And normally one begins with $\nabla f=\lambda\nabla g$ which would give $1+\lambda_1+\lambda_2=0$ instead of $-1+\lambda_1+\lambda_2=0$. $\endgroup$ – John Wayland Bales Jul 25 '16 at 20:12
  • $\begingroup$ I've solved the problem via KKT conditions. Thanks for the tip, it got me to the point where i could figure it out. $\endgroup$ – Vogtster Jul 26 '16 at 0:34
  • 1
    $\begingroup$ @Vogster Glad it helped. $\endgroup$ – John Wayland Bales Jul 26 '16 at 3:29

Your Answer

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

Browse other questions tagged or ask your own question.