2
$\begingroup$

Min$_{x}~x$
Subject to $x \geq 0$
For this problem, is $(x^{*}, \lambda^{*})=$$(0,0)$ a KKT point ?

My try : I formulated corresponding Lagrangian and tried to find out the KKT point(s). But it is not giving $(0,0)$. But if we notice, $x=0$ is the solution for for the given constrained optimization problem.

$\endgroup$
4
$\begingroup$

No. The KKT point is $(x^*,\lambda^*)=(0,1)$. $\lambda=0$ is not dual feasible.

The Lagrangian is $L(x,\lambda)=x-\lambda x$, and the dual problem is $$\begin{array}{ll} \text{maximize} & 0 \\ \text{subject to} & \lambda = 1 \\ & \lambda \geq 0 \end{array}$$ So clearly, $\lambda^*=1$ is the optimal dual point.

It's actually not difficult to see why this is the case if you consider the dual cost interpretation. If the primal model is changed to $x\geq \epsilon$, where $\epsilon$ is small, then the objective should change by $\lambda\epsilon$. Since this perturbation yields $x^*=\epsilon$, it is clear that $\lambda^*=1$.

$\endgroup$
  • $\begingroup$ Thank you sir. $(1,0)$ is obviously a Lagrangian saddle point and as the programming problem is given here is Convex programming problem and Slater's constraint qualification holds, it is KKT point. But, why can't we find the point $(1,0)$ directly by KKT conditions. $\endgroup$ – user107723 Apr 17 '14 at 5:08
  • $\begingroup$ I'm not convinced you can't. What did you try? What do you think the KKT conditions are? $\endgroup$ – Michael Grant Apr 17 '14 at 13:09
  • $\begingroup$ I mean by KKT optimality condition (First order partial derivative equating to zero) $\endgroup$ – user107723 Apr 17 '14 at 16:45
  • $\begingroup$ Well that's good, but from what I'm seeing, that condition implies $\lambda=1$. $\endgroup$ – Michael Grant Apr 18 '14 at 1:45
  • 1
    $\begingroup$ Well, the derivative test fails because the objective is linear in $x$. But you can get $x=0$ from complementary slackness. $\endgroup$ – Michael Grant Apr 18 '14 at 11:09

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.