The Karush–Kuhn–Tucker conditions (a.k.a. KKT conditions or Kuhn–Tucker conditions) are a set of necessary conditions for a solution of a constrained nonlinear program to be optimal [1]. The KKT conditions generalize the method of Lagrange multipliers for nonlinear programs with equality constraints, allowing for both equalities and inequalities. In this Demonstration, we consider only inequality constraints. Specifically, the problem used for this Demonstration has the form

such that

where

and

are both real-valued, differentiable functions on

that satisfy the regularity conditions needed for the KKT conditions to apply [2]. For this simple problem, the KKT conditions state that a solution

is a local optimum if and only if there exists a constant

(called a KKT multiplier) such that the following four conditions hold:

1. Stationarity:

2. Primal feasibility:

3. Dual feasibility:

4. Complementary slackness:

There are two possibilities for the optimal solution: it can occur either on the boundary of the feasible set (where

) or on the interior (where

). If it occurs on the boundary, then we are left with the equivalent of an equality constraint, in which case the simple method of Lagrange multipliers applies. The preceding stationarity condition is identical to the one for Lagrange multipliers, and it captures instances for which either

(meaning that

becomes flat on the boundary) or

(meaning that the level sets of

and

lie tangent to each other). The first case forces

, while the second forces

.

If, on the other hand, the optimum occurs on the interior, then the constraint has no effect on the calculation of the optimum. This can only occur where

, but the stationarity condition guarantees simply that at least one out of

and

is true, with no guarantees about which one holds. Additional conditions are needed to ensure that

for any candidate optimum on the interior. The snapshots include various examples of solutions that are not locally optimal and satisfy some (but not all) of the KKT conditions.

Dual feasibility ensures that the optimum occurs on the correct side of the feasible boundary by ensuring that

and

point in opposite directions. Complementary slackness ensures that the correct restriction is enforced. The condition itself forces at least one of

and

to vanish. On the interior of the feasible set, we have

, in which case complementary slackness enforces

and thus

. On the boundary, we have

, in which case

is unrestricted.

The three boxes contained in this Demonstration graphically illustrate each of these conditions. Primal feasibility is satisfied exactly when the chosen point lies inside the feasible region. The top two boxes of the Demonstration display

as a black arrow and

as a blue arrow. The bottom-left box shows a point on the

versus

axis corresponding to the current values of

and

. The positive

and negative

axes are highlighted to indicate the coordinates that simultaneously satisfy dual feasibility and complementary slackness. Note that

is only defined when

or when

and

are collinear, and that no point is plotted when

does not exist.

Snapshot 1: an optimal solution on the boundary of the feasible region. Here we do not have

, so the optimal solution is a stationary point on the boundary. Note that

(the black arrow) and

(the blue arrow) point in opposite directions. In this case, we have

and

; therefore, dual feasibility and complementary slackness are also satisfied.

Snapshot 2: a clearly nonoptimal solution on the interior of the feasible region. Stationarity is not satisfied, therefore there exists no value

such that

. With no KKT multiplier, dual feasibility and complementary slackness are meaningless, and so there is nothing to report in the bottom-left box.

Snapshot 3: a nonoptimal solution that does not satisfy complementary slackness. This means that

(so

) and

(so we are not on the boundary), which contradicts the only possible interior solutions coinciding with

being flat.

Snapshot 4: a nonoptimal solution that satisfies only stationarity. This indicates that if the level sets of

were extended outside of the feasible region, then one would lie tangent to a level set of

at this point, but the point is obviously not feasible.

Snapshot 5: an optimal solution inside the feasible region. As is necessary for such a solution, we have

.

Snapshot 6: a nonoptimal solution that does not satisfy dual feasibility. This is identical to the example from Snapshot 5, but the point has been shifted to the right and away from where

is flat. Here

and

point in the same direction and

, which indicates that moving further toward the interior would decrease

; therefore, the current solution cannot be optimal.

[1] D. P. Bertsekas,

*Nonlinear Programming* (2nd ed.), Belmont, MA: Athena Scientific, 1999.