What are KKT conditions?

KKT conditions are derivative tests of the first order for optimal solutions. These solutions are contained within a nonlinear programming Optimization problems with non-linear objective function constraintsspace.

Before we go ahead and explain the KKT theorem, it is necessary to understand what a saddle point is.

The saddle point

Let's look at the graph below:

You will notice that the point $(0,0)$has no gradient and no second derivative. Also, it does not contain a global or local minimum.

The KKT theorem is simple. Let's say we choose a variable from the convex subset of these three values —$R^n$, $a^*$, and a point, $\omega$. Then, we can say that if $a^*$and $\omega$ are the saddle point of the Lagrangian function, then $a^*$can be a vector that can define optimum results for the minimization or maximization problems.

The KKT theorem makes use of the hyperplane separation theoremhyperplane existence between two disjoint convex sets that are closed by trying to find a supporting hyperplaneA hyperplane that tends to fulfill the conditions for convex sets divided being (1) entirely contained and (2) set having a boundary point on the hyperplane for the vector $a^*$.

Note: Read more about hyperplane theorems here.

Now, let's go forward and look at the conditions of the KKT theorem.

Important conditions

There are exactly four conditions for the problem defined in the KKT theorem:

1. Stationarity condition (inequality + equality constraint)

2. Complementary slackness (assurance of no feasible direction that could improve the function)

3. Primal feasibility (inequality constraint)

4. Dual feasibility (inequality constraint)

The problem we stated above is one subjected to minimization. For our explanation, let's suppose a problem $P$and give it a syntax:

Let's now state the conditions of this problem $P$for it to have an optimal $x$value.

Stationarity condition

The stationarity condition tends to take a DualConsists of all linear forms of a vector space of P; $D$. It simply states:

This dual pair tends to minimize the Lagrangian functionThis helps finding the maximum or minimum of a multi-variable function. containing the three variables.

Complementary slackness

This condition is only defined for inequality constraints:

In the statement given above, either the variable$A_i(x)$or its dual$D_i(x)$is equal to$0$. This means that the inequality constraint is present and concise.

Primal feasibility

Primal feasibility basically means that the "subject to" conditions defined in the problem$P$must be satisfied by$x$at all costs.

Dual feasibility

The dual feasibility condition states that the dual variables must be non-negative:

Once all of these conditions are fulfilled, we can assume that we've found the optimal solution$x$ and its optimal dual$D$at the same time.