0
$\begingroup$

KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for strong duality in all cases, and also sufficient when the primal problem becomes convex (i.e. when the objective and inequality constraints all become convex and the equality constraints are affine).

However, in one of my class slides it presents a different version of KKT conditions with the additional LICQ (i.e. active inequality constraints and equality constraints have linearly independent gradients). I'm really confused why LICQ is needed here at all. Does requiring LICQ additionally improve or generalise the usual LICQ-free version of KKT? I don't see how it can (the conclusion the slide shows doesn't seem strengthened, despite requiring more). So I'm curious to know where LICQ can come into play. Thanks.

$\endgroup$
  • $\begingroup$ How does LICQ change the KKT conditions other than turning them into necessary conditions? $\endgroup$ – LinAlg Dec 11 '18 at 18:32
  • $\begingroup$ @LinAlg it seems that in Boyd's book there's no mention of LICQ in the KKT conditions. $\endgroup$ – Vim Dec 12 '18 at 1:32
  • $\begingroup$ LICQ is an alternative to Slater's condition $\endgroup$ – LinAlg Dec 12 '18 at 1:37
  • 1
    $\begingroup$ Vandenberghe and Boyd use Slater's condition rather than LICQ. You need some kind of constraint qualification to make the KKT conditions necessary- there are many constraint qualification conditions. $\endgroup$ – Brian Borchers Dec 13 '18 at 4:03
  • $\begingroup$ @BrianBorchers thanks. May I ask a converse question: if the problem is convex and $C^1$, KKT conditions are satisfied, but no CQ is assumed, then does it necessarily imply optimality? (Namely are KKT still sufficient?) $\endgroup$ – Vim Dec 13 '18 at 7:07
3
$\begingroup$

It's possible for a convex optimization problem to have an optimal solution but no KKT points. Constraint qualifications such as Slater's condition, LICQ, MFCQ, etc. are necessary to ensure that an optimal solution will satisfy the KKT conditions.

For example, consider the problem

$\min x_{2}$

subject to

$(x_{1}-1)^{2}+x_{2}^{2} \leq 1$

$(x_{1}+1)^{2}+x_{2}^{2} \leq 1$

Here, the only feasible point is $x^{*}_{1}=0$, $x^{*}_{2}=0$. Thus that point is an optimal solution. However, you can check and you'll find that the KKT conditions are not satisfied at $x^{*}$.

$\endgroup$

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.