WOLFRAM NOTEBOOK

Karush-Kuhn-Tucker (KKT) Conditions for Nonlinear Programming with Inequality Constraints

boundary height

low

mid

high

This Demonstration explores a constrained nonlinear program in which the objective is to minimize a function

f(x,y)

subject to a single inequality constraint

g(x,y)≤0

. The top-left box shows the level sets of

as gray contours, the level sets of

as blue contours and the feasible region as a shaded blue area. The optimal feasible solution is shown as a red dot. Clicking anywhere inside the top-left box selects a point as a candidate solution; the radio buttons adjust the location of the feasible region. All three boxes display visual representations of the Karush–Kuhn–Tucker conditions, along with a green checkmark or a red Χ to indicate that the candidate does or does not satisfy the condition, respectively. In particular, the top two boxes display

∇f

as a black arrow and

∇g

as a blue arrow, while the bottom left box displays a point corresponding to the KKT multiplier

(provided it exists, which requires that either

∇f=0

or that

∇f

and

∇g

are collinear) and the value of

. In order for a solution to be the gobal optimum, it is necessary to satisfy all of the conditions simultaneously.

Details

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

minf(x,y)

such that

g(x,y)≤0

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:

∇f(

)=-μ∇g(

)

2. Primal feasibility:

)≤0

3. Dual feasibility:

μ≥0

4. Complementary slackness:

μg(

)=0

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

g=0

) or on the interior (where

g<0

). 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

∇f=0

(meaning that

becomes flat on the boundary) or

∇f∝∇g

(meaning that the level sets of

and

lie tangent to each other). The first case forces

μ=0

, while the second forces

μ≠0

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

∇f=0

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

∇f=0

and

∇f∝∇g

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

∇f=0

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

∇f

and

∇g

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

g<0

, in which case complementary slackness enforces

μ=0

and thus

∇f=0

. On the boundary, we have

g=0

, 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

∇f

as a black arrow and

∇g

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

∇f=0

or when

∇f

and

∇g

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

∇f=0

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

∇f

(the black arrow) and

∇g

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

μ=0.4

and

g=0

; 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

∇f=-μ∇g

. 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

μ≠0

(so

∇f≠0

) and

g≠0

(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

∇f=0

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

∇f

and

∇g

point in the same direction and

μ<0

, which indicates that moving further toward the interior would decrease

; therefore, the current solution cannot be optimal.

References

[1] D. P. Bertsekas, Nonlinear Programming (2nd ed.), Belmont, MA: Athena Scientific, 1999.

[2] R. G. Eustáquio, E. W. Karas and A. A. Ribeiro, Constraint Qualifications for Nonlinear Programming, Working paper, Department of Mathematics, Federal University of Paraná, Brazil, 2007. www.researchgate.net/publication/230663810_Constraint _Qualifications _for _Nonlinear _Programming.