Karush-Kuhn-Tucker (KKT) Conditions

• categories: Optimization, Method

Definition:
The Karush-Kuhn-Tucker (KKT) conditions are necessary (and sometimes sufficient) conditions for a solution to be optimal in a nonlinear optimization problem with constraints.

The general problem:
Minimize $f(x)$ subject to:

• Equality constraints: $h_i(x)=0,i=1,\dots ,m$,
• Inequality constraints: $g_j(x)\le 0,j=1,\dots ,p$.

KKT Conditions:
Let $x^{\ast }$ be a candidate solution, and let ${\lambda }_i$ and ${\mu }_j$ be the Lagrange multipliers for the equality and inequality constraints, respectively. The KKT conditions are:

1. Stationarity:
   $\nabla f(x^{\ast })+{\sum }_{i=1}^m{\lambda }_i\nabla h_i(x^{\ast })+{\sum }_{j=1}^p{\mu }_j\nabla g_j(x^{\ast })=0$

2. Primal Feasibility:
   $h_i(x^{\ast })=0\text{for all }i$
   $g_j(x^{\ast })\le 0\text{for all }j$

3. Dual Feasibility:
   ${\mu }_j\ge 0\text{for all }j$

4. Complementary Slackness:
   ${\mu }_j{g}_j(x^{\ast })=0\text{for all }j$
   (If ${\mu }_j>0$, then $g_j(x^{\ast })=0$; if $g_j(x^{\ast })<0$, then ${\mu }_j=0$.)

Intuition:
The KKT conditions generalize the Lagrange Multipliers Method to handle inequality constraints.

• Stationarity ensures that $x^{\ast }$ is a critical point of the Lagrangian function.
• Primal feasibility ensures that $x^{\ast }$ satisfies the original constraints.
• Dual feasibility ensures non-negativity of the multipliers for inequality constraints.
• Complementary slackness couples the satisfaction of inequality constraints with their associated multipliers.

Applications:

• Convex optimization: For convex problems, the KKT conditions are both necessary and sufficient for optimality.
• Non-convex optimization: KKT conditions are necessary, but not always sufficient.

Lagrangian Function:
The KKT conditions derive from the Lagrangian function:
$\mathcal{L}(x,\lambda ,\mu )=f(x)+{\sum }_{i=1}^m{\lambda }_i{h}_i(x)+{\sum }_{j=1}^p{\mu }_j{g}_j(x)$

Special Case (Unconstrained Problems):
If there are no constraints, the KKT conditions reduce to $\nabla f(x)=0$.