Introduces constrained optimization with inequality constraints and the Karush Kuhn Tucker conditions.
A constrained optimization problem with inequality constraints can be written as
Definition 1 Let
be a feasible point. If
, we say that the constraint
is
active at
, if
then
is
inactive at
.
The set of active constraints at
is denoted by;
Definition 2 We say
is a
regular point in
if
is a linearly independent set.
Theorem 1 (Karush-Kuhn-Tucker Conditions) if
is a regular point of
and
is a local minimizer of
over
then there exist scalars
and
such that;
,
(complementary slackness condition),
.
Since
, we have that if
is inactive at
(i.e., if
) then we must have
. Therefore, some versions of the theorem feature only the active inequality constraints in the third condition.
Example 1 We pictorially demonstrate some examples of active inequality constraints: consider the case where the set
is a convex set bounded by three inequality constraints,
,
, and
. Now, consider these three possibilities for the minimizer
of
in
, illustrated in
[link] :
In this case, the minimizer is in the interior of the set
, and no constraints are active; therefore, the minimizer of the constrained problem matches the minimizer of the unconstrained problem, and the solution is found by solving
, which ignores all inequality constraints. This means that each
.
In this case, the minimizer has one active constraint (
). Consider the gradient of the constraint
, which is orthogonal to the tangent space. If
and
are not collinear (scalar multiples of one another), then there is a direction within the tangent space in which the value of
would decrease and
would not be a minimizer. Otherwise, if
for
, then both gradients point in the same direction and the value of
would decrease by moving in the opposite direction toward the interior of
, and so
would not be a minimizer. Therefore, we must have
with
, as specified by the KKT conditions. In this case the inactive constraints
and
are ignored.
In this case, the minimizer has two active constraints (
and
).
In this case, the directions
in which we can move from
within
must obey
and
. Similarly, moving in a direction
decreases the value of
below
if
. Thus, for us to be able to find such a direction
we must have that
with
and
, which would give
Thus, the minimizer
of
must obey
with
and
.
The example illustrates a simple “recipe” for solving inequality constraint optimization problems includes the following steps:
Pick a candidate active set
,
Build the corresponding form of the third KKT condition:
and solve for
,
, and
,
If
and
for
then
is a solution. Otherwise, pick a new candidate active set
and repeat Step 2.