A Brief Summary of KKT Conditions

Posted on Views: Word count in article: 487 Reading time ≈ 2 mins.

In nonlinear programming, the Karush–Kuhn–Tucker (KKT) conditions are necessary conditions to determine whether a point is an extreme point. The necessary condition here means that the solution that satisfies the KKT conditions is not necessarily the optimal solution (e.g., saddle point), but if the KKT conditions are not satisfied, it must not be the optimal solution.

For convex programming, the KKT conditions are sufficient and necessary conditions to determine whether a point is an extreme point. If a point satisfies the conditions, it must be an extreme point and must be a global optimal solution.

Note: In a convex optimization problem, the objective function is convex and the domain is defined as a convex set.

Lagrangian function

For a given minimization problem:

min:f(x)s.t.gi(x)<=0,j=1,2,...,mhj(x)=0,k=1,2,...,nmin: f(x)\\ s.t.\\ g_i(x)<=0, j=1,2,...,m\\ h_j(x)=0,k=1,2,...,n

Note: In the case of a maximization problem, i.e., max:f(x)max: f(x), the inequality constraint needs to be rewritten to the form g(x)≥0g(x)≥0.

You can get its Lagrangian function as follows:

L(x,λ,μ)=f(x)+λg(x)+μh(x)L(x,\lambda,\mu)=f(x)+\lambda g(x)+\mu h(x)

Because the problem includes multiple inequality and equation constraints, the Lagrangian function can also be expressed as:

L(x,λ,μ)=f(x)+∑i=1mλigi(x)+∑j=1nμjhj(x)L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m}\lambda_i g_i(x)+\sum_{j=1}^{n}\mu_j h_j(x)

Four groups of conditions

KKT conditions include the following four categories:

Stationarity

∇f(x∗)+∑i=1mλi∇gi(x∗)+∑j=1nμj∇hj(x∗)=0 \nabla f(x^*)+\sum_{i=1}^{m}\lambda_i \nabla g_i(x^*)+\sum_{j=1}^{n}\mu_j \nabla h_j(x^*)=0

Complementary slackness

λigi(x∗)=0,i=1,...,m \lambda_i g_i(x^*)=0, i=1,...,m

Dual feasibility

λi>=0,i=1,...,m \lambda_i>=0, i=1,...,m

The gradient direction of g(x)g(x) is the same as that of the negative gradient direction of f(x)f(x).

Primal feasibility

gi(x∗)<=0,i=1,...,mhj(x∗)=0,j=1,...,n g_i(x^*)<=0, i=1,...,m\\ h_j(x^*)=0, j=1,...,n

  • If 𝑔(𝑥)<0𝑔(𝑥)<0: The optimal solution is located inside the domain, and this constraint is inactive. ∇f(x∗)=0\nabla f(x^*)=0, λ=0\lambda=0.

  • If 𝑔(𝑥)=0𝑔(𝑥)=0: The optimal solution is located on the boundary of the domain, and this constraint is active. ∇𝑓(x∗)=−λ∇g(x)\nabla 𝑓(x^*)=−\lambda \nabla g(x), λ>=0\lambda>=0.

Therefore, the KKT conditions for the above problem are as follows:

∇f(x∗)+∑i=1mλi∇gi(x∗)+∑j=1nμj∇hj(x∗)=0λigi(x∗)=0,i=1,...,mλi>=0,i=1,...,mgi(x∗)<=0,i=1,...,mhj(x∗)=0,j=1,...,n \nabla f(x^*)+\sum_{i=1}^{m}\lambda_i \nabla g_i(x^*)+\sum_{j=1}^{n}\mu_j \nabla h_j(x^*)=0\\ \lambda_i g_i(x^*)=0, i=1,...,m\\ \lambda_i>=0, i=1,...,m\\ g_i(x^*)<=0, i=1,...,m\\ h_j(x^*)=0, j=1,...,n\\

In the above formula, x∗x^* denotes the optimal solution.

Note: There is no non-negative requirement for the equation-constrained Lagrange multiplier μj\mu_j.