2
$\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$
7
  • $\begingroup$ How does LICQ change the KKT conditions other than turning them into necessary conditions? $\endgroup$
    – LinAlg
    Dec 11, 2018 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, 2018 at 1:32
  • $\begingroup$ LICQ is an alternative to Slater's condition $\endgroup$
    – LinAlg
    Dec 12, 2018 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$ Dec 13, 2018 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, 2018 at 7:07

1 Answer 1

7
$\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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .