KKT Conditions

The Karush-Kuhn-Tucker (KKT) conditions are first-order necessary conditions for a solution in nonlinear programming to be optimal. Named after William Karush, Harold W. Kuhn, and Albert W. Tucker, these conditions generalize the method of Lagrange multipliers to handle inequality constraints.

Background

The KKT conditions apply to the general constrained optimization problem:

\begin{align} \min_{\theta} \quad & L(\theta)\ \text{subject to:} \quad & E_j(\theta) = 0, \quad j = 1,2,...,m\ & I_k(\theta) \geq 0, \quad k = 1,2,...,n \end{align}

where:

• $L(\theta )$ is the objective function to be minimized
• $E_j(\theta )$ are equality constraints
• $I_k(\theta )$ are inequality constraints
• $\theta \in {\mathbb{R}}^D$ is the design vector

The KKT Conditions

For a solution ${\theta }^{\ast }$ to be a local optimum of the constrained problem, the following KKT conditions must be satisfied:

1. Stationarity

${\nabla }_{\theta }L({\theta }^{\ast })-{\sum }_{j=1}^m{\lambda }_j^{\ast }{\nabla }_{\theta }{E}_j({\theta }^{\ast })-{\sum }_{k=1}^n{\lambda }_{m+k}^{\ast }{\nabla }_{\theta }{I}_k({\theta }^{\ast })=0$

This can be written as the gradient of the Lagrangian equals zero:

${\nabla }_{\theta }\mathcal{L}({\theta }^{\ast },{\lambda }^{\ast })=0$

where the Lagrangian is defined as:

$\mathcal{L}(\theta ,\lambda )=L(\theta )-{\sum }_{j=1}^m{\lambda }_j{E}_j(\theta )-{\sum }_{k=1}^n{\lambda }_{m+k}{I}_k(\theta )$

2. Primal Feasibility

a) All equality constraints are satisfied: $E_j({\theta }^{\ast })=0,\forall j=1,2,...,m$

b) All inequality constraints are satisfied: $I_k({\theta }^{\ast })\ge 0,\forall k=1,2,...,n$

3. Dual Feasibility

The Lagrange multipliers for inequality constraints are non-negative: ${\lambda }_{m+k}^{\ast }\ge 0,\forall k=1,2,...,n$

4. Complementary Slackness

${\lambda }_{m+k}^{\ast }{I}_k({\theta }^{\ast })=0,\forall k=1,2,...,n$

This means that for each inequality constraint, either:

• The constraint is active (binding): $I_k({\theta }^{\ast })=0$ and ${\lambda }_{m+k}^{\ast }\ge 0$, or
• The constraint is inactive: $I_k({\theta }^{\ast })>0$ and ${\lambda }_{m+k}^{\ast }=0$

Interpretation of the Conditions

The KKT conditions have important interpretations:

Stationarity

At the optimum, the gradient of the objective function must be in the span of the gradients of active constraints. This means that any attempt to improve the objective must violate at least one constraint.

Complementary Slackness

This condition embodies the idea that inequality constraints only influence the optimal solution when they are active (binding). If a constraint is not active, its corresponding multiplier is zero, meaning it has no effect on the solution.

Dual Feasibility

The non-negativity of multipliers for inequality constraints reflects that these constraints are one-sided. Relaxing an inequality constraint can only improve (or leave unchanged) the objective value.

Example

Consider the problem:

\begin{align} \min_{x,y} \quad & x^2 + y^2\ \text{subject to:} \quad & x + y \geq 2 \end{align}

Let’s apply the KKT conditions:

1. Lagrangian: $\mathcal{L}(x,y,\lambda )=x^2+y^2-\lambda (x+y-2)$

2. Stationarity:

   • $\frac{\partial \mathcal{L}}{\partial x}=2x-\lambda =0⟹x=\frac{\lambda }{2}$
   • $\frac{\partial \mathcal{L}}{\partial y}=2y-\lambda =0⟹y=\frac{\lambda }{2}$

3. Primal Feasibility: $x+y\ge 2$

4. Dual Feasibility: $\lambda \ge 0$

5. Complementary Slackness: $\lambda (x+y-2)=0$

From stationarity, $x=y=\frac{\lambda }{2}$. From complementary slackness, either $\lambda =0$ or $x+y=2$.

If $\lambda =0$, then $x=y=0$, violating primal feasibility. If $x+y=2$, then $2(\frac{\lambda }{2})=2⟹\lambda =2$.

Therefore, $x=y=1$ is the solution, with $\lambda =2$.

Special Cases

Linear Programming

For linear programming problems (linear objective and constraints), the KKT conditions are both necessary and sufficient for optimality.

Convex Programming

For convex programming problems (convex objective, convex inequality constraints, and affine equality constraints), the KKT conditions are both necessary and sufficient for global optimality.

Constraint Qualifications

The KKT conditions are guaranteed to be necessary conditions for optimality only when certain constraint qualifications are satisfied. Common constraint qualifications include:

1. Linear Independence Constraint Qualification (LICQ): The gradients of all active constraints are linearly independent.

2. Mangasarian-Fromovitz Constraint Qualification (MFCQ): The gradients of active inequality constraints are positively linearly independent.

3. Slater’s Condition: For convex problems, there exists a strictly feasible point (a point satisfying all inequality constraints strictly).

Related Pages

• Lagrange Multipliers
• Constrained Optimization
• Penalty Methods
• Augmented Lagrangian Method