[Math] When is LICQ useful in KKT conditions

convex optimizationkarush kuhn tuckernonlinear optimizationoptimization

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.

Best Answer

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^{*}$.